## Interview Question

Interview San Francisco, CA

`BitTorrent`

## You have 2 identical crystal orbs and a 100 storey tall

building. How do you determine which floor the orbs will shatter at, and what is the minimum number of tests you need to execute?

## Interview Answer

5 Answers

If this is supposed to be a "what's the worst case" sort of question -- Drop first at the 50th floor. If it shatters, work you way up from the first floor. If it does not, drop from the 75th floor. If it shatters, work up from 50th floor. It it does not, drop from the 88th floor. If it shatters, work up from the 75th floor. It it does not, drop from the 94th floor, etc.

You can get it done in about 4-5 tests, I think. Start by dropping one from the 33rd and one from the 66th. If both shatter, it's a floor below 33. If 33 is intact and 66 shatters, then it's a floor between 33 and 66. If both remain intact, then you'll check floors above 66. For your next test, divide the range you need to investigate into 3. So, for example, if the 66th breaks and the 33rd does not, then you have 33 possible floors. 33 divided by 3 is 11, so go up 11 floors from 33 and down eleven floors from 66 and drop them. Same idea as last time- you're narrowing it down to 1/3rd of all of the possible floors. You'll know the correct floor at which they will break when the number of possible floors is exactly 1 percent of the number of original floors (in other words, when there is only 1 floor out of 100 that could be the lowest shattering floor). Since each test reduces the possible floors by 66% (leaving 1/3 of the previous floors remaining), you'll have one floor left when (1/3)^n = .01, where n is the number of trials. This occurs at log base 1/3 of .01, which wolfram alpha says is 4.19, so it would take at least 5 trials to get this narrowed down to a single floor.

The problem here is that you only have two crystal orbs. If you had closer to 100, a strategy of beginning on the 50th floor and working up or down would work great. Unfortunately, if it breaks at 50, and then breaks at 25, you're out of orbs. You'll have to be cautious. You can start on 50. If it shatters at 50, though, you'll have to go to the second floor (assuming you can simply place the orb on the ground when on the first floor) and work your way up one at a time--because you've only got one orb left. If it doesn't shatter at 50, go to 75. If it shatters at 75, you have to go to 51 and work up one at a time, as, again, you only have one orb left. If it doesn't shatter at 75, go to 88, etc. The minimum number of tests is 2. Shatters at 50, shatters at 2.

If you only have two orbs, use one to test and the second to confirm. starting from the bottom make your way to the top on steps of 3 floors. This is slightly better than n/3 (n/3 + 3) where n is 100 in this problem. For example: let's say the orbs break on the 48 floor. On increments of 3 you get to the 48 floor in 16 steps. Once the orb breaks go to floors down and throw the second orb. You know that the orb didn't break on the 45th floor. If it breaks on the 48th floor, it won't break on the 46th, or the 47th floor, when you throw the orb from the 48th floor again it will be confirmed. let's say the orbs break on the 49th floor. you know 48th checks, 51st will break the 1st floor. go to 49th if it breaks you can confirm 49th is the limit. let's say they break on the 50th floor. 48th checks, 51st doesn't. go to 49th, checks, 50 doesn't therefore 50th is the limit.

## Add Answers or Comments

To comment on this, Sign In or Sign Up.

One test. If they shatter, they will shatter at the bottom floor. =)D