BitTorrent Interview Question: You have 2 identical crystal ... | Glassdoor

Interview Question

QA Automation Engineer Interview San Francisco, CA

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?
brain teaser, trick question

Interview Answer

5 Answers


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

Mats Svensson on Aug 3, 2013

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.

Jason D on Aug 6, 2013

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.

Jordan on Sep 2, 2013

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.

Dave on Oct 23, 2014

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.

Fabian on Nov 20, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.