Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Puzzle Description
3.
Solution
4.
Frequently Asked Questions
4.1.
How should we solve the puzzles during the interview?
4.2.
Best tips for preparing for puzzles for interviews?
4.3.
Should we always reach the correct answer to the puzzle during the interview?
5.
Conclusion
Last Updated: Mar 27, 2024

2 Eggs 100 Floors

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM
Interview Puzzles

Introduction

Some interviews involve puzzles apart from technical questions. Puzzles are a good measure of one's analytical skills and lateral thinking. Many companies ask puzzles in their interviews to filter the candidates based on their real-life problem-solving skills. You can get perplexed if you are not ready for them. 

The interviewer is generally interested in the candidate's approach while solving the puzzle. Solving different puzzles can help you build up the thinking skills and the out-of-the-box approach the companies demand.

2 eggs and 100 floors puzzle is one such puzzle that is asked frequently in the interviews. Let us have a look at it.

Illustration image

Puzzle Description

A building has 100 floors. One of the floors is the highest floor an egg can be dropped from without breaking.

If an egg is dropped from above that floor, it will break. If it is dropped from that floor or below, it will be completely undamaged, and you can drop the egg again.

Given two eggs, find the highest floor an egg can be dropped from without breaking, with minimum drops.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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:

  1. If an egg does not break by dropping from a specific floor, it will not break from another floor below.
  2. 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.

Live masterclass