CSE Blog - quant, math, computer science puzzles

Source: Mailed by Sudeep Kamath (EECS PhD Student, UC Berkeley, EE IITB 2008 Alumnus)

Problem:

A is a 300 x 300 matrix with 17 on the diagonal, and the rest of the entries being 11. What is det (A) ?

Update: (21 June 2014):

Solution posted by Gowtham R (Stanford), Justin Rising, Pavan Bharadwaj, Hansaplatz and gaurushh in comments! Thanks

Disclaimer: It is a made up problem. Not to be attempted by light hearted.

Problem:
I have a 300 word text. I have a large list of indexed strings (Length of string ~ 20, Number of strings ~ 1M). I need to figure out phrases in the 300 word text that match exactly to one of the strings in the large list of strings I have.

A naive approach:
Taking all 45000 (300 C 2) phrases, search in the large list of strings. Can we do better than this? We need to minimize calls to list of indexed strings!

Problem 1: Consider the problem of picking K elements randomly from N elements. Suggest an algorithm. What is the time and space complexity of your algorithm?

Problem 2: Now consider that the stream is infinitely long (i.e. N is unknown). Now how do we pick K elements randomly.

Update (24 June 2014):
Solution: Posted by Himanshu (Prob 1), PlacementIITB2014 (Prob2) and Sid (Prob1 and Prob2) in comments! Thanks
claimtoken-52ac74fbddf1e