Someone told about this phone interview question.
If you drop a ball from a high enough floor of a 100-story building, it will break into pieces when it hits the ground. You have two balls to test with. How do you determine the lowest floor that is high enough to break a ball with the fewest number of drops?
Subscribe to:
Post Comments (Atom)
23 comments:
You could use a protocol similar to a quicksort. Drop one ball from the 50th floor. If it explodes, start from the first floor repeating the drop, moving up 1 floor at a time until you find the floor from which the ball explodes.
If it doesn't explode on the drop from the 50th floor, repeat the drop from the 75th floor. If it explodes, start from the 50th floor repeating the drop, moving up 1 floor at a time until you find the floor from which the ball explodes.
If it doesn't explode start again with values of 87 and 75. Then 93 and 87, then 96 and 93, then 98 and 96 then 99 and 98. Worst case scenario is that the ball breaks when dropped from the 49th floor, so you will perform 50 tests.
Fifty tests with two balls is twice as good as the worst case scenario with a single ball. Can anyone do better?
Drop a ball from floor 10, 20, 30, until it breaks or you get to 90. Then drop the other ball from the last floor where the ball didn't break (x) until it breaks or you get to floor x + 9. This has a worst case of 18 drops, and corresponds to a radix sort, I think.
My gut says that this is optimal, but I haven't done any analysis on it.
Going by tens was the official solution, but it is not optimal. If nothing else, you can do better after reaching floor 90 with two intact balls. At most it has the best worst case scenario, but I'm not convinced even of that. The problem is more subtle than I thought.
If nothing else, you can do better after reaching floor 90 with two intact balls.
Ah, naturally. If you reach floor 90 with no breaks, drop one ball from 95, etc.
I'm pretty sure that this refinement actually is optimal, though. I suppose a better criterion for "optimal" than "best worst case scenario" would be "least average number of drops", but I can't immediately think of a situation where the former doesn't imply the latter.
Much is implied by that little "etc."
I have an algorithm that works in all cases with fewer than 18 drops.
Hmm. How many drops to find floor 89 using your algorithm?
Floor 89 is identified with 15 drops.
Ah-ha. OK, I have an algorithm that does no worse than the refinement from comment 5 for floors up to 80, and does no worse than 15 drops for floors above that. It does worse in at least one case, but the overall worst case is reduced to at most 17.
Reduced to exactly 17, in fact. Now to repair to the train to work on further refinements.
I can get a best worst case of 16 drops with a couple different (but similar) algorithms. Not sure yet whether either has an advantage as to least average drop count.
A worst case better than 16 is possible.
Are you sure you're not forgetting the two ball limit?
Perhaps it is you who have forgotten that there are two balls to employ. What is your worst case when the critical floor is 50 or below? If it is much lower than your overall worst case, then you are not using the balls as efficiently as possible.
More to the point, how do you choose where to put the first ball? Did you start on floor 10 because (100 floors)^(1/2 balls) = 10? The radix sort depends on the base in which you express the values, which surely should not matter in this problem.
I still get 16, but my solution doesn't feel clean. Regardless, I'm dubious of the sub-16 best worst case algorithm's existence.
It's subtle.
For the record, let's say that an algorithm will be judged first by it's worst case. To break a tie, use the average performance over all 100 cases.
OK, I now have a system with a worst case of 14 drops. Pretty simple and clean. Not that subtle, though.
Might could fiddle it around some in the upper floors to drop the average drop count a little, but haven't bothered yet.
Sounds about where I am. And I can demonstrate that a worst case of 13 is not possible.
My algorithm with a worst case of 14 has an average performance of 10.35. With a tweak I can get it down to 10.33. Are we doing the same thing?
Interestingly enough, my untweaked algorithm has an average drop count of 10.34 and a tweaked value of 10.32. I can tweak it two ways, but they both come out with the same average.
I wonder if we're doing the same thing but you're over-counting the drops for floor 100. My values are 11 untweaked and 12 or 13 tweaked, depending on which tweak I use.
I did overcount. With the naive version of the correct algorithm, the eleventh drop of the first ball is from the 99th floor, so no more drops are necessary if the ball doesn't break.
There are many ways to tweak the worst case 14 algorithm. My best average result is 10.30.
I will read your responses later today, I came in a hurry to post the answer, if I am posting the same answer as you did before sorry for that.
We are trying the find the floor #X.
Suppose we have only 1 ball. We have no chance but to try every floor starting from 1.
For 2 ball case, 1 ball case shows when we break our first ball, we have no chance but start from a floor and try each one by incrementing floor number. So we have to find a good starting point before wasting our first ball.
I am assuming the probability of the ball breaking on a given floor is equal. I mean the selected floor may be the 80th or the 20th floor equally.
Say we have n floors. We split the floors to k parts. The floor number we are looking for can be in any k part with equal probability. So in average case number of drops will be [1st ball drop count] + [2nd ball drop count] = k/2 + (n/k)/2
On average we break the first ball with k/2 drops. After finding the which part the X is in we start from the parts lowest floor and increase the floor by 1 untill ball breaks (and that gives (n/k)/2 where n/k is the number of floors in a part).
If we take the derivative and equal to zero to find the minimum of f(k) = k/2 + n/2k we get k = sqrt(n)
So, the strategy is: Split floors into sqrt(n) parts, start dropping ball from each parts end floor. When the ball breaks go to parts beginning start dropping ball from each floor until it breaks.
I hope I was clear, it is still hard for me to tell something in English, I hope I am doing good.
Very clear, yes. And your approach to the general case is interesting.
I think the flaw in your analysis, though, is that you assume all the parts must have an equal number of floors. My original answer was based on exactly that assumption, plus an instinctive reaction that the number of divisions should be sqrt(n). However, that approach gives a non-optimal answer for both the worst case and average number of drops.
I feel inspired to work on the general case now.
Now I've read all the answers, I see that there are more optimal solutions, I wonder what they are... I will think about it.
Post a Comment