The Two Egg Problem • Hacker News Board

Re: The Two Egg Problem

#21

Post by majormajor » Sat, Jul 21, 2012, 4:14 PM UTC

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, that's good, let's move on."

I could've asked for paper, I suppose, but something about the word "puzzle" makes me want to puzzle it out in my head.

So my question for any interviewer types who ask puzzle questions is: do you prefer a candidate to go all the way to working out an optimal solution on paper, or is it really more about "the approach"?

Re: The Two Egg Problem

#22

Post by cperciva » Sat, Jul 21, 2012, 4:26 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 know that an unprotected egg will smash when dropped from one story, guaranteed.

I've heard this problem specified as involving fossilized dinosaur eggs in order to get around this problem.

Re: The Two Egg Problem

#23

Post by tomp » Sat, Jul 21, 2012, 4:45 PM UTC

JeanPierre wrote: post #13

From the text: We now have all the information to compute the optimal two egg solution. While I prefer to read about algorithms and strategies in the fashion the author writes, I'm a bit sad that there's is no proof (or informal reasoning) why this is the optimal solution. Does anyone have a paper or some reasoning which will make me believe that this is the optimal solution?

When you break the first egg, the worst case is the difference between the current floor (where the egg broke) and the previous floor (where the egg last survived). So, the worst total number of drops is the number of drops for the first egg (until it breaks), plus the above difference. If you try making the maximum difference less than 14, you run into problems with the first number...

The problems with optimizing worst case are much simpler than optimizing the average case (you don't have to deal with probabilities, and you don't need to know the distribution of egg hardness). So, the proof, and the complexity of the proof, depends on what "optimality" measure you choose.

Re: The Two Egg Problem

#24

Post by [deleted] » Sat, Jul 21, 2012, 4:50 PM UTC

[deleted]

Re: The Two Egg Problem

#25

Post by tomp » Sat, Jul 21, 2012, 4:56 PM UTC

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, knowing that x × y = 100. Since the problem is symmetric, x and y must be equal, namely 10, so "every 10 floors" is the correct answer.

Re: The Two Egg Problem

#26

Post by dahbearz » Sat, Jul 21, 2012, 5:03 PM UTC

How about this solution: It's an egg. It will break from the hight of even 5 feet. The answer is the first floor.

Re: The Two Egg Problem

#27

Post by sigkill » Sat, Jul 21, 2012, 5:04 PM UTC

columbo wrote: post #4

Wouldn't the absolute best way (assuming you have never seen an egg before and do not know anything about eggs) would be to try and crush one egg in a vice grip to determine the strength of the outer structure and then infer a fuzzy-ish height/speed limit from that?

Well frankly, as a aero/mech engineer I'd definitely pull out the UTM and the aero chamber. Your vice grip isn't going to be enough. [For those wondering, first the aero chamber to determine Cd and terminal velocity. Then the UTM be used to determine the compressive strength.] After that I'd scan the other egg in a 3D scanner and generate a super accurately detailed model. Once the model is ready, it's just a matter of plugging these values into Ansys explicit dynamics or Comsol multiphysics and find out the exact height at which the egg will break. Granted, you might require a bunch of the world's fastest super computer clusters and a few days to solve this problem, but hey you have a very high accuracy and precision. [Probably +_ 1cm even].

But yeah, since the author has stated it's a math problem we've just left it as a thought experiment.

Re: The Two Egg Problem

#28

Post by sampo » Sat, Jul 21, 2012, 5:07 PM UTC

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…

optimizing the average case is (in my experience) more common in optimization problems ... the author should say is that the number of floors required to break the egg follows a uniform distribution

Then again, optimizing the worst case performance can be done without worrying about the underlying, and unknown, distribution of the lowest egg breaking drop.

If we start optimizing the average performance, then we need to assume something about the distribution (is it uniform? exponential? is there a bump in the middle?), and different distribution will have different optimal search strategies.

Looking at the worst case keeps the problem algorithmic, the version you propose would be more an exercise in probability calculus.

Re: The Two Egg Problem

#29

Post by [deleted] » Sat, Jul 21, 2012, 5:09 PM UTC

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…

[deleted]

Re: The Two Egg Problem

#30

Post by chrisbennet » Sat, Jul 21, 2012, 5:14 PM UTC

If I was interviewing someone with this problem, I would want to hear what questions the interviewee asked, such as: "Do you want to optimize for best average or minimizing the worst case?"