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?
Take the elevator :)
The Two Egg Problem
51–60 of 87 posts
Re: The Two Egg Problem
#52I 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…
Again you expect the interviewee to read your mind that he should ask a particular question. The puzzle is set up with certain conditions and boundary to see how the interviewee performs with those constraints. If one of the terms of the puzzle can be changed, then other terms can be changed, too. I would just replace the egg with a steel ball and be done with it, like just in real life you can just push the boundary and replace the meaning of the question completely.
Re: The Two Egg Problem
#53An 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…
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.
Re: The Two Egg Problem
#54I 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…
This seems to be false:
eggs :: [Int] -> Int -> Int
eggs drops floor =
if floor >= last drops
then (length drops) - 1
else let numless = length $ filter ( floor) drops
in numless + (floor - below) + (if floor + 1 == above then 0 else 1)
sum $ map (eggs [0,10 .. 100]) [0..100] -- returns 1100
sum $ map (eggs [0,14,27,39,50,60,69,77,84,90,95,99,100]) [0..100] -- returns 1047
But if I haven't made a mistake, "10, 20, 30..." takes an average of 10.9 drops and "14, 27, 39..." takes an average of 10.4. That's assuming the floor is uniformly distributed between 0 and 100 inclusive.)
Re: The Two Egg Problem
#55Earlier quoted context omitted.
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.
I had a quick go at it using memoized minimax search. I assumed that picking up any dropped eggs is automatic when you're on the ground floor, but it would also be easy to model it as an action.
https://gist.github.com/3157191
Let me know if this is what you had in mind.
Re: The Two Egg Problem
#56The 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.
Darn...too late to edit.
Note that if the number of floors is 105 instead of 100, then you can still do it in 14 drops, and the solution is unique: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 102, 104, 105.
The two solutions given above for 100 floors can be derived from the 105 solution. To get the solution given in the article, use the 105 floor solution and if it calls for dropping from a floor above 100 pretend that you did that drop and the egg broke, and don't actually count that drop in your drop count since you didn't actually do the drop.
The get the solution I gave, take the 105 floor solution, and shift it down 4 floors, so it ends on 100 instead of 105.
Many more solutions are possible by mixing the ideas of pretending that floors about 100 break, and by shifting all or part of the 105 solution down.
Re: The Two Egg Problem
#57I 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…
> E(# of drops) = E(# of drops for 1st) + E(# of drops for 2nd)
In the general case, I don't think this is true. I think you're relying on the idea that all intervals are equally large. But I'm not definite here.
> E(# of drops for 2nd) = 1/2 the difference between two drops of the 1st egg
Sure, but this depends in a nasty way on your schedule for dropping the first egg.
> E(# of drops of 1st) = 1/2 the number of intervals
This is definitely wrong. Say my schedule for dropping the first egg is [1, 2, 3, 100]. On your analysis, the expected number of drops the first egg will take to break is 1.5. If we assume that the egg's breaking threshold is uniformly distributed over floors 1-100, the actual expectation for drops-to-break-the-egg is 3.94.
> 100 = the number of intervals × the difference
True for the average difference, but this is pretty explicit about assuming that the size of an interval is constant.
Re: The Two Egg Problem
#58The 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…
another critical error is damage to the egg (or any object) from each 'successful' drop.
An object that survies from being dropped from height x may not survive being dropped a second time from height x.
Re: The Two Egg Problem
#59Earlier quoted context omitted.
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.
Can you see if the egg is broken without going down? I guess you're assuming so.
Re: The Two Egg Problem
#60An 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
If the probability of an egg breaking on any particular floor is uniform over all floors--something reasonable to assume unless you're told otherwise--the average case is the worst case.