## Posts

Showing posts from November, 2010

### Sorted arrays

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!

### Coin Tossing - Lucky Dealer

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!