"You have 2 supposedly unbreakable light bulbs and a 100-floor building. Using fewest possible drops, determine how much of an impact this type of light bulb can withstand. (i.e. it can withstand a drop from 17th floor, but breaks from the 18th).
Note that the ever-popular binary search will give you a worst case of 50 drops. You should be able to do it with under 20."
Maybe there's something I don't understand, because my reaction to that question was "lolwut?"
In that scenario, with a binary search you drop from the 50th, 25th, 13th, 19th, 16th, 17th and 18th floors.
By my back of the postage stamp calculations you need to do (log N) + 1 drops...
My question: how did they get a number of 50 for binary search??? Is it because you're limited to 2 failures? And by 'binary search' they mean something like start at floor 2 and drop, if it is still intact go to floor 4 and then drop it, if it breaks you don't know about floor 3, so you have to use the remaining one to check that. That's not binary search, that's linear.
To do it in 20 or less drops you could drop it from the 20th floor, and if it smashes, go to floor 1 and start going up in increments of 1. Otherwise go to floor 39 and drop it (etc). But that makes me think it is not the best for that starting number, we can do better. Just pull out the good old (n^2 + n)/2 formula again and the first one in that progression that ticks over the 100 threshold is 14. So we drop it at floor 14 first, if it breaks then start from floor 1 and go up. Otherwise go up 13 floors and repeat...
Our major floor increments are 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99.
I'm not sure if there is a better solution, if you have one, feel free to chip in. :D
Suppose that bulbs have a tolerance of 8.5. Doing a naive binary search causes you to drop at floor 50, breaking a bulb, and then at floor 25, breaking your second bulb. You have no more bulbs, and cannot discriminate between 25 possible values for the tolerance, so your naive strategy was not a good idea.
The binary search strategy which works is to binary search with the first bulb until you break it, then exhaustively search with the second bulb starting from the lowest possible tolerance and increasing until it breaks, thus identifying the precise breaking point with the minimum number of drops. This has a worse case performance of 50 drops, for when the bulb had a tolerance of 49.5: one drop with the first bulb, bulb breaks, 49 drops with the second bulb. (1 + 48 = 49 if we assume that it can't break on the first floor.)
Your solution is very good, but I do not believe it to be optimal. I am working on a better one.
"Your solution is very good, but I do not believe it to be optimal. I am working on a better one."
Very well sirrah, I shall consider myself slapped in the face with the object with five extrusions that is topologically identical to a plane. Your challenge is accepted. :D Duelling algorithms at dawn it is. I keenly await your opening salvo.
Coded both our algorithms. I win by a nose (more visible at larger building sizes -- 1k floors, etc.) Code quality is an abomination, please excuse exploratory programming:
Gist of my approach: dynamically recalculate number of steps to go with each jump we take, using the same approach that you do (find smallest k such that k(k + 1) / 2 > n), rather than assuming it decreases monotonically. This has superior performance around some boundary conditions.
Instructions for running script:
ruby hn.rb patio11 debug 100
ruby hn.rb stormy debug 100
Debug on or off as desired, 100 is size of building.
Then, leave off debug flags, and diff the outputs.
Do you mean "incrementally by 1 each iteration" where you wrote "monotontically", in your reference to Stormbringer's algorithm?
Mathematically, I do not see how any solution could beat Stormbringer's, by considering the cases where tolerance = k+0.5 and tolerance = ((kk +k)/2+0.5, which shows that the set of tolerances for a building of height > (kk+k)/2 requires >= k+1 drops to validate. But I have not been quite formal in my analysis.
Neither of these proposals is optimal; patio11's proposal takes linear time in the worst case.
IIRC, the correct solution to this is in sqrt(N) time; for a 100-floor building, you drop at floors 10, 20, 30, 40, 50, 60, 70, 80, 90, and 100, in that order. In general, this is sqrt(N) floors, spaced sqrt(N) floors apart.
The bulb will break at floor sqrt(N) * X [10X in this example]. Now, drop the bulb from the approximately sqrt(N) [10] floors between floor sqrt(N) * (X-1) [10 * (X-1)] and sqrt(N)* X - 1 [10 * X - 1], inclusive. When it breaks, you have the exact tolerance rounded down to the nearest floor, and you've done it with at worst 2 * sqrt(N) drops.
By the way, this is a great example of a dumb interview question; it's not particularly obvious that there is a solution in sqrt(N) worst case time, but once you're told that there is one (and, perhaps, that binary search + linear search is linear search in the worst case), it's not too difficult to get it in sqrt(N).
Also, note that average case running time analysis is meaningless if you don't have a distribution for the input; simply assuming that the tolerance is distributed uniformly at random from 1 to 100 just because you have a 100-floor building makes little sense.
For the record, Stormbringer's solution is slightly less than sqrt(n) in the worst case. floor((k * k + k)/2) = n; solve for k to get approximately sqrt(2 * n)
The (Sqrt(n) * 2)-1 solution is less efficient, but only by a roughly constant factor of approximately sqrt(2). (14 vs 19, when n=100)
Patio11's binary+linear algorithm is almost certainly the inefficient solution that the blogger hinted at.
Patio11 claims to have coded an even more efficient solution, but has not explained it.
I for one suspect his supposedly more efficient solution has a bug, but I have not inspected or tested his code.
Drop bulb a every ten floors starting with floor ten, extending to floor 100.
When bulb a breaks, start with bulb b. Drop bulb b starting from 9 floors below the floor that bulb b breaks, and extending to the floor directly below the one the b broke on.
You can probably optimize this a bit by adjusting how many floors you jump with for bulb a, but 10 seems like an easy number.
Bulb 1: drop from the Xth floor, then the 2Xth floor, 3Xth floor, and so on until you pass 100. The bulb will survive a drop from the AXth floor, but break on the (A+1)Xth floor. For X = 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 the worst case number of drops is floor(100/X) = 50, 33, 25, 20, 16, 14, 12, 11, 10, 9, 8, 7, 7, 6, 6. This narrows the break point to a range of values between AX+0.5 and (A+1)X - 0.5, and leaves X-2 floors whose result must be found.
Bulb 2: iterate over the X-2 unknown floors checking them too. Worst case performance is X-2 further tests. Total worst case performance is floor(100/X) + X - 2 = 50, 34, 27, 23, 20, 19, 18, 18, 18, 18, 18, 18, 19, 19, 20.
So pick X = 8, 9, 10, 11, 12 or 13. For example, drop the first bulb from floors 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88 and 96. Worst case scenario is the bulb survives being dropped from floor 88 but breaks when dropped from floor 96. That's 12 drops.
Drop the second bulb from floors 89, 90, 91, 92, 93, 94 and 95. Worst case scenario is the bulb survives being dropped from floor 94 and breaks/survives when dropped from floor 95. That's 6 more drops.
Total is 18 drops.
The problem with this question is that you could just randomly pick 10 and find the right answer without having to do any calculation. Meh.
Ah, I see now though that if the bulb passes at 8 then you have reduced the problem to a 92-storey building so the "step size" upwards should be reduced. You don't even need to do that to get a good answer though. Ridiculous.
For 100 storeys, you drop the first bulb at floors 9, 22, 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99 and 100. If the first bulb breaks, iterate over the gap that's left over. Worst case is 14 drops total.
"The problem with this question is that you could just randomly pick 10 and find the right answer without having to do any calculation. Meh."
True, but consider it as a test of intuition. Why pick 10? Because it is √100 (or maybe because it is log(100)). The intuitive approach doesn't get you the perfect answer, but it gets you into the ballpark.
Having picked 10, we might then realise that the 'worst case' changes and gets worse the higher up the building we go, so then intuition might say that we need to tweak the step size somehow to get down the size of the worst case. Or we might think that that step size works fine for a 100 storey building, but what about a 10,000 storey building? Our intuition is telling us the algorithm can still be refined.
But then maybe we look at what you wrote and think to ourselves, 'what if the best sequence isn't linear, but is based off the fibonacci sequence instead?'. And then maybe we tootle around a bit with our theoretical fibonacci based algorithm. Maybe we decide it isn't quite as good because it has a worse worse case. But then we might have another intuition, that perhaps there are other ways of measuring which is the better algorithm. So lets say we measure the average, and lo and behold the theoretical fibonacci algorithm has a better average, but a worse worst case. We might be confused at that point as to which one was 'better', because they are each better by different measures. But now we can put it into a broader context and reason about which one to use in which situation.
Moreover recognising that this sort of problem can be decomposed into smaller chunks is not a bad thing. Having a good intuition towards decomposition is an important part of design.
Yes, it's because it's limited to two failures. If you drop the first bulb at floor 50 and it breaks, you have only one bulb left, so you MUST not break it until you have limited the possible range to 1, so you have to just incrementally test 1, 2, 3, 4, etc. If you went straight to floor 25 and it broke, all you know is 0 < x < 25, and you have no bulbs left.
Yes, it's because you're limited to 2 failures, and yes, "binary search" is a dumb way to describe it since you can't actually do a binary search in that situation.
Working in increments of 20 floors gives you a worst case of more than 20 drops. 20, 40, 60, 80, 100 (bang), 81, 82, ..., 99 (bang): that's 24 drops.
Your other solution is better, and indeed dropping first at floor 14 is one of the 6 initial choices that minimize the worst-case number of drops. If, subject to minimizing the worst-case number, you also want to optimize the average case (assuming all possibilities are initially equally likely) then doing floor 14 first is optimal.
Even if the lightbulbs are breakable I think you would need a maximum of (2√n)-1 drops - i.e. go up in increments of √n then when it breaks work forward from the previous drop.
It's a fairly cool recursive problem. Let N be the number of floors.
OneBulb(N) = N. With one bulb and 100 floors, you have no choice but to drop the bulb 100 times, once for each floor.
With two bulbs, a single drop at floor K has two outcomes. If the bulb survives, then you can consider all the floors above K as a separate building, and start again with two bulbs and N - K floors. If the bulb breaks, you can consider all the floors below K as a separate building, and start again with ONE bulb and K - 1 floors. So:
TwoBulbs(N) = min { 1 <= K <= N } ( max(TwoBulbs(N-K), OneBulb(K-1)) ) + 1
Now, the same is true when you go to three bulbs:
ThreeBulbs(N) = min { 1 <= K <= N } ( max(ThreeBulbs(N-K), TwoBulbs(K-1)) ) + 1
And the recursion continues.
I wrote a small Perl script which solves for arbitrary B (number of bulbs) and N (number of floors). For B = 3, N = 100, you can do it in a worst case scenario of 9 drops.
3 bulbs. 100 floors.
drops[3][100] = 9 drops.
Drop bulb at floor 8.
Bulb survives: consider floors 9 to 100 as a separate 92-floor building and observe drops[3][92] = 8 drops.
Bulb breaks: consider floors 1 to 7 as a separate 7-floor building and observe drops[2][7] = 4 drops.
I know it's supposed to be purely hypothetical, but I can't help thinking that the bulbs will be more prone to break after being dropped multiple times, and might break before they normally would have under different circumstances.
Maybe there's something I don't understand, because my reaction to that question was "lolwut?"
In that scenario, with a binary search you drop from the 50th, 25th, 13th, 19th, 16th, 17th and 18th floors.
By my back of the postage stamp calculations you need to do (log N) + 1 drops...
My question: how did they get a number of 50 for binary search??? Is it because you're limited to 2 failures? And by 'binary search' they mean something like start at floor 2 and drop, if it is still intact go to floor 4 and then drop it, if it breaks you don't know about floor 3, so you have to use the remaining one to check that. That's not binary search, that's linear.
To do it in 20 or less drops you could drop it from the 20th floor, and if it smashes, go to floor 1 and start going up in increments of 1. Otherwise go to floor 39 and drop it (etc). But that makes me think it is not the best for that starting number, we can do better. Just pull out the good old (n^2 + n)/2 formula again and the first one in that progression that ticks over the 100 threshold is 14. So we drop it at floor 14 first, if it breaks then start from floor 1 and go up. Otherwise go up 13 floors and repeat...
Our major floor increments are 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99.
I'm not sure if there is a better solution, if you have one, feel free to chip in. :D