Hacker News Reader

Comment by patio11 | Hacker News Reader

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.

View on HN

"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:

http://dl.dropbox.com/u/751473/hn.rb

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.

(Argh, asterisks!)

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.

Worst case of 19 drops:

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.

Reply on news.ycombinator.com