The Two Egg Problem • Hacker News Board

Re: The Two Egg Problem

#31

Post by ww520 » Sat, Jul 21, 2012, 5:18 PM UTC

I would hate it to do it in an interview setting since the question didn't state the goal of finding the worst case scenario. It's like mind reading. I did solve it once during lunch with colleagues when we asked each other puzzles, which was fun.

Is people ok with posting the solution here? Or want to try out some more?

Hint: square root.

Re: The Two Egg Problem

#32

Post by numlocked » Sat, Jul 21, 2012, 5:26 PM UTC

tomp wrote: post #25

numlocked wrote: post #20

I was asked this question in a google interview earlier this year. Neither I nor the interviewer got past the "every 10 floors" approach (though I did make it through that round of interviews!). Interesting to see there was more meat on that bone.

I think that "every 10 floors" approach is optimal for average case. Basically, E(number of drops) = E(number of drops for 1st egg) + E(number of drops for 2nd egg) . We know that E(number of drops for 2nd egg) = 1/2 the difference between two drops of the 1st egg , and E(number of drops of 1st egg) = 1/2 the number of intervals , and 100 = the number of intervals × the difference . So, we're minimizing x + y , knowi…

Actually there's a slight optimization available. Why ten floors? Because basically what we are doing is establishing a most significant digit - the tens place, then the ones place. This works because 100 is a square number (10*10). But what if there were 64 floors? Then, to do the same thing (but in base 8), we'd drop every 8 floors. We can account for this as we drop by treating all floors above as a fresh tower and rounding to the nearest square number: Drop on floor 10 (90 floors remain - 81 is closest square, so now only go up 9 floors), drop on 19 (81 floors remain, go up 9 again), drop on 28 (72 floors remain, 64 is closest square, go up 8), etc, etc.

Re: The Two Egg Problem

#33

Post by skybrian » Sat, Jul 21, 2012, 5:43 PM UTC

misnome wrote: post #3

dsr_ wrote: post #2

The blog author is very smart. However, he is not very clever. From my experience in the real world, I know that an unprotected egg will smash when dropped from one story, guaranteed. No need to go up 14 or 27 or even two stories. (I also know that it is possible to devise protective enclosures to keep an egg from breaking when dropped from 6 stories. The Society of Women Engineers often sponsors competitions. Been t…

Yeah. I dropped an egg from the kitchen counter and it broke. Ergo, first floor it would break. Except of course, the article doesn't mention what the landing surface is, or whether it is what we think of as an egg, or some hypothetical super-egg. This would seem to be discounted by the "There are no tricks, gotchas or other devious ruses" clause, however. If the point of the article is to make it purely a mathematic…

I think it's a fun problem and the main reason I wouldn't ask it is that it's probably on the banned interview questions list by now (for being too well-known).

An interview isn't a written exam. You don't lose points for bringing up real-world considerations - quite the contrary! But the interviewer might ask you to solve the math problem anyway (perhaps by modifying the question a bit, on the fly).

Re: The Two Egg Problem

#34

Post by jonsen » Sat, Jul 21, 2012, 5:45 PM UTC

And the next question:

What strategy should you adopt to minimize the number of steps it takes you up and down the stairs to find the solution?

Re: The Two Egg Problem

#35

Post by JackC » Sat, Jul 21, 2012, 5:47 PM UTC

dsr_ wrote: post #2

The blog author is very smart. However, he is not very clever. From my experience in the real world, I know that an unprotected egg will smash when dropped from one story, guaranteed. No need to go up 14 or 27 or even two stories. (I also know that it is possible to devise protective enclosures to keep an egg from breaking when dropped from 6 stories. The Society of Women Engineers often sponsors competitions. Been t…

I wonder if it would avoid this kind of objection (which always comes up in logic puzzles) if problems was first stated in mathematical terms, and then analogized to a real world scenario. Something like ...

Assume two sets of integers (1..n) and (n+1..100), where 1 If it helps, you can analogize this problem to dropping two fragile objects out of a 100-story building or something. Just don't forget the failure mode of "clever".

Re: The Two Egg Problem

#36

Post by shasta » Sat, Jul 21, 2012, 6:07 PM UTC

He doesn't write down the math in the general case for the number of floors F(e,d) that you can check with e eggs and d drops:

F(1,d) = d

F(e,d) = sum k>0. F(e-1, d-k)

The sum can given a closed form solution for e > 2, just like for e=1 and e=2.

Another thing is that he directly solves the quadratic, but in fact n^2/2 < n(n+1)/2 < (n+1)^2/2. So taking the square root of twice the number of floors will get you either give you the number of drops you need with 2 eggs, or will under count by 1. It's easy to check which that is.

Re: The Two Egg Problem

#37

Post by tzs » Sat, Jul 21, 2012, 6:19 PM UTC

The author states that the solution is: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100, which takes at most 14 drops.

In fact, that is a solution, not the solution, for this also works, and takes at most 14 drops: 9, 22, 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100.

Re: The Two Egg Problem

#38

Post by psykotic » Sat, Jul 21, 2012, 6:31 PM UTC

jonsen wrote: post #34

And the next question: What strategy should you adopt to minimize the number of steps it takes you up and down the stairs to find the solution?

That version seems too simple to be interesting. Let there be n floors. In the worst case you'll have to walk to the top floor from the ground floor in case the answer happens to be n-1. Therefore you can't do any better than n-1 steps in the worst case, so the obvious strategy of alternating dropping an egg and walking up one floor until you break the egg is optimal and takes n-1 steps and n-1 drops and only requires 1 egg.

Re: The Two Egg Problem

#39

Post by tocomment » Sat, Jul 21, 2012, 6:35 PM UTC

Is binary search until the first egg breaks and then increment by 1 for the second egg the best approach?

Re: The Two Egg Problem

#40

Post by tomerv » Sat, Jul 21, 2012, 6:35 PM UTC

A more generalized version of the problem was posted as a practice question in Google's codejam contest:

http://code.google.com/codejam/contest/32003/dashboard#s=p2

I suggest solving this version of the problem, as it forces you to look at the problem from various perspectives. If you're stuck you can download solutions from the dashboard (link in top right corner).