2 Eggs – 100 Floors – Interview Question

You are given two Eggs and you are in a building with 100 Floors. You have to find the minimum floor from which if an egg is dropped, it won’t break. You have to do this in such a manner that your worst case number of attempts is minimized.

Let’s find out how to answer this question in a technical interview.

If we were to try binary search, that is, try egg1 at 50th floor. If the egg breaks there. Then we take egg2 and try from 1st floor and then 2nd floor and so on. So if the 49th floor is the answer then in case of Binary Search, the worst case scenario takes 50 attempts.

If we were to try jumping 10 floors at a time, then the worst case scenario is 19 attempts. Suppose we start with egg1 at 10th floor it doesn’t break. Then we try 20th floor, it doesn’t break and so on until 90th floor. Suppose it breaks at 100th floor. Next, we take egg2 and we try at 91st floor -> doesn’t break. Then we try 92nd floor -> doesn’t break and so on. And then we find that it breaks at 99th floor. So in this case it took 19 attempts worst case.
This is certainly an improvement over 50 worst case attempts. But we can still do better.

So there are 2 components to the way we approach the problem. The first egg helps us decide the range where the threshold floor is. And once we know the range, we use the brute force approach with the second egg to find the threshold floor. Since our aim is to minimize the attempts in worst case scenario, we need to reduce the number of attempts needed for second egg by 1 for each attempt consumed by egg 1.
So this leads us to our solution. We want to reduce the floor to be attempted by 1 for egg 1 with each succession. So the solution can be found by solving this equation:
X + (X – 1) + (X – 2) +… = 100.
If you solve for x, the answer comes to about 13.6 which is equivalent to 14.
So for egg 1, we attempt at floor 14, then 27, then 39, then 50, then 60, then 69 and so on. So suppose it breaks 39, then we check floor 28 to 38 to find the threshold floor.
It always take 14 attempts or less to find the threshold floor. So, in worst case, it will take 14 attempts to find the threshold floor.

I will be adding more such interview questions to my youtube channel, please subscribe to my channel Coach4Dev for more such questions.
Until next time Happy Coding 😊