Super Egg Drop

HardDynamic Programming2d dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You have k identical eggs and a building with floors 1 through n. There is an unknown threshold floor f with 0 <= f <= n: an egg dropped from any floor above f breaks, and an egg dropped from floor f or below survives and can be reused. A broken egg cannot be used again. Each move, you drop one unbroken egg from a floor of your choice. Return the minimum number of moves that guarantees you can determine f exactly, no matter what its value is. Aim for about O(k * log n) or O(k * moves) time.

Examples

Input: k = 1, n = 2
Output: 2
With one egg you must test floor 1 then floor 2, so 2 moves in the worst case.
Input: k = 2, n = 6
Output: 3
Two eggs and 3 moves can distinguish up to 6 floors.
Input: k = 3, n = 14
Output: 4
Three eggs with 4 moves cover up to 14 floors.

Constraints

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

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More 2d dp problems