> The question is: What strategy should you adopt to minimize the number egg drops it takes to find the solution? (And what is the worst case for the number of drops it will take?)
Then in the solution he says:
> Problems where the solution lays lower down the building are taking less drops than when the solution lays higher up. We need to come up with a strategy that makes things more uniform.
It is not explained why it has to be more uniform.
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).
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.
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.
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.
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.
But they weren't willing to give us a 3rd egg. This means that 1E is more than 5 trips. So our labor cost is less than E0.20/trip (assuming a uniform labor cost per trip), but more than E0.012/trip (E1 / 86 trips).
My goal is to find someone willing to work for E1 for 100 trips. This would be be between 1/20 and 86% of my salary (management's choice don't give me enough information to know exactly how much I will be making in eggs).
So if I can find someone* willing to work for that labor cost, I can give him the 1 egg problem, and I can give him the other egg to pay his salary, I then I can spend my time doing something more interesting while still achieving management's objectives.
*Assume the cost of finding an employee is zero. This is an important assumption to make in an interview.
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 smaller sub-problem with y-x floors. So the number of drops required is 1 (for the current drop) plus the max of either x-1 or f(y-x). We simply minimize this value over all potential floors x from 1 to y.
Here is a solution in C++:
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 there, got the T-shirt.)
"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.
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.
I've heard this problem specified as involving fossilized dinosaur eggs in order to get around this problem.
Except of course, the article doesn't mention what the landing surface is, or whether it is what we think of as an egg, or some hypothetical super-egg. This would seem to be discounted by the "There are no tricks, gotchas or other devious ruses" clause, however. If the point of the article is to make it purely a mathematical problem, then pretty much anything except an egg would work, like "A strong box".
Otherwise, it's pretty much a "work out this problem but automatically disregard anything that I don't think should be part of the solution" interview question, that whilst I have no doubt are asked by many middle manager interviewers, would imagine is a little below microsoft or google.
Poor specifications lie at the root of many a programming problem.
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 break when you drop them from shoulder height.
The alternative is to specify the problem in purely dense mathematical terms. However, I think this way is much better because to understand what the question is really asking without getting into this "eggs break easily" stuff is actually common sense. If someone can't use common sense to figure out what the question is asking without coming up with second grade smart aleck reasons why the problem doesn't work then I think the interviewer would have the answer they would looking for out of the exercise anyway. :)
An interview isn't a written exam. You don't lose points for bringing up real-world considerations - quite the contrary! But the interviewer might ask you to solve the math problem anyway (perhaps by modifying the question a bit, on the fly).
Assume two sets of integers (1..n) and (n+1..100), where 1 <= n <= 100. Your goal is to discover the value of n by asking whether a given number falls within set 1 or set 2. If you propose more than one number that belongs to set 2, you can propose no further numbers. What is the maximum number of proposals necessary to determine n?
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 of "clever".
An object that survies from being dropped from height x may not survive being dropped a second time from height x.
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.
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.
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?
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.
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.
eggs :: [Int] -> Int -> Int
eggs drops floor =
if floor >= last drops
then (length drops) - 1
else let numless = length $ filter (<= floor) drops
below = last $ filter (<= floor) drops
above = head $ 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.)
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.
> "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."
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.)
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"?
What strategy should you adopt to minimize the number of steps it takes you up and down the stairs to find the solution?
Let me know if this is what you had in mind.
And yeah, didn't get that one. Oh well. "Brain teasers" with thoroughly documented, widely-read solutions leave you with a Bayesian problem: You'll have the 0.5% geniuses that can come up with the answer in 2 minutes and 5% of people that have read the answer but will make you believe that they are geniuses by not disclosing they have read the solution.
In other words, you'd probably get 90% cheaters and 10% smarties.
But yeah, since the author has stated it's a math problem we've just left it as a thought experiment.
Not within the rules!
Not out of the rules either (according to what you just posted). At some point you need to crush an egg.
If the rules are implying that you can only do X and we are only looking for solution Y then why are we even talking about this? We may as well have a discussion about trains leaving from Chicago and New York and debate what city they will intersect from on a given day.
F(1,d) = d
F(e,d) = sum k>0. F(e-1, d-k)
The sum can given a closed form solution for e > 2, just like for e=1 and e=2.
Another thing is that he directly solves the quadratic, but in fact n^2/2 < n(n+1)/2 < (n+1)^2/2. So taking the square root of twice the number of floors will get you either give you the number of drops you need with 2 eggs, or will under count by 1. It's easy to check which that is.
I suggest solving this version of the problem, as it forces you to look at the problem from various perspectives. If you're stuck you can download solutions from the dashboard (link in top right corner).
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
With 3 coconuts, we have
n/k + 2k^(1/2)
minimize for k, we get
What happens when we get log(n) coconuts?
Sweet! So at least we can see that it converges to binary search as we add coconuts.
You'd have to shape your answer to the position you're applying for. The article would be perfect for a programming position, above and beyond what I could ever hope to achieve.
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.
Is people ok with posting the solution here? Or want to try out some more?
Hint: square root.
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.
- 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.
So the correct floor at which to make the first drop is clearly not floor 50. If you dropped the first egg from floor 40 you would do better - it'd take you up to 40 goes to find the right floor if it's below floor 40, and up to 31 or so goes to find the right floor if it's above (because you can reuse the first egg to check whether it's in 40-70 or 70-100). Floor 40 is in some sense a "more binary" place to drop the first egg from than floor 50.
If you keep following this line of thought, and remember that whenever you make your approach more efficient, you can recursively apply that more efficient approach to "what do I do if the first egg doesn't break", you'll arrive at the solution given in the article.