Egg Drop With 2 Eggs and N Floors Interview Question for Google

You are given two identical eggs and you have access to a building with n floors labeled from 1 to n.

You know that there exists a floor f where 0 <= f <= n such that any egg dropped at a floor higher than f will break, and any egg dropped at or below floor f will not break.

In each move, you may take an unbroken egg and drop it from any floor x (where 1 <= x <= n). If the egg breaks, you can no longer use it. However, if the egg does not break, you may reuse it in future moves.

Return *the minimum number of moves that you need to determine with certainty what the value of f is.

Example 1:

Input: n = 2 Output: 2 Explanation: We can drop the first egg from floor 1 and the second egg from floor 2. If the first egg breaks, we know that f = 0. If the second egg breaks but the first egg didn't, we know that f = 1. Otherwise, if both eggs survive, we know that f = 2.

Example 2:

Input: n = 100 Output: 14 Explanation: One optimal strategy is:

Drop the 1st egg at floor 9. If it breaks, we know f is between 0 and 8. Drop the 2nd egg starting from floor 1 and going up one at a time to find f within 8 more drops. Total drops is 1 + 8 = 9.
If the 1st egg does not break, drop the 1st egg again at floor 22. If it breaks, we know f is between 9 and 21. Drop the 2nd egg starting from floor 10 and going up one at a time to find f within 12 more drops. Total drops is 2 + 12 = 14.
If the 1st egg does not break again, follow a similar process dropping the 1st egg from floors 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, and 100.

Regardless of the outcome, it takes at most 14 drops to determine f.

The problem is a classic dynamic programming problem. We are asked to find the minimum number of moves to determine the critical floor f in a building with n floors, given two identical eggs. If an egg breaks when dropped from floor x, it will also break when dropped from any floor higher than x. If an egg does not break when dropped from floor x, it will not break when dropped from any floor lower than x. We want to find the floor f such that dropping an egg from any floor above f causes it to break, and dropping an egg from any floor at or below f does not cause it to break.

Brute Force Solution

A naive approach would be to start from floor 1 and go up one floor at a time, dropping the first egg at each floor. If the egg breaks, we know the critical floor is one less than the current floor. If the egg doesn't break, we move to the next floor. If the first egg breaks at floor x, we know that the critical floor lies between 0 and x-1. With the second egg, we can check each floor linearly from 1 to x-1 to find the exact value of f. This approach would be very slow, especially for larger values of n.

Optimal Solution (Dynamic Programming)

We can solve this problem using dynamic programming. Let dp[i][j] represent the minimum number of moves needed to determine the critical floor with i eggs and j floors. We have two choices when dropping an egg from floor x:

The egg breaks. In this case, we have i-1 eggs and x-1 floors to check.
The egg doesn't break. In this case, we have i eggs and j-x floors to check.

Therefore, the recurrence relation is:

dp[i][j] = 1 + min(max(dp[i-1][x-1], dp[i][j-x])) for x in range(1, j+1)

However, this is computationally expensive. A better DP formulation is to define dp[m][k] as the maximum number of floors that can be checked with k eggs and m moves. If we drop the first egg on floor x, we either have k-1 eggs and m-1 moves remaining if it breaks, or k eggs and m-1 moves remaining if it doesn't break. Therefore, the number of floors we can check is the sum of those two scenarios, plus 1 (for the floor we just dropped the egg on).

dp[m][k] = dp[m-1][k-1] + dp[m-1][k] + 1

Base cases:

dp[0][k] = 0 (0 moves, can check 0 floors)
dp[m][0] = 0 (0 eggs, can check 0 floors)
dp[1][m] = m (1 egg, m moves, can check m floors linearly)

We are trying to find the minimum m such that dp[m][2] >= n. We iterate through values of m and calculate dp[m][2] until we find the smallest m that satisfies the condition.

Here is the Python code implementation:

def egg_drop(n):
    dp = [[0] * 3 for _ in range(n + 1)]
    m = 0
    while dp[m][2] < n:
        m += 1
        for k in range(1, 3):
            if m == 1:
                dp[m][k] = 1
            else:
                dp[m][k] = dp[m-1][k-1] + dp[m-1][k] + 1
    return m

# Example usage:
n = 100
result = egg_drop(n)
print(f"Minimum number of moves for n = {n}: {result}")

Big(O) Run-time Analysis

The time complexity of the dynamic programming solution is O(n) because we iterate through values of m until dp[m][2] >= n. The inner loop runs a constant number of times (once for k=1 and once for k=2).

Big(O) Space Usage Analysis

The space complexity of the dynamic programming solution is O(n) because we store the dp table with dimensions (n+1) x 3. We only need to store the values for the current and previous row, so we can optimize this to O(1) space complexity by using only two rows.

Edge Cases

n = 1: The minimum number of moves is 1 (drop the egg from floor 1).
n = 2: The minimum number of moves is 2 (drop from floor 1, then floor 2 if needed).
n = 1000: The minimum number of moves is 31.
n = 0: While the prompt says 0 < f <= n, if we handled n=0 we should return 0, which would mean that we don't need to check any floor.