Hacker News Reader

Comment by kdheepak | Hacker News Reader

That was a fun puzzle. I have another one that is math puzzle:

> You are given two eggs, and access to a 100-storey tower. Both eggs are identical. The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.

> If an egg breaks when dropped from a floor, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.

> The question is: What strategy should you adopt to minimize the number egg drops it takes to find the solution? (And what is the worst case for the number of drops it will take?)

I wrote up a solution for this (along with a generalized analytical solution) on my blog: https://blog.kdheepak.com/the-egg-tower-puzzle

View on HN

> The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. (emphasis added)

The egg doesn't break when dropped out of the window (i.e., instantaneously). It potentially breaks when it hits the floor after a time delay t. So, the answer is 100 and 0 trials.

ps: This is a joke. Don't take it too seriously.

I'm not too math-y, but this did capture my sense of wonder.

However, it was short lived since now I know it takes "14 drops" maximum, but not the solution - "which floors should I use the 14 drops on though?"

Maybe I'd be intrigued enough to try and follow the math if that was added in :)

First the 14th floor, then the (14 + 13 =) 27th floor, and so on.

I was asked this one in a google phone interview in ~2009. I remember deriving that intervals of 10 floors were optimal in the two-egg 100-story case using some simple calculus and getting that far took me most of the hour. Your solution is super nice, but I hope you don't ask candidates to recreate it :P

That's not optimal though, like the blog says. When doing the first egg, as you get up near the top you've already used up many drops, so the gaps need to get correspondingly smaller.

Maybe that's why I don't work at google :)

Wouldn't one normally just try to convert this to an unambiguous discrete problem, something like:

Given:

(1) the ordered sequence of whole numbers (1, 2, ... , 99, 100) and

(2) an unknown value N that is a member of this sequence,

(3) the following tests (a candidate is a guess at the value of N), and two separate threads to run tests:

(A) if candidate <= N : true & thread continues (another candidate can be checked with that thread)

(B) candidate > N : false & thread terminates (no more candidates can be checked with that thread)

Determine the best strategy for finding N (minimize the number of tests while leaving at least one thread alive)

Determine the worst case for the number of tests needed to find N using this optimal strategy.

Reply on news.ycombinator.com