CSE Blog - quant, math, computer science puzzles

Source: Just made it up! Problem: Easy: Given 2 sorted arrays of size n, give an efficient algorithm to find the kth largest number. Hard: Given m sorted arrays of size n each, give an efficient algorithm to find the kth largest number. Update (04 December 2010) Solution: Posted by Gaurav Sinha (chera) (CSE IITK 1996 Graduate, Now working at Indian Revenue Service) in comments! Another solution posted by me in comments!

Source: Credit Suisse Placement Test at IITB Problem: You bet 1$ on a coin toss. A win gives u 1$ gain, a loss gives you a 1$ loss. The guy tossing the coin gets what he wants 80% of the time. You start with X$. Find strategy so that you always win. Update (Dec 04, 2010) Assumption: Note that the dealer is just an employee of the casino. You can take him in your group and make an offer he cannot refuse. Solution: Posted by Gaurav Sinha (chera) (CSE IITK 1996 Graduate, Now working at Indian Revenue Service) in comments!

You are trying to buy a stock at the best price. You need to buy it in the next 100 minutes. Every minute you will receive a random price (uniform distribution) that is a number between 1 and 100 dollars and decide whether to buy it or not. 1. Assuming you buy the stock in one trade, give a condition for buying the stock. 2. On average how many minutes will pass before that condition holds (expression or approximation is fine)? 3. If you could split up the trade, i.e, buy different amounts at different minutes, what would you do differently? Update(Nov 17, 2010): Solution posted by Sumit Somani (Senior Undergraduate, CSE, IITB) in comments! Same solution posted by me with spreadsheet in comments!

Source : A Quant Company Placement Test 2010 at IITB Problem : You are given an urn with 100 balls (50 black and 50 white). You pick balls from urn one by one without replacements until all the balls are out. A black followed by a white or a white followed by a black is "a colour change". Calculate the expected number of colour changes if the balls are being picked randomly from the urn. Update (Oct 30, 2010): Solution posted by Ankush Agarwal (Junior Undergraduate, CSE, IITB) in comments! Update (Nov 05, 2010): A different solution posted by Piyush Sao (5th year Dual Degree Elec Student, IIT Madras) in comments!

Source: Placement Test of a Quant Company at IITB in 2010 Problem: Consider a random walk around the edges of a square. From any vertex, the probability of moving to any adjacent vertex is 0.5. Suppose the walk stops as soon as after all traversing through all the vertices, you return to your starting vertex. What is the expected path length? Update (Nov 10, 2010): Solution: 1) First solution posted by Naval Chopra (Final year student, CSE, IIT Bombay) in comments! 2) A more elegant solution posted by Ankush Agarwal (Third Year undergraduate student, CSE, IIT Bombay) in comments! He has also posted a mathematica code for verifying his solution :) 3) A similar solution posted by Yash in comments (with a minor typo though) Thanks a lot for the active participation!

Source : Asked to me by Nigel Coldwell (now posted on his blog) Problem : Two creepers, one jasmine and other rose, are both climbing up and round a cylindrical tree trunk. jasmine twists clockwise and rose anticlockwise, both start at the same point on the ground. before they reach the first branch of the tree the jasmine had made 5 complete twists and the rose 3 twists. not counting the bottom and the top, how many times do they cross? Related video : Solution : My solution posted on Nigel's Blog here . Slightly different solution posted by Gaurav Sinha (1996 CSE IITK passout, now at Indian Revenue Service) in comments! A more general argument by Aaditya Ramdas (CMU Grad Student - CSE IITB 2009 Alumnus - Ex Tower Research Analyst) in comments!

Source : Asked to me by Sudeep Kamath (Third year PhD Student, UC at Berkeley, EE IITB Alumnus) Problem : There are n men, n hats, one hat belonging to each person. A random permutation of hats is picked by the men, whoever gets their own hat, takes it and leaves and a random permutation of the remaining hats is picked and so on. What is the expected number of rounds it takes for everyone to leave? Hint : Answer is n Update (21 Oct 2010): Solution posted by Siddhant Agarwal (Senior Undergraduate, EE, IITB), and a more detailed explanation posted by me in comments!