Two marbles

Question

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

Answer 1

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.

Answer 2

I'm personally not very big a fan of such puzzle questions, I prefer actual programming exercises in interviews.

That said, first it would depend on if I can tell if they are broken or not from the floor I am dropping them at. I will presume I can.

I would go up to the second floor, drop the first marble. If it broke I would try the first floor. If that broke I would know it was no floor.

If the first didn't break, I would go to the 4th floor and drop from there. If that broke, I would go back down and get the other marble, then drop at the 3rd floor, breaking or not I would know which is the limit.

If neither broke, I would go get both, and do the same process, this time starting at the 6th floor.

This way, I can skip every other floor until I get a marble that breaks.

This would be optimized for if the marble breaks early... I suppose there is probably an optimal amount of floors I could skip to get the most for each skip... but then if one breaks, I would have to check each floor individually from the first floor above the last known floor... which of course would be a pain if I skipped too many floors (sorry, not going to figure out the optimal solution right now).

Ideally, I would want a whole bag of marbles, then I could use a binary search algorithm and divide the number of floors in half with each drop... but then, that wasn't the question, was it?

Answer 3

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.

Answer 4

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

Answer 5

Drop the first marble from the 3rd floor. If it breaks, you know it's floor 1 or 2, so drop the other marble from floor 2. If it doesn't break you've found that floor 2 is the highest. If it does break, you've found that floor 1 is the highest. 2 drops.

If dropping from the 3rd floor does not break the marble, drop from floor 6. If it breaks, you know floor 4 or 5 is the highest. Drop the second marble from floor 5. If it doesn't break you've found that 5 is the highest. If it does, floor 4 is the highest. 4 drops.

Continue.

3 floors - maximum of 2 drops

6 floors - maximum of 4 drops

9 floors - maximum of 6 drops

12 floors - maximum of 8 drops

etc.

3x floors - maximum of 2x drops

So for a 99 floor building you'd have a maximum of 66 drops. And that is the maximum. You'd likely have less drops than that. Oh, and 66 is the maximum for a 100 story building too. You'd only need 66 drops if the break floor was floor 98 or 97. If the break floor was 100 you'd use 34 drops.

Even though you said it didn't matter, this would probably require the least amount of walking and you don't have to know how high the building is.

Part of the problem is how you define efficiency. Is it more "efficient" to always have a solution in less than x drops, or is it it more efficient to have a good chance at having a solution in y drops where y < x with the caveat that you could have more than x drops?

Answer 6

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.

Answer 7

I think it is firmly established that with two marbles the only method is to divide the floors up into segments and then drop a marble from the top floor of each segment, and once you get a smash work your way up from the bottom of the segment.

With that established it is a matter of finding what segment size results in the least number of drops (assuming that is the metric for efficiency). If n represents the segment size then 100/n is the number of segments and hence the total number of top floors in all segments. n-1 is the number of floors excluding the top floor in each segment that we need to test when a top floor break occurs. So for each value of n the worst case scenario for drops is:

(100/n)+(n-1)

All we have to do now is plug in the values for each segment size from 1 to 100. Doing so reveals that with a value of n=10 we get the minimum number drops, which is 19.

Answer 8

First thing I would do is use the dead simple algorithm that starts at floor 1 drops the marble one floor at a time until it reaches 100 or the marble breaks.

Then I'd ask why should I spend time optimizing it until somone can show that it will be a problem. Too many times people get all hung up on finding the perfect complicated algorithm when a much simpler one will solve the problem. In other words don't optimize things until it's needed.

This might be trick question to see if you are one of those people who can make a mountain out of a mole hill.