61–70 of 87 posts
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 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?
Earlier quoted context omitted.
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.
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 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.
EDIT: actually, the worse case depends on the algorithm you are using; if you are using linear search, the worst case is when the egg won't break for any height. So yeah, in that case the distribution is uniform. But it seems like grasping at straws.
This isn't a critical thinking problem, it's a math problem. As a critical thinker, I would estimate what floor I think the egg would break at, then estimate a safe floor I feel the egg won't break at. The more eggs I have, the less safety margin needed. After finding the first "safe" floor I would go up floor by floor (or more than one floor at a time if I had spare eggs).
This isn't a solution to the problem. Your approach carries the risk that you never find the answer (given the preconditions). I don't think this qualifies as "good" critical thinking, since you don't actually have a solution.
Earlier quoted context omitted.
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 int…
> "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."
Pretty much.
More explicitly, the grandparent is relying on the assumption that E(egg2) is independent of what happens to egg1, which is only true if the interval sizes are the same. In the article's solution, E(egg2) is dependent upon which interval egg2 is dropped in -- if egg1 breaks on the first drop, E(egg2)=7 (the center of the 1-13 interval) but if egg1 breaks on floor 100, E(egg2)=0 since we already know floor 99 is safe.
To calculate E(egg1 + egg2) we need to compute something resembling a weighted average. A quick-and-dirty excel chart gives me an expectation of 9.97, whereas intervals of size 10 give an expectation of 10.5 (first egg gets 1-10 drops for an expectation of 5.5; second gets 1-9 drops for an expectation of 5.0 as the tenth drop would be a repeat.)
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 wonder if it would avoid this kind of objection (which always comes up in logic puzzles) if problems was first stated in mathematical terms, and then analogized to a real world scenario. Something like ... Assume two sets of integers (1..n) and (n+1..100), where 1 If it helps, you can analogize this problem to dropping two fragile objects out of a 100-story building or something. Just don't forget the failure mode…
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…