CSE Blog - quant, math, computer science puzzles

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

Source: IBM Ponder This Dec 12 ( http://domino.research.ibm.com/comm/wwwr_ponder.nsf/challenges/December2012.html ) - Mailed to me by Aashay Harlalka (Final Year Student, CSE, IITB) Problem: 36 people live in a 6x6 grid, and each one of them lives in a separate square of the grid. Each resident's neighbors are those who live in the squares that have a common edge with that resident's square. Each resident of the grid is assigned a natural number N, such that if a person receives some N>1, then he or she must also have neighbors that have been assigned all of the numbers 1,2,...,N-1. Find a configuration of the 36 neighbors where the sum of their numbers is at least 90. As an example, the highest sum we can get in a 3x3 grid is 20: 1 2 1 4 3 4 2 1 2 Update (24 June 2014): Solution:  Available on  IBM Research Ponder This - December 2012 Solution