question
You are given 2 identical eggs and access to a 100-story building. If an egg is dropped from a story and broken then it cannot be used again. But if the egg does not break, then it will not break for every story below and can be considered undamaged.
Devise a strategy to determine the highest floor from which the eggs can be dropped without breaking while minimizing the number of egg drops to find the solution. What if you were given 3 eggs? 4 eggs? etc.
P.S. This question is commonly used by Google/Microsoft in interviews
Devise a strategy to determine the highest floor from which the eggs can be dropped without breaking while minimizing the number of egg drops to find the solution. What if you were given 3 eggs? 4 eggs? etc.
P.S. This question is commonly used by Google/Microsoft in interviews
Most people will try to use a binary solution or try to drop the egg every 10 stories. While these may lead to acceptable solutions, the optimal solution will involve a summation function.
The folks at DataGenetics have written an excellent and detailed solution to this question. Check the link for the full solution. I will simply present the bare gist of it below.
Suppose we were to drop an egg every 10th story till it broke. Our worst case scenario would total 19 drops and would occur when the egg breaks at floor 99. This is because when the first egg breaks on the 100th story, we go back to the 91st floor and work our way back to floor 99.
To minimize the number of drops, we need to minimize the number of maximum regret. This is because the if the egg breaks at a lower floor, the most number of drops will be less than if the egg breaks at a higher floor. The solution this realization eventually leads to is to step-up by 14 floors at first and then subtract one floor with every step. Ex. Drop at floor 14 -> Egg survives -> Drop at floor 14 + 13 -> Survives -> Drop at 14 + 13 + 12 ...
Again, please see DataGenetics for the full and thorough solution.
Thoughts or alternate solution? Let us know in the comments below!
Suppose we were to drop an egg every 10th story till it broke. Our worst case scenario would total 19 drops and would occur when the egg breaks at floor 99. This is because when the first egg breaks on the 100th story, we go back to the 91st floor and work our way back to floor 99.
To minimize the number of drops, we need to minimize the number of maximum regret. This is because the if the egg breaks at a lower floor, the most number of drops will be less than if the egg breaks at a higher floor. The solution this realization eventually leads to is to step-up by 14 floors at first and then subtract one floor with every step. Ex. Drop at floor 14 -> Egg survives -> Drop at floor 14 + 13 -> Survives -> Drop at 14 + 13 + 12 ...
Again, please see DataGenetics for the full and thorough solution.
Thoughts or alternate solution? Let us know in the comments below!