Solution
The brute force approach for this puzzle is to drop the egg from the first floor and keep going up until the egg is broken. This solution is very inefficient. We have to find the minimum number of drops.
Two things to keep in mind while solving the puzzle are:
- If an egg does not break by dropping from a specific floor, it will not break from another floor below.
- If an egg breaks by falling from a certain floor, it will break from any floor above that.
If we drop the egg from a floor, there are two possibilities: either the egg will break, or it doesn't break. If the egg breaks, we need to check the floors lower than the current floor by the other egg starting from floor number one. If the egg doesn't break, we must check the floors higher than the current floor.
The whole puzzle boils down to selecting the optimal floor number to drop the egg for the minimum number of drops. Let us suppose we drop the egg from pth floor. If the egg breaks, we need to check the lower p-1 floors one by one from floor one. So, the worst case for this is p trails. If the egg doesn't break, we need to check from a higher floor. The next floor is p+p-1. We took a leap of p-1 floors because we already tested for the pth floor, and to minimize the number of trials, we cannot go beyond p attempts. Likewise, if the egg does not break, we will take a jump of p-2 from the current floor. Thus, the next floor is p + (p-1) + (p+2), and so on.
Thus, for n number of floors, we have:
p + (p-1) + (p-2) + (p-3) + …. = n
The sum of the above series is given by (p*(p+1))/2.
Example:
Let us try to find out the number of trials to test a 100-floor building"
For n =100 → (p*(p+1))/2=100 → p = 13.65.
Thus, it takes 14 trials to test a 100-floor building.
Answer: 14
Check out this problem - 8 Queens Problem
Frequently Asked Questions
How should we solve the puzzles during the interview?
Think about the problem and try to understand the question. Ask for clarifications if you feel that you do not understand the puzzle. Getting the right answer is not as important as your approach. Always explain your approach while answering.
Best tips for preparing for puzzles for interviews?
The best approach is practicing different puzzles and solving the previously asked puzzles.
Should we always reach the correct answer to the puzzle during the interview?
You should focus on your approach and your ability to convey it to the interviewer. Sometimes, you may not be able to reach the correct answer, but if your approach is right, it does not matter much.
Conclusion
This blog looked at an exciting puzzle called the 2 Eggs 100 floors puzzle. We looked at its solution extensively. This is just one of the numerous puzzles asked in your interviews. You can solve any puzzle asked in your interview if you keep practicing these types of puzzles.
Recommended Readings:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
85+ registered