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