Saturday, October 15, 2011

Google Recruitment Puzzle

I was reading an article about how Google recruits and one of the items was an onsite interview. Appearantly such an interview can include the followin riddle: You have 8 balls, out of which one is heavier than the other. How do you decide which one with only two weightings on balanced scale. My solutions is the following:
1) Pick 6 out of the 8 balls
2) Divide the 6 balls from step 1 into 2 groups of 3 each
3) Weight the 2 groups from step 2
4) If they weight the same, weight the remaining 2 balls to find the heaviest among them
5) If the 2 groups from step 3 do not balance, take the group which is heavier
6) From the heavier group in step 3 select 2 balls and leave the third ball aside
7) Weight the 2 balls from step 6 on the scale
8) If they balance, the third ball is heaviest (the one which was left out in step 6)
9) If the balls in step 7 do not balance, then the one that is heavier is actually the ball that was saught in the beginning of the puzzle.
In this way using the decision tree with only 2 weightings, one can determine the heavier ball. When I have time, I will look up the mathematics behind it.

No comments:

Post a Comment