The Egg Problem

The Egg Problem

An Interview Question Examined.

We have a building defined in terms of height in floors, or ‘H’. This building has a special floor ‘N’ where 0 <= N <= H. We also have two eggs. These eggs have a special property, where if they are dropped out the window of any floor, they will break if the floor is is greater than or equal to N. Once an egg is broken, they can no longer be used for this dropping experiment. How do we find N in the least amount of drops?


Relevance

I read this question somewhere online maybe 4 months ago. I casually thought about it, came up with a vague idea of a solution and moved on. However, recently I stumbled upon this article which presents a slightly different version of the same problem. This article claimed this was one of the top questions interviewers at Apple gave to engineering interviewees. Well this piqued my interest. Since then, like all good puzzles, has been stuck in my head. I was thinking about it in the shower, before I fell asleep, and while driving. So let’s see if we can’t make some progress on finding this answer.


General Solution

All the solutions I could come up with all fell into the same general pattern:

  • Drop an egg from a test point at some floor ‘X’.
  • If the drop at X did not cause a break, we have eliminated floors 0 – X. Drop another Egg any floor from X to H. This is our new X.
  • If the drop at X caused a break, move to next step.
  • Start dropping eggs floor by floor starting at ‘Y’, where Y is either 0, or the last X that did not cause an egg break.
  • The next broken egg will occur at floor N.

Choosing Our Drop Point

Since the height of our building is variable, it makes sense to define our X in terms of H. Let X = H / F, where F is an arbitrary integer Consider a building where H=100 and our F is 10. X = 10, or 100/10. Consider a building where H=1000 and our F=5. X = 200, or 1000/5. Note that we are only considering integer division so that we don’t end up with an answer that is not a valid floor. In my code below I refer to this as ‘factor’.
This is where things get tricky. Our number of drops is a function of N and F. Consider a building where H=100, and F=20. If our N=1, our algorithm finds the floor in 3 drops. A drop at floor 5 where the first egg breaks, a drop at floor 0 where the egg doesn’t break, and another at floor 1, where our egg breaks and we are confident that N=1. Keep in mind, I’m thinking in terms of indexing, where the first floor in our building is 0, and the highest floor is (H-1).

Consider the same building where N = 99. We have to drop our egg 20 times before the first break. and another 5 times before our egg breaks again for floors 95 – 99. This demonstrates how our algorithm performs very efficiently for certain values of N, and not as efficiently for others.

This also points out a deficiency in our algorithm. If the egg breaks on the first drop, we have to check floor 0. If the egg breaks at another value, we don’t have the check the last floor where we last performed a drop with no break. Let’s make note of this for our implementation.to

In any case, if we’re going to judge the efficiency of this algorithm for different values of F, it is logical to assume that we have to test it for all values of N. That way, we can objectively say that if we don’t know the value of N, a certain value of F is the best for the task.
Implementation
The only elements of our building concept that we are concerned with are H or height, and N for our special floor. This lends itself to a very simple minimal class:


My Python Algorithm for Finding N

Next we need a system for testing our algorithms. I created a separate class to handle this:

Now all we need to do is call the run() method on a Dropper object.


Deficiencies in Our Model

The first drawback to our model is our test values for F. I chose these somewhat haphazardly. There is probably a more mathematical way to selecting these, but for the moment, we’ll stick with these.

The next deficiency is the fact that we’re only testing values of F in a linear way. Consider a building of H=100 and our F=10. Say for example we decide to determine F as a fraction of either the distance from the last unbroken egg drop or zero to H. In this scenario our first drop still occurs at floor 10. The next drop would occur at floor 19. This occurs because H – 10 = 90. 90 / F = 9. 9 + 10 = 19. It is also very possible that having a varying value of F as the algorithm unfolds would be very helpful. Again, there is probably a very mathematical way of determining the best possible method for varying F as we go, but that is beyond my skill level…at the moment anyway.
Conclusions and Next Steps
The results vary greatly as H changes. This makes sense because as our H increases, the small differences between our values of F become more significant due to rounding. It would be a fun experiment to create a system for evaluating this data again and produce visualizations for the data where we can see the value of each factors change as H increases.

However, let’s assume H is 100 always. Then we can at least be pretty confident that our program can get us pretty close to the right answer. For fun, let’s try this again with values of F specifically chosen for the H=100 scenario and see what we get.

As you can see, F = 8, 10, and 12 all give us the minimum drop average or 10. For the sake of completion, let’s test values in between to see if they vary at all.

So at least in terms of our system of checking values, 10 is the fewest number of drops we can use to discover N. It’s good to know that if we had to test this in real life we’ll only have to buy a dozen eggs.

3 thoughts on “The Egg Problem

    1. Fixed. This post was copied from my old blog and I didn’t notice that some of the formatting HTML came with it. Thanks for pointing that out.

Leave a Reply

Your email address will not be published. Required fields are marked *