Interview questions: Two marbles
This is another question I saw around the place somewhere, attributed to Google. It goes along the following lines…
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.
Effectively, what we have here is a search problem, but we’re limited to making at most two checks above the upper limit. My first though was a binary search but clearly there’s no way to limit the number of checks above the value, so we can’t guarantee we will actually find the correct value.
As far as I can see, the best policy is to use the first marble in a broad first pass to narrow down the possibilities, then use the second to actually find the correct floor within a limited range.
Let’s say we start at the ground, and move up x floors at a time dropping the first marble until we find the first floor at which it breaks (let’s say it’s fu). We then need to use the second marble to search from fu to fu - x (let’s call it fl).
We already know that the marble is safe at fl, So we’ve got to check fl + 1, then fl + 2 and so on until we reach fu - 1 (aka fl + x - 1). On average, we’ll need to perform (x - 1) / 2 checks to find the correct floor with the second marble.
The key question, then, is what value should be used for x. Obviously the value of this is going to vary with the height of the building, which we were told was 100 floors, but to keep things generic, let’s call it h. On average, we’ll need to perform (1/2 * h) / x checks with the first marble, so in total on average we’ll need to perform the following number of checks.
((1/2 * h) / x) + ((x - 1) / 2)
(forgive me for not marking up the equations properly)
or simplifying,
(h / 2x) + (x / 2) - (1 / 2)
What we need is to find the value for x where this expression is a minimum. To get an idea of what we’re looking at, we could substitute in h = 100 and graph this, which gives us the following…
From a glance, it looks very much like we want x = 10, but just for the sake of checking, we can take the derivative and find the zeros (local minima and maxima are where the slope is zero)…
y = (h / 2x) + (x / 2) - (1 / 2)
dy/dx = (-(h / 2) / x^2) + 1 / 2
and since we’re looking for the zeros…
0 = (-(h / 2) / x^2) + 1 / 2
1 / 2 = (h / 2) * x^-2
x^-2 = 1 / h
x^2 = h
x = sqrt(h)
(If we hadn’t already drawn a graph, we’d need to check that this was a in fact a local minima, and also confirm it’s below x = 0 and x = 100, but I’ll skip it for now).
So, for out case of a 100 story building, we should start by going up ten floors at a time until the marble breaks, then walk through the previous nine floors one at a time with the other marble.
I’ve got to say though, that’s a lot more maths than I’ve ever needed in an interview. I’ve got to say it’s quite a cute question though, and requires a decent amount of thought.
Technorati Tags: puzzle, search, google, interview
June 9th, 2007 at 6:31 pm
Your solution is not optimal; you made an unwarranted assumption. With two marbles and a 100 story building, it is possible to find the maximum height from which a marble can be dropped without shattering in a maximum of 14 drops.
I was also asked this question in an interview, and the interviewer told me that I should be able to derive the mathematical formula for the optimal solution. I came up with your solution, but recognized it as non-optimal. It took me about two hours this evening to find the optimal solution, and another hour to prove to my own satisfaction that is is optimal.
Hint: 14 drops are sufficient for buildings of 92 to 105 floors.
June 10th, 2007 at 11:48 am
My first idea (after a couple of beers at a friend’s housewarming last night) is that the size of the broad pass should perhaps vary as we gain more information…
Anyway, thanks…I’ll have a think about it…
January 14th, 2008 at 5:39 am
The reason why it is 14 is because the sum from 1-14 just breaches 100. The intervals don’t have to be constant. The reason why this is so is because after dropping it a certain number of times until it breaks, you need the other marble to go back through the previous interval up towards breakpoint to determine exactly WHERE it breaks. However, the varying interval lengths are a way to compensate for this.
January 14th, 2008 at 5:42 am
Also:
The reason why you initially got 10 is because of your assumption that the interval lengths have to be constant. Say you drop it x number of times until the first marble breaks, going up N floors each time. The number of drops for this = x = 100/N. Say it breaks at floor 100 using interval length 10. Then you use the second marble to go from 90 to 100 each floor until that one breaks. Worst case scenario, you need 10 more drops.
So drops here = 100/N + N, but to find the minimum, you can find the derivative:
-100/N^2 + 1 = 0, N=10, or drops=100/10 + 10 = 20
Of course, as previously stated, it’s under the assumption that you can’t change the interval lengths. If you can, you’ll find it to be 14.
February 23rd, 2008 at 5:09 am
just curious, why would the second marble needs to be dropped the remainder of the 9 floors. why can’t we go to the middle which would reduce the search to 3, so the maximum tries to determine would be 13.
April 16th, 2008 at 6:34 am
Gandolf - You can’t state the exact floor it would’ve broken on unless you tested the floor immediately below it previously, so you can’t safely jump in the middle with your last marble - if it breaks, you’re no longer able to do more testing, and you still have a range of floors to search.