40

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
Improve this question
5
  • 1
    It's probably better not to assume the correct floor is randomly distributed, and instead just come up with a solution to minimize the worst case.
    – David L
    Commented Sep 16, 2008 at 16:43
  • 6
    This has a pretty big "aha!" factor for someone who hasn't studied math. Questions with "aha!" factor are exceptionally bad for interviews.
    – Brad Wilson
    Commented Sep 25, 2008 at 15:34
  • 1
    @Brad Wilson: this entirely depends on the interview... it's a great question to check logical thinking and math solving skills.
    – Karoly Horvath
    Commented Oct 21, 2012 at 17:10
  • The question title doesn't state clearly: do we need to find the max floor from which we can drop the marble w/o breaking it or, as the answer suggests, the min number of attempts to arrive at that floor...?!
    – Sayan
    Commented Oct 22, 2012 at 11:59
  • You need an algorithm for finding the floor efficiently (which should lead you to both the maximum number of drops required for your approach, and a set of steps for how to do it).
    – Matt Sheppard
    Commented Oct 23, 2012 at 21:41

10 Answers 10

Reset to default
55

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

Improve this answer
5
  • 3
    can you please explain the the reason for the equation n+(n-1)+(n-2)+...1 <=100?
    – Geek
    Commented Apr 22, 2015 at 7:07
  • 1
    @Geek say n is the worst outcome allowed. So you try and make that worst case the worst for each of a number of segments. To maintain that maximum worst case for each segment tested, you have to use 1 less drop for each segment tested. Test the first segment at that value of n, if it breaks you then test from 1 up to n-1. So your final max drops is 1 + (n-1) = n. If it didn't break at n, but at 2n, then you've already done 1 drop at n, so to stick to the worst case of n drops, you've only got n-1 remaining. At 3n, you've already done 2 drops so to stick to worst case have n-2 drops remaining.
    – Davos
    Commented Aug 8, 2017 at 15:34
  • Logically the marble hits the ground harder the higher you go up, so you start low and work your way up. So the segments start low and go up as well. The more segments you test, the fewer drops remaining, so the higher segments are forced to be smaller and smaller. The bottom segment is the largest, equal to n. Each step up is one less, because you are working your way up.
    – Davos
    Commented Aug 8, 2017 at 15:38
  • The goal then is to minimize n. You can run through this manually by charting the results of each of these: n=100 , n+(n-1)=100 , n+(n-1)+(n-2)=100 , n+(n-1)+(n-2)+(n-3)=100 ,etc etc. Rearrange each of those equations to n=100 , n=101/2, n=103/3, n=106/4 . Keep going, the value of n will get smaller, until it reaches a minimum, and then will go higher after that. That minimum solution is the optimal. The solution is 13.64, but there is no 13.64 floor, so 14. The number of segments required is the same as the number of terms to find the minimum, e.g. n+(n-1) is 2 terms...
    – Davos
    Commented Aug 8, 2017 at 15:46
  • 2
    I can't edit that first comment. This part is wrong: "if it didn't break at n, but at 2n" . Sorry 2n is not right, it should be "but at n+(n-1)"
    – Davos
    Commented Aug 8, 2017 at 15:49
16

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:

Improve this answer
5
  • can you please comment on the rationale behind the equation in step 5 above?
    – Geek
    Commented Apr 22, 2015 at 7:30
  • 3
    @Geek You just need to cover all the 100 range with decremental ranges. We wanted to make it balanced so the jumps are in floors: 14, 27,39, 50, 60, 69, 77, 84, 90, 95. Every time is incremented one floor less. This way even if we drop the first one 10 times we only need 4 drops more. 10 +4 = 14 just like if it breaks in the first floor.
    – borjab
    Commented Aug 27, 2015 at 11:13
  • "For that to be the case, since each drop of Marble1 takes one more step, Marble2 is allowed one fewer step." . I don't understand this part. Could you please explain ?
    – Dinaiz
    Commented Jan 8, 2017 at 15:14
  • @Dinaiz Totaldrops = Marble1Drops + Marble2Drops. If you want the value of TotalDrops to stay the same (worst case), then as Marble1Drops increases, Marble2Drops has to decrease. e.g. Assume TotalDrops = 10. If Marble1Drops = 1 then Marble2Drops = 9. If Marble1Drops =2, then Marble2Drops = 8 and so on.
    – Davos
    Commented Aug 8, 2017 at 15:56
  • @Geek You can start by assuming the worst x=100, i.e. you're going to do 100 drops. It couldn't be worse than 100, because there's only 100 floors to test. The next step is to try and split the space in half. i.e. drop one at roughly half way. So that is sortof like 2x=100, but not quite. It's really x+(x-1)=100, the second segment is x-1 because the floors are two segments which will be tested bottom-up. If the marble is unbroken for the first segment, you've used 1 drop, so have one less for the upper segment. The more segments, the more drops used up. They get smaller as you go up.
    – Davos
    Commented Aug 8, 2017 at 16:14
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.

Improve this answer
2

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.

Improve this answer
2

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.

Improve this answer
1

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?

Improve this answer
0
1

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?

Improve this answer
1

If you want a general solution which will give you the result for N floors (in your case N=100) then you can just solve quadratic equation $x^2+x-2\cdot(N-1)=0$ and the result is a ceiling of a positive root.

Which is:

$$f(N)=ceiling\bigg(\frac{-1+\sqrt{1+4\cdot2\cdot(N-1))}}{2}\bigg)$$

Improve this answer
-1

This can be done better with just 7 marbles.

So following the voted answer, say marble breaks at at least 49th floor.

  1. 50th floor -> breaks (answer is between 1 to 50 inclusive)
  2. 25th floor -> doesn't break (26 to 50)
  3. 37th floor -> doesn't break (38 to 50)
  4. 43rd floor -> doesn't break (44 to 50)
  5. 46th floor -> doesn't break (47 to 50)
  6. 48th floor -> doesn't break (49 or 50)
  7. 49th floor -> breaks (49th, this step is actually needed because it might have been the min floor for marble to break is at 50th)

This can be imagined as doing a binary search in a sorted set for some k, where we half the solution space with each try. For 100 floors, we need log2 100 = 6.644 (7 tries). With 7 marbles we can be sure which is the minimum floor that marble will break up to 128 storeys.

Improve this answer
2
  • 1
    That would be a very different problem.
    – borjab
    Commented Aug 27, 2015 at 11:15
  • 1
    The problem with you answer is that it will NOT guarantee that if egg breaks from say 43rd floor, then you will not know whether the threshold floor was 38th,39th... 42nd. Also, see this
    – ABcDexter
    Commented Jun 25, 2016 at 9:07
-3

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.

Improve this answer
1
  • 7
    Even if you want to use a dead simple algorithm, at least make use of all the information given in the question. You have got 2 marbles but still using only 1. Don't let the other marble sit and cry "I came to this world to make a difference and you are wasting my existence :("
    – Vikram Singh
    Commented Dec 20, 2012 at 5:55

Not the answer you're looking for? Browse other questions tagged or ask your own question.