The Two Egg Problem • Hacker News Board

Re: The Two Egg Problem

#81

Post by lmm » Sun, Jul 22, 2012, 10:13 AM UTC

tocomment wrote: post #69

Someone wrote: post #43

Earlier quoted context omitted.

No. If you first test is at floor N, the two possible consequences are: - egg breaks: you know you the answer is in [1,N], and will have to start stepping by one floor until the second egg breaks - egg does not break: you know the answer is in [N+1, max], and you still have an extra egg to play with. There is an asymmetry here. Because of it, assuming that you can improve upon binary search, N should be less than at…

Hmm I'm not following. What do you do with the first egg if it doesn't break?

You keep using it. Binary search is the right way of thinking about it, but in some sense you haven't really created an even split by dropping the egg from floor 50 - because you know that you can figure out the correct floor faster using two eggs than one, you could check floors 51-100 much faster than you could check floors 1-50 (Even if you just did the naive binary search approach you first applied - i.e. if the first egg didn't break on floor 50 then drop it from floor 75, and then after that use the second egg to check each floor, it would only take you So the correct floor at which to make the first drop is clearly not floor 50. If you dropped the first egg from floor 40 you would do better - it'd take you up to 40 goes to find the right floor if it's below floor 40, and up to 31 or so goes to find the right floor if it's above (because you can reuse the first egg to check whether it's in 40-70 or 70-100). Floor 40 is in some sense a "more binary" place to drop the first egg from than floor 50.

If you keep following this line of thought, and remember that whenever you make your approach more efficient, you can recursively apply that more efficient approach to "what do I do if the first egg doesn't break", you'll arrive at the solution given in the article.

Re: The Two Egg Problem

#82

Post by hermannj314 » Sun, Jul 22, 2012, 11:44 AM UTC

Let's say an egg costs 1 egg (1E). This means that for management to give us 2 eggs, they were willing to spend 1 additional egg to let us make (in the worst-case) 14 trips vs 100 if we only had 1 egg. So 1 egg But they weren't willing to give us a 3rd egg. This means that 1E is more than 5 trips. So our labor cost is less than E0.20/trip (assuming a uniform labor cost per trip), but more than E0.012/trip (E1 / 86 trips).

My goal is to find someone willing to work for E1 for 100 trips. This would be be between 1/20 and 86% of my salary (management's choice don't give me enough information to know exactly how much I will be making in eggs).

So if I can find someone* willing to work for that labor cost, I can give him the 1 egg problem, and I can give him the other egg to pay his salary, I then I can spend my time doing something more interesting while still achieving management's objectives.

*Assume the cost of finding an employee is zero. This is an important assumption to make in an interview.

Re: The Two Egg Problem

#83

Post by thlt » Sun, Jul 22, 2012, 4:07 PM UTC

As solved mathematically here http://www.trungh.com/2010/12/light-bulbs/

Re: The Two Egg Problem

#84

Post by malkia » Sun, Jul 22, 2012, 9:08 PM UTC

hermannj314 wrote: post #82

Let's say an egg costs 1 egg (1E). This means that for management to give us 2 eggs, they were willing to spend 1 additional egg to let us make (in the worst-case) 14 trips vs 100 if we only had 1 egg. So 1 egg But they weren't willing to give us a 3rd egg. This means that 1E is more than 5 trips. So our labor cost is less than E0.20/trip (assuming a uniform labor cost per trip), but more than E0.012/trip (E1 / 86 tr…

This could've been something much mor expensive and dangerous to use - for example atomic bomb test to check at what elevation when detonated it would affect the ground (just making this up, btw)

Re: The Two Egg Problem

#85

Post by pippy » Sun, Jul 22, 2012, 11:38 PM UTC

This problem has multiple solutions, as demonstrated by the HN comments. It's not asked to find a solution, instead to figure out your thought processes. You could come up with a comp sci solution (analogous to a data structure or algorithm), or a mathematical solution, or a physics solution or something different.

You'd have to shape your answer to the position you're applying for. The article would be perfect for a programming position, above and beyond what I could ever hope to achieve.

Re: The Two Egg Problem

#86

Post by kristopolous » Mon, Jul 23, 2012, 2:27 AM UTC

I was asked this question once and I said "This is a common, widely discussed interview question on the internet. Are you trying to find out how smart I am thinking on my feet or whether I surf the web, because in practice, on the job, I'd be doing the latter to find out the answer. If you have genuinely unique problems here, you can do better than that."

And yeah, didn't get that one. Oh well. "Brain teasers" with thoroughly documented, widely-read solutions leave you with a Bayesian problem: You'll have the 0.5% geniuses that can come up with the answer in 2 minutes and 5% of people that have read the answer but will make you believe that they are geniuses by not disclosing they have read the solution.

In other words, you'd probably get 90% cheaters and 10% smarties.

Re: The Two Egg Problem

#87

Post by dinkumthinkum » Mon, Jul 23, 2012, 6:09 AM 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…

No, I think this is a great way to discern reasonable from unreasonable people. Unreasonable people would miss the question entirely and bring up these issues. Reasonable people would quickly disregard such jibber jabber, see what the question is asking, and get on to solving the problem.

The alternative is to specify the problem in purely dense mathematical terms. However, I think this way is much better because to understand what the question is really asking without getting into this "eggs break easily" stuff is actually common sense. If someone can't use common sense to figure out what the question is asking without coming up with second grade smart aleck reasons why the problem doesn't work then I think the interviewer would have the answer they would looking for out of the exercise anyway. :)