Two marbles and a 100 story building

One of those classic programming interview questions...

You are given two marbles, and told that they will break when dropped from some certain height (and presumably suffer no damage if dropped from below that height). You’re then taken to a 100 story building (presumably higher than the certain height), and asked to find the highest floor your can drop a marble from without breaking it as efficiently as possible.

Extra info

• You must find the correct floor (not a possible range)
• The marbles are both guaranteed to break at the same floor
• Assume it takes zero time for you to change floors - only the number of marble drops counts
• Assume the correct floor is randomly distributed in the building

The interesting thing here is how you can do it in the least amount of drops possible. Going to the 50th floor and dropping the first would be disastrous if the breaking floor is the 49th, resulting in us having to do 50 drops. We should drop the first marble at floor n, where n is the max amount of drops required. If the marble breaks at floor n, we may have to make n-1 drops after that. If the marble doesn't break we go up to floor 2n-1 and if it breaks here we have to drop the second marble n-2 times in the worst case. We continue like this up to the 100th floor and try to break it at 3n-2, 4n-3....
and n+(n-1)+(n-2)+...1 <=100
n=14 Is the maximum drops required

This problem is covered in Problem 6.5 from Book "Cracking the Coding Interview (5th)", with solutions summarized as follows:

Observation:

Regardless of how we drop Marble1, Marble2 must do a linear search. Eg, if the Marble1 breaks between floor 10 and 15, we have to check every floor in between with the Marble2

The Approach:

A First Try: Suppose we drop an Marble from the 10th floor, then the 20th, …

• In the first Marble breaks on the first drop (Floor 10), then we have at most 10 drops total.
• If the first Marble breaks on the last drop (Floor 100), then we have at most 19 drops total (floors 1 through 100, then 91 through 99).
• That’s pretty good, but all we’re considered about is the absolute worst case. We should do some “load balancing” to make those two cases more even.

Goal: Create a system for dropping Marble1 so that the most drops required is consistent, whether Marble1 breaks on the first drop or the last drop.

1. A perfectly load balanced system would be one in which Drops of Marble1 + Drops of Marble2 is always the same, regardless of where Marble1 broke.
2. For that to be the case, since each drop of Marble1 takes one more step, Marble2 is allowed one fewer step.
3. We must, therefore, reduce the number of steps potentially required by Marble2 by one drop each time. For example, if Marble1 is dropped on Floor 20 and then Floor 30, Marble2 is potentially required to take 9 steps. When we drop Marble1 again, we must reduce potential Marble2 steps to only 8. eg, we must drop Marble1 at floor 39.
4. We know, therefore, Marble1 must start at Floor X, then go up by X-1 floors, then X-2, …, until it gets to 100.
5. Solve for X+(X-1)+(X-2)+…+1 = 100. X(X+1)/2 = 100 -> X = 14

We go to Floor 14, then 27, then 39, … This takes 14 steps maximum.

Code & Extension:

• For code implementation, you can check out here.

• For the extension to N marbles, M floors, check out Chapter 12: The puzzle of eggs and floors .

They each break when dropped from the same height, or are they different?

If they're the same, I go to the 50th floor and drop the first marble. If it doesn't break, I go to the 75th floor and do the same, as long as it keeps not breaking I keep going up by 50% of what's left. When it does break, I go back to one higher than where I was previously (so if it broke at the 75th floor I go back to the 51st floor) and drop the second marble and move up a floor at a time until it breaks, at which point I know the highest floor I can drop from with no marble breakage.

Probably not the best answer, I'm curious to see how others answer.

I think the real question is how accurate do you want the answer. Because your efficiency is going to really depend on that.

I'm going to agree with Justin if you want 100% accuracy on the marbles then once the first marble breaks your going to have to go up 1 floor at a time from the last known "good" floor until you find out which floor is the "winner." Maybe even throw in some statistics and start at the 25th floor instead of the 50th floor so that you're worst case scenario would be 24 instead of 49.

If you're answer can be plus or minus a floor or two then there could be some optimizations.

Secondly, does walking up/down the stairs count against your efficiency? In that case always drop both marbles and pick up both marbles on every up/down trip.

Drop the first marble at floor 10, 20, 30, etc. until it breaks then jump back to the last known good floor and start dropping marbles from there one floor at a time. Worst case is 99 being the Magic Floor and you can always find it in 19 drops or less.