October 2, 2015

I will first introduce 2 very interesting puzzles. The first one is: There are 3 switches outside a room, and 3 light bulbs inside the room; the room has no window so you cannot see what is happening in the room. But you know whether you turned on the switch or not. You are only allowed to go into the room once. How do you determine which switch controls which light bulb?

Solution: This one is the easiest. The answer is to turn on any 2 switches (let's say, switch A and B). After 5 minutes, turn off one of the 2 switches (e.g., turn off switch B), and go inside the room. There must be one light bulb on, which is controlled by switch A. Then you can feel the temperature of the remaining two light bulbs. The one that is warmer than the other is controlled by switch B.

The second puzzle is a little bit harder. We are given 2 identical eggs and there is a building of 100 levels. If you throw an egg out of the window at any level, the egg may break or not break. If an egg breaks at level X, that means both of the 2 eggs will definitely break at level (X+1), (X+2), etc. The egg is totally reusable unless it is broken. That is, suppose you throw the egg at level 3 as an experiment; if the egg does not break, then this experiment will have no effect on the egg. What is the best strategy (i.e., the least number of throws in the worst case) to throw those 2 eggs to determine at what level the eggs will break exactly? I want to find such a level X that at level X and any level above it, the eggs will break; but for any level below X, the eggs will not break.

Solution: I got this one during the interview, but it was not an easy one. I will show my solution first.

Suppose you use binary search, if the first one (at level 50) breaks, then you cannot risk the remaining egg; so you have to use a linear search from level 1 up to level 49. The number of throws in the worst case is (1+49)=50 (throwing the first egg 1 time and throwing the second egg 49 times).

Now let us suppose we use a "stepped" linear search, that we throw the first egg at Level 2, Level 4, Level 6, and so on. If the first egg is broken, we only need to use the remaining egg to check the floor we just missed. The number of throws, in the worst case, is (50+1)=51.

In the binary search, we use the first egg too little while we use the second egg too many times; in the stepped linear search, we use the first egg too many times. This inspires us to look for a more balanced solution. So we now change the step size in the stepped linear search. Let us denote the step size as A (in the answer mentioned previously, A = 2). In the worst case, we throw the first egg (100/A) times (the first egg breaks at level 100 in the worst case). Then we have to throw the second egg in a linear way checking all the levels between the two steps we just missed. The number of throws in the worst case is (100/A + A - 1) ≥ 19. I think you know the optimal solution is A = 10. This means we throw the first egg at level 10, level 20, and so on. Whenever the first egg breaks, we just check all the (A-1) levels below that level (in a bottom-up manner, of course!).

Then my solution was 19. However, that is not the right answer. The right answer is 14. A complete analysis can be found here.