Hacker News Reader

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.

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 worse case is much rarer than some other case (I'd ask if I think that).

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.

> 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.

> 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.

> 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.

No. The worse case is when the topmost floor is the most likely to break the egg. And it's not reasonable to to assume anything about the distribution, so there's not a "most reasonable" case. Except maybe assuming that the higher the floor, the higher the chance of breaking the egg, simply because we are talking about things breaking and height plays a factor in that.

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.