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
Subscribe To Live Tech Offers: https://offerfeed.io
Join Our Coaching Service: https://backtobackswe.com/coaching
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: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Видео Egg Dropping Problem: Dynamic Programming Fundamentals & Understanding Subproblem Decomposition канала Back To Back SWE
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Subscribe To Live Tech Offers: https://offerfeed.io
Join Our Coaching Service: https://backtobackswe.com/coaching
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: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Видео Egg Dropping Problem: Dynamic Programming Fundamentals & Understanding Subproblem Decomposition канала Back To Back SWE
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
5 Simple Steps for Solving Dynamic Programming ProblemsEgg Dropping Problem - Approach to write the code (Dynamic Programming) | GeeksforGeeksEgg Dropping Puzzle with 2 Eggs and 100 Floors || Microsoft Interview PuzzlesEgg Dropping Dynamic ProgrammingProfessor Clyde Kruskal On Kruskal's AlgorithmHow to listen to lectures: Understand & remember with these strategiesImplement A Binary Heap - An Efficient Implementation of The Priority Queue ADT (Abstract Data Type)Longest Common Subsequence (2 Strings) - Dynamic Programming & Competing SubproblemsCount Total Unique Binary Search Trees - The nth Catalan Number (Dynamic Programming)Lecture 19: Dynamic Programming I: Fibonacci, Shortest PathsHow I Got An Internship @ TwitterEgg Dropping Problem Dynamic Programming | Leetcode Hard SolutionsThe Egg Dropping Problem - Interview QuestionWhat no one tells you about coding interviews (why leetcode doesn't work)Teaching yourself to learn programming? Start Here!43 Egg Dropping Problem RecursiveThe Change Making Problem - Fewest Coins To Make Change Dynamic ProgrammingSerialize & Deserialize A Binary Tree - Crafting Recursive Solutions To Interview Problems