techInterview Discussion

Answers to technical interview questions. A part of TechInterview.org

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

Locate the floor

Not sure if it's an old question. But here it goes anyway: Thare 100 floors in a building. If you drop a glass ball from a floor down to the ground, it may or may not break. There's this threshold floor where dropping a ball from this floor or the above breaks the ball but dropping a ball from any floor below it won't. Now you are given only two glass balls to locate the threshold floor. How do you find it quickly?
Ray Send private email
Wednesday, February 01, 2006
 
 
I will start with the first floor and try dropping a ball. If it is not the threshold floor, the ball wont break and so I will move to next floor. So if the ball breaks at nth floor, n-1 floor is the threshold floor.
Neeraj Agrawal Send private email
Wednesday, February 01, 2006
 
 
This has become a classic.

the answer, if i recall correctly, is 14.
Safe Driver. Send private email
Wednesday, February 01, 2006
 
 
Are you allowed to throw again a ball if it did not break? If yes, the answer will be quite different, each ball not broken will reduce the search range by a ratio. After the ball breaks, you have to go floor by floor... So the best ratio will minimize the sum of the two over all possible thresholds.
Radu Cornea Send private email
Wednesday, February 01, 2006
 
 
Yes, Radu Cornea, you are allowed to rethrow the ball if it's not broken. You are on the right track. Actually it's not much a programming problem. More like a math puzzle. I was asked this in an IT interview so I brought it here.
Ray Send private email
Wednesday, February 01, 2006
 
 
It's a classic.  I remember being asked this in an iterview more than a decade ago, and it was quite well known back then.

The "standard" answer for n floors is to first try floor sqrt(n), then 2sqrt(n), then 3sqrt(n), etc., until the first ball breaks (or you reach the nth floor).  Supposing it breaks on floor (i+1)*sqrt(n), drop the second ball successively from floors i*sqrt(n)+1, i*sqrt(n)+2, etc., until it breaks.  This way you are guaranteed at most sqrt(n) trials with the first ball, and at most sqrt(n) trials with the second, for a total of at most 2sqrt(n).

To find the optimal solution, it is more convenient to view the problem backwards, i.e., given k, what is the maximum number of floors n for which you can guarantee an answer in at most k trials?  Clearly, the first floor you try may not be higher than k (since the first ball might break on the first trial, and you will have only k-1 trials left).  Also, you can obviously gain nothing from making the first trial on a lower floor, so the first trial should be on floor k.  Supposing the ball didn't break in the first trial, you are left with k-1 trials and two balls, so the next trial should be on floor k+(k-1).  Continuing in this manner, we see that the sequence of trials for the first ball must be
k, k+(k-1), k+(k-1)+(k-2), ..., k+(k-1)+...+2+1,
so the maximum number of floors is
n = k+(k-1)+...+2+1 = k(k+1)/2.

Turning back to the original question (given n, what is k?), we see that
k = ceil(-1+sqrt(1+8n))/2)
which is approximately sqrt(2n) --- an improvement by a factor of sqrt(2) over the standard solution.  (Indeed, for n=100, we get k=14.)

Finally, the above reasoning generalizes easily to three balls or more.
A.F.
Thursday, February 02, 2006
 
 
Great explanation, A.F, wery well organized. During the interview the guy only mentioned the sqrt(n) solution and didn't go the distance as you. Now I could see the clear picture of the problem. Appreciate it!!
Ray Send private email
Thursday, February 02, 2006
 
 
AF your answer is not optimize. Its 14 in your case it can go as far as 20.

think on terms like drop on 14
then 14 + 13 = 27
then 39 and so on

but the better way is to work from end like drop on 100 then 99 97 94
Saurabh Sharma Send private email
Friday, February 24, 2006
 
 
Saurabh, could you please explain your claim better?  I don't understand what you are trying to say.  Are you suggesting that for n=100, you can do with less than 14 trials (in the worst case)?  If so, what is the sequence of trials you are suggesting?
A.F.
Tuesday, March 07, 2006
 
 
the answer is 7 trials at the max its as simple as binary search first go to  the 50th floor if it breaks then go to 25th floor like wise just keep going to the previous floor no/2 at last u will reach the floor in maximum 7 trials whatever be the floor no.
its simple binary search try for any floor no buddy.
Abhishek Anand Send private email
Monday, March 13, 2006
 
 
Abhishek, did you notice the fact that you only have two balls to work with?
A.F.
Tuesday, March 14, 2006
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz