Egg Dropping Problem: Dynamic Programming Fundamentals & Understanding Subproblem Decomposition

Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions


Question: You are given n eggs and specified a number of k floors. Write an algorithm to find the minimum number of drops is required to know the floor from which if the egg is dropped, it will break.

Note: There are more optimal solutions than this approach, but in a 45-minute interview they seem to me unreasonable to get. So I covered what one could reasonably deduce given they have never seen this question.


Complexities

Time: O( totalEggs * totalFloors^2 )

We will have totalEggs * totalFloors subproblems and spend O(totalFloors) time computing each subproblem.

Space: O( totalEggs * totalFloors )

We can upper bound to the number of subproblems which will be totalEggs * totalFloors subproblems (whether you include the base cases or not in the memoization table)

++++++++++++++++++++++++++++++++++++++++++++++++++

HackerRank:    / @hackerrankofficial  

Tuschar Roy:    / tusharroy2525  

GeeksForGeeks:    / @geeksforgeeksvideos  

Jarvis Johnson:    / vsympathyv  

Success In Tech:    / @successintech