CSE Blog - quant, math, computer science puzzles

Source: FunctionSpace.org Problem: Given the polygons P and Q as shown in the grid below, cut P into two polygons P1 and P2 such that, when pasted together differently, they form Q. Update ( 21 June 2014 ) : Solution by Varun and Adwait in comments!

Source: Asked to a friend at Goldman Sachs Quant Interview Problem: Estimate the value of pi using a dice Update: (21 June 2014) Solution posted by Tushar Makkar, 'My first amateur attempt', Satadip, Gaurav Bajaj and me (Pratik) in comments. Thanks

Source: Cute problem sent by Sudeep Kanath Problem: Prove that (2n choose n) is never a perfect power Update ( 21 June 2014 ): Solution:  Posted by Sandeep, Dinesh Krithivasan and Vishal Khatri in comments.

Source:  The super awesome puzzle blog by Gowtham Kumar  -  Puzzle Tweeter - Coin Problem  who got it from  Wolfram Mathematica Problem: Suppose you have an infinite stock of $a bills and $b bills such that g.c.d(a,b)=1. Find the largest amount of money (integer) that cannot be represented using $a and $b denominations. Shameless plug: If you have not done it already, please like / +1 / follow on:  Quora ,  Twitter ,  Facebook ,  G+ Update (21 June 2014): Solution: Posted by Raunak Kudesia, Sid Hollander and me (Pratik) in comments!

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