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!