A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor
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?
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.
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.
Thursday, February 02, 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?
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, did you notice the fact that you only have two balls to work with?
Tuesday, March 14, 2006
This topic is archived. No further replies will be accepted.Other recent topics
Powered by FogBugz