Katkat
Back

Solve classic coding interview problems

VoleonSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Determine the minimum number of trials needed to find the highest safe floor in an n-story building using at most k eggs in the worst case.

Problem Statement

You are given k identical eggs and access to a building with n floors numbered 1 through n.

There exists an unknown floor f such that 0 <= f <= n where:

  • Any egg dropped from a floor higher than f will break.
  • Any egg dropped from floor f or lower will not break.

Each trial consists of dropping an egg from a chosen floor x (1 <= x <= n):

  • If the egg breaks, you can no longer use it. It counts as one of your k eggs.
  • If the egg does not break, you may retrieve it and use it again in subsequent trials.
  • The outcome is certain: if an egg breaks at floor x, it will break at all floors > x. If it survives at floor x, it survives at all floors ` int: pass

## Input Format
- `k`: An integer representing the number of available eggs (`1 <= k <= 100`).
- `n`: An integer representing the number of floors (`1 <= n <= 10^4`).

## Output Format
- Returns an integer denoting the minimum number of attempts needed in the worst case.

## Examples

### Example 1
```python
k = 1
n = 2
# Output: 2

Explanation: With only 1 egg, you must drop from floor 1, then floor 2 sequentially. If it breaks at floor 1, f = 0. If it survives floor 1 and breaks at floor 2, f = 1. If it survives floor 2, f = 2. The worst-case requires 2 drops.

Example 2

k = 2
n = 6
# Output: 3

Explanation: Drop from floor 3 first:

  • If it breaks, 1 egg remains to test floors 1 and 2 sequentially (worst case: 1 + 2 = 3 trials).
  • If it survives, drop from floor 5 with 2 eggs remaining. If it breaks, test floor 4 with the remaining egg (3 trials total). If it survives, test floor 6 (3 trials total). Thus, 3 drops are sufficient.

Example 3

k = 3
n = 14
# Output: 4

Constraints

  • 1 <= k <= 100
  • 1 <= n <= 10^4

Hints

Hint 1

A standard dynamic programming state `dp(k, n)` yields an O(k * n^2) solution, which is too slow; consider how the monotonicity of egg outcomes allows binary searching for the optimal floor to test.

Hint 2

Instead of finding the minimum drops for a fixed floor count, invert the problem: what is the maximum number of floors you can check given `m` moves and `k` eggs?

Hint 3

If you drop an egg at step `m`, it either breaks (covering `dp[m-1][k-1]` floors below) or survives (covering `dp[m-1][k]` floors above), leading to the recurrence `dp[m][k] = 1 + dp[m-1][k-1] + dp[m-1][k]`.

Follow-up questions

  • How does the time and space complexity change if n is increased up to 10^9?
  • Can you express the maximum floors checkable in m moves with k eggs as a sum of binomial coefficients, and how does this enable an O(k log n) solution?
  • What strategy would you use if each egg drop had an associated cost depending on the floor level dropped from?