Number of Locks and Keys

Problem:
7 thieves wanted to lock the treasure looted from a ship. They wanted to put locks to the treasure where each lock had multiple keys. Find the minimum number of locks N and minimum no. of keys K with every thief subject to the following conditions:-
All the locks should open each time a majority of thieves(4 or more) try to open the locks.
At least one lock remains unopened if less than 4 thieves try opening them.
All locks should have same no. of keys.
All thieves must have same no. of keys with them.

Source:
Shamir's paper on Secret Sharing Scheme states this problem and gives the answer with the explanation that its written in standard Combinatorics books

Expected Number of HH

Source: Placement Paper of one of the CS companies

Problem: A coin is tossed 10 times and the output written as a string. What is the expected number of HH? Note that in HHH, number of HH = 2

Example: In 3 tosses
HHH (2 HH)
HHT (1 HH)
HTH (0 HH)
HTT (0 HH)
THH (1 HH)
THT (0 HH)
TTH (0 HH)
TTT (0 HH)
Expected number of HH in 3 tosses = 2/8 + 1/8 + 1/8 = 0.5

Random point in a circle

This was the killer one. Interesting problem asked to me in one of the interviews.

You are given a black-box which returns a random number between 0 and 1. Give an algorithm to generate a point in the circle of radius 1.

(I was able to solve this but I must admit, its a difficult problem)

Break the sticks

Three question related to stick breaking. A stick is of length 1.

1) The stick drops and breaks at a random point distributed uniformly across the length. What is the expected length of the smaller part? (Source: DB interview)

2) In the above experiment, what is the expected length of the larger part? (Source: Made it up)

3) In the third experiment, the stick is dropped and breaks at two points. What is the probability that the three pieces could form a triangle? (Source: V.K.Bansal notes, MathOverflow.net)

Ants on a Cube

This was asked to me on Dec 1 in campus interviews of one of the companies.

We have a cube. An ant is on one of the corners. It moves randomly with equal probability in all the three directions. What is the expected number of steps to reach the opposite corner.

Note that the probability of the ant reaching the opposite corner in 2 steps is 0, in 3 steps is 6/27, in 4 steps is 0 and so on..

(I was able to solve it :D)

Placements and Puzzles!!!

Some real stud people told me that my blog helped them a lot in their interviews at IITB Campus placements. I am really happy about that. I must admit that my blog helped me too :P. In Morgan Stanley QM interview, about half the questions that were asked to me were from my blog. (Although I never pretended that I am thinking and then solving. I always told them that I have seen this problem before. But still, it gives you an extra delta point). In Deutsche Bank GMC interview, more than half of the questions were from the blog. I would really recommend all puzzle enthusiasts and also people who would be preparing for placements 2010-2011 to solve the book (Mathematical Puzzles: A Connoisseur's Collection) by Peter Winkler. Thanx for all your reviews on the blog. I am especially happy as I got responses from many friends after they were placed that my blog helped them. :)

Thanx junta!

Best of Luck!

Nearest Point problem

This was the question asked to Anirudh in his google interview. He could not do it (who cares! He got the job :D)
I could give a vague but correct answer :)

You have n points on a 2-D plane. You have to execute the query, given a fresh point, which of these n points is closest to it. This is termed as gas-station problem or postman problem, as in asking the question which is the closest gas-station/post-office from some place.

Of course, O(n) can be done {Compare best-so-far value for each point}
But since our set of n points is constant, we would want some pre-processing so that the query time is reduced.

:) Interesting problem. Interesting solution.