-1

The `two egg problem' is a well-known puzzle and over-used interview question. (See eg Generalised Two-Egg Puzzle)

My question is a variant: come up with an algorithm that works when the maximum number of floors is not known before-hand.

Compare https://en.wikipedia.org/wiki/Exponential_search

I have a candidate: drop the first egg at the floors 1, 1+2, 1+2+3, 1+2+3+4, ... until it breaks, then do linear search with the second egg.

So the more important part of my question is: figure out a sensible measure by which that algorithm is optimal. (Or find an algorithm that's better by that sensible measure.)

I am thinking of something like big-O notation, but only forgetting about constant difference and preserving constant factors. But other measures are fine, too.

Generalizations to a larger but fixed number of eggs welcome.

Matthias
  • 133
  • 2
  • 10
  • The answer will depend on the probability distribution of the number of floors. Minimizing the expected number of drops seems like the obvious measure. – Paul Hankin Feb 24 '16 at 06:41
  • it's not clear what you're asking. You suggest a quadratic search here, but in the comments below talk about "nailing down" conditions under which exponential search works. You say you don't want to just minimize expectation, but what do you want? – Paul Hankin Feb 24 '16 at 06:57
  • The quadratic search is an analogue to the exponential search. So I want to nail down the conditions under which this analogy holds. Figuring out what I want is exactly my question. Minimizing the expectation for a particular distribution is one possibility, but I think there are others, that have less parameters. – Matthias Feb 24 '16 at 09:44

1 Answers1

-1

Using the language of that link, it is pretty straightforward to show that any reasonable algorithm will be O(i), including the one you propose. This is because, unlike the exponential search, the penalty for skipping too many floors at a time is linearly proportional to the number of floors you skipped.

Ken Clubok
  • 1,238
  • 6
  • 11
  • Number of floors is unbounded. As you point out, without a probability distribution, you can not argue about the expected (or even worst case) number of floors as a static number. Of course, we have developed tools in computer science to talk about asymptotic growth. Ie even for list of arbitrary size we can say that merge sort in O(n log n) is a better algorithm than bubble sort in O(n^2). I am looking for a similar, but perhaps more precise, measure for this problem. – Matthias Feb 24 '16 at 06:09
  • Arbitrary size and unbounded are two different things. For example, the most efficient search on a sorted array of arbitrary size n is a binary search, which can be done in O(log n) time. If the array is unbounded, you wouldn't even know where to start, and the algorithm falls apart. – Ken Clubok Feb 24 '16 at 06:37
  • @KenClubok If the number of floors is unbounded but has finite expectation E, then the single-egg algorithm (try the first floor, then the second, etc.) has finite expectation (and is also equal to E). So the question makes sense even in the unbounded case. You're right that the optimal algorithm will depend on the probability distribution. – Paul Hankin Feb 24 '16 at 06:47
  • @PaulHankin. Thanks! By the way, I do not necessarily want to optimize the expected number of drops. Basically, I want to nail down the conditions under which the obvious porting of the idea behind exponential search (https://en.wikipedia.org/wiki/Exponential_search) works. – Matthias Feb 24 '16 at 06:51
  • @KenClubok, it seems like you edited your answer. Are you talking about the first or second link? How would you show that the algorithm takes O(i)? I think the quadratic search algorithm proposed is O(sqrt(i)), and not O(i). – Matthias Feb 24 '16 at 09:48
  • I'm talking about the second link. Now let's show that the algorithm is O(i): Your algorithm has two parts: Getting the first egg to break, and getting the second egg to break. Because the floor you are testing on the first egg goes as O(a^2) (where a is the attempt number), the first egg breakage will indeed take place in O(sqrt(i)), But then you have to go back through the floors you skipped in the last attempt. The number of floors skipped will be a, which we have just shown is O(sqrt(i)), so.... Oh yeah.... you're right. – Ken Clubok Feb 24 '16 at 19:46
  • I think this makes it easy to prove that the quadratic algorithm is optimal. The more efficient the first egg breakage is (because you skipped more floors), the less efficient the second egg is (because you have to cover all the floors you skipped). So the optimal algorithm will be when they are both of the same order. If the first egg algorithm is the function f(a), then this means that the inverse of f(a) must be the same polynomic order (of i) as the derivative of f(a). This only happens if f(a) is quadratic. – Ken Clubok Feb 24 '16 at 19:53
  • Yes, we are on the same page now. And in O(.) terms this algorithm is basically optimal, and even optimal for all sensible distributions. I was hoping for something that's stronger than what O(.) estimation gives you. O(.) ignores constant factors. I think we can analyse the constant factors, and merely have to skip constant differences. (We have to skip these, because a variant algorithm might skip a lot of steps in the beginning.) – Matthias Feb 25 '16 at 00:40
  • @KenClubok You can do a sort of binary search when the sequence you are searching in is unbounded, and you can find the item you are looking for in O(log (position of the item)). Basically, you first grow your search range geometrically, then you use normal binary search afterwards: https://en.wikipedia.org/wiki/Exponential_search – Matthias Sep 18 '20 at 02:11
  • @KenClubok Binary search (and exponential search) only work when you have an infinite supply of eggs. – Matthias Aug 02 '22 at 05:44