Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Two Egg Problem

datagenetics.com

Post reply on HN
Print view View original

41–50 of 87 posts

Re: The Two Egg Problem

#41

Post by jonsen »

psykotic wrote: post #38
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 require…

You have to go down and pick up the unbroken egg.

Re: The Two Egg Problem

#42

Post by psykotic »

jonsen wrote: post #41
psykotic wrote: post #38

Earlier quoted context omitted.

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 require…

You have to go down and pick up the unbroken egg.

Good point! That adds a lot of nuance. With several eggs, if you drop one egg and it doesn't break, you have the option of postponing the pick-up until later or leaving it on the ground altogether. Let me think about it.

Re: The Two Egg Problem

#43

Post by Someone »

tocomment wrote: post #39

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

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 half the maximum height. That gives you less information, but decreases the chance that you get into the 'only one egg in hand' endgame.

Re: The Two Egg Problem

#44

Post by vladd »

ww520 wrote: post #31

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.

Part of an interview should test communication skills as well.

In the real job's performance you'll get ill-defined specs; it's sometimes more important to know to ask the right questions rather than solve perfectly the wrong problems.

Interviewers are humans, sometimes tired, and an ill-defined question is likely to appear sooner or later. Asking the interviewer if he meant worst-case has the potential to bring lots of bonus points for you; at least it would in my book.

Re: The Two Egg Problem

#45

Post by manglav »

kbgrant wrote: post #17

I was asked this question at a Google interview in 2006. At that time I worked it out mathematically as the author has here. Only afterwards did I realize that it is a simple Dynamic Programming problem. Let f(y) be the number of drops required with y floors remaining. At a drop from floor x, either the egg breaks and you must test all floors from 1 to x-1, or else the egg does not break and you have reduced to a sma…

This is really helpful ,thank you for the example. Does anyone know of any other resources for simple Dynamic Programming examples?

Re: The Two Egg Problem

#46

Post by [deleted] »

benihana wrote: post #19
dsr_ wrote: post #5

Earlier quoted context omitted.

All it would take to remove the real-world problem would be to change the object from an egg to a ball made of a material of unknown strength and toughness. Poor specifications lie at the root of many a programming problem.

Yes but this isn't a programming problem. It's a math thought experiment. The real thing I'm wondering is why are you making a big deal about this? You obviously have the mental capacity to come up with the concept that it's a special material, why can't you just pretend that's what it is and not make a big pedantic joke about it? What is added to this discussion by pointing out something we all know - that eggs brea…

[deleted]

Re: The Two Egg Problem

#47

Post by bgilroy26 »

antidoh wrote: post #16
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…

Suspension of disbelief: https://en.wikipedia.org/wiki/Suspension_of_disbelief "This is a math puzzle plain and simple." You're being asked to accept that it's possible for an egg, or some other fragile object like, say, a baby, to survive a drop from the first or any other floor, and proceed to solve the math problem.

I agree with both you and the parent post. The article definitely asks for the suspension of disbelief and to be treated like a math puzzle.

However, I think it would be a valuable exercise to try and make a more formal statement of the situation so that the parts of the problem that don't line up squarely with the premise (i.e. eggs often crack when dropped from ~4ft high) were more explicit.

That way, the problem could be introduced both ways at the outset, so that you have the motivating image along with the actual constraints of the problem.

Re: The Two Egg Problem

#48

Post by JunkDNA »

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 agree here. My first thought was that you optimize for the two floors and forget about most of them. One of the best skills you can have when solving real world problems is to recognize when they're specifically not general case math problems and take the appropriate short cuts. If it weren't an egg, it would be a different story. But the problem specifically says it's an egg. Not a bowling ball or a chair or any other semi-resilient object that could survive an arbitrary fall. Details like that matter.

Re: The Two Egg Problem

#49

Post by sopooneo »

benihana wrote: post #19
dsr_ wrote: post #5

Earlier quoted context omitted.

All it would take to remove the real-world problem would be to change the object from an egg to a ball made of a material of unknown strength and toughness. Poor specifications lie at the root of many a programming problem.

Yes but this isn't a programming problem. It's a math thought experiment. The real thing I'm wondering is why are you making a big deal about this? You obviously have the mental capacity to come up with the concept that it's a special material, why can't you just pretend that's what it is and not make a big pedantic joke about it? What is added to this discussion by pointing out something we all know - that eggs brea…

I hear you on that, and it can be annoying when people knowingly pretend not to know what you are talking about. However, the most groundbreaking things are often not so much the discovery of clever solutions as the recognition of what the actual problem is. In my work creating custom workflow apps, discovering the question is by far the most difficult part.

Re: The Two Egg Problem

#50

Post by chmike »

JunkDNA wrote: post #48
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 agree here. My first thought was that you optimize for the two floors and forget about most of them. One of the best skills you can have when solving real world problems is to recognize when they're specifically not general case math problems and take the appropriate short cuts. If it weren't an egg, it would be a different story. But the problem specifically says it's an egg . Not a bowling ball or a chair or any…

Exactly my thought. This could have been a test of over analysis. Though he wrote it should be considered as a simple mah problem and nothing more,
Post reply on HN