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

71–80 of 87 posts

Re: The Two Egg Problem

#71

Post by snprbob86 »

lunchbox wrote: post #18

An issue with this puzzle is that the objective is not clearly stated upfront. The author should make it clear from the outset that the goal is to minimize the number of drops in the worst case, rather than to minimize the average case, especially since optimizing the average case is (in my experience) more common in optimization problems. He asks in parentheses what the worst case is, but that just sounds like a sid…

> An issue with this puzzle is that the objective is not clearly stated upfront. The author should make it clear ...

It's an interview question. You're supposed to ask for clarification. In fact, demonstrating your ability to elicit requirements is an important part of a technical interview.

Re: The Two Egg Problem

#72

Post by dwc »

Fargren wrote: post #64
SlowButEffectiv wrote: post #53

Earlier quoted context omitted.

That may be true. Lunchbox's point holds true regardless: the problem statement is ambiguous, and is easy to correct so that it is not so.

Well, the standard in computer science is to optimize algorithms and discuss their performance for the worst case, so if we assume he's talking from a CS perspective, I find it natural to assume he's talking about that. There are a few exceptions, like QuickSort, but if some tells me to optimize some algorithm, I'll assume he's asking for optimization of the worst case unless he says otherwise or it's clear that the…

These considerations certainly exist in every day code as well. If you change the daily reporting process to have a worst case run time of 25 hours then you lose, even if the mean run time is cut in half.

Re: The Two Egg Problem

#73

Post by sold »

lunchbox wrote: post #18

An issue with this puzzle is that the objective is not clearly stated upfront. The author should make it clear from the outset that the goal is to minimize the number of drops in the worst case, rather than to minimize the average case, especially since optimizing the average case is (in my experience) more common in optimization problems. He asks in parentheses what the worst case is, but that just sounds like a sid…

> The author should make it clear from the outset that the goal is to minimize the number of drops in the worst case, rather than to minimize the average case [...] A more minor issue with this puzzle is that for the sake of thoroughness, the author should say is that the number of floors required to break the egg follows a uniform distribution (i.e., every floor is an equally likely candidate).

These two are incompatible. Once you state you are interested in worst case, stating that the number of floors follows a uniform distribution is irrevelant, and IMO confusing; the only relevant thing is that every floor is a possible candidate.

Re: The Two Egg Problem

#74

Post by eranki »

Asymptotically, the question with more coconuts is more interesting. I haven't verified this for sure (there are some assumptions), but:

With the "naive" asymptotically correct solution (go up a constant number k of floors, then linearly search the remainder), two coconuts gives us a worst case cost of:

n/k + k

minimize for k, we get a cost of

2n^(1/2)

With 3 coconuts, we have

n/k + 2k^(1/2)

minimize for k, we get

3n^(1/3)

What happens when we get log(n) coconuts?

log(n)n^(1/log(n))

= O(log(n))

Sweet! So at least we can see that it converges to binary search as we add coconuts.

Re: The Two Egg Problem

#75

Post by criveros »

Start dropping the first egg at floor 1, if it doesn't break, then drop it from floor 10, then 20, then 30, then 40, etc until it breaks. Say the egg breaks at floor 30, start dropping the other egg from floor 21, then 22, then 23, until it breaks. Very easy problem.

Re: The Two Egg Problem

#76

Post by habidasher »

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…

That was my first thought as well. My answer would have been something along the lines of, "Given my domain knowledge of eggs and sidewalks, I can estimate that the egg will survive a fall of at most zero or one stories. Therefore the best algorithm is a linear search starting from the 0th floor."

Re: The Two Egg Problem

#77

Post by georgemcbay »

majormajor wrote: post #21

I was asked that question, with glass bulbs instead of eggs, at an interview last year. I don't think I found the optimal solution of 14, IIRC I got to the point (just talking aloud to the interviewer, no paper) of saying something like "so if we started at, say, floor ten, we'd have nine floors below, and something close to that sets of floors above if we needed to move up..." and he said something like "ok, cool, t…

In my experience it is more about "I heard you were supposed to ask questions like this on tech interviews, so I'll ask it even if I myself am shaky enough on the mathematics behind it that I simply know the One True Solution I read online".

Re: The Two Egg Problem

#78

Post by jessriedel »

snprbob86 wrote: post #71
lunchbox wrote: post #18

An issue with this puzzle is that the objective is not clearly stated upfront. The author should make it clear from the outset that the goal is to minimize the number of drops in the worst case, rather than to minimize the average case, especially since optimizing the average case is (in my experience) more common in optimization problems. He asks in parentheses what the worst case is, but that just sounds like a sid…

> An issue with this puzzle is that the objective is not clearly stated upfront. The author should make it clear ... It's an interview question. You're supposed to ask for clarification. In fact, demonstrating your ability to elicit requirements is an important part of a technical interview.

That doesn't make any sense for a webpage. You either state the problem cleanly, or you explicitly discuss the point of clarification interview questions. But just putting up an ambiguous question with no recourse for the reader (other than carefully reading the answer and inferring what the author meant to ask) is sloppy.

Re: The Two Egg Problem

#79

Post by noonespecial »

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…

As my physics prof used to say with a smirk to all such "clever" retorts to questions he posed: "assume a spherical chicken of uniform density".

Re: The Two Egg Problem

#80

Post by jgeralnik »

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 could continue the binary search but that's not relevant anymore - the problem is to minimize the worst case, and your worst case is 51 while there exists a solution whose worst case is 14.
Post reply on HN