Google’s interview question just got a whole lot simpler. Egg dropping puzzle (2-egg, 100-floor version). “Figure out the highest floor of a 100-floor building an egg can be dropped without breaking, given two eggs” The Egg Dropping Puzzle is a mathematical puzzle that has been around the internet for some time now, which is known to be adopted in interviews of major companies like Google, Microsoft, Accenture and even Hewlett Packard. You are to determine the number of attempts required in the worst case to find the critical floor. minimum Photo by Pablo Vargas via Unsplash Assumptions in the egg dropping puzzle: The two eggs are identical. If an egg does not break by dropping from a certain floor, it will not break dropping from any floor below that. If an egg breaks by dropping on a certain floor, it will break dropping from any floor above that. An egg may break by dropping on the 1st floor. An egg may not break by dropping even on the 100th floor. Note: If you don’t want it to get spoiled, you’d want to stop reading from here and start working out the answer. If you have already read and known the solution, you can skip the following and go ahead to read the combinatorial view of the solution. Solution to the 2-egg, 100-floor egg dropping puzzle. While the answer is not too hard to understand, it takes some twists of one’s thought to arrive at the answer. The solution is derived using the utilization of a restricted number of trials. And then the 2-egg, n-floor solution can be easily generalized. A step-by-step solution to optimize the answer: If the first egg breaks, we need to test the remaining floors one by one starting from the lowest until the remaining egg breaks. For example, if the first drop is on the 50th floor and the egg breaks, it will take 49 more drops from the 1st floor to the 49th floor to ensure the remaining egg does not break until we know the answer. If the first drop is on the 10th floor and it breaks, then it takes a total of 10 trials to know the answer in a worst case scenario, i.e. the egg starts to break on the 9th or the 10th floor. The trials will be: 10 → 1 → 2 → 3 → 4 → 5 → 6 → 7→ 8 → 9 To utilize the number of trials used (10 trials), if the first drop is on the 10th floor and the egg does not break, the second drop should be on the 19th floor, i.e. if the egg breaks on the 19th floor, then you should drop the eggs in the following sequence: 10 → 19 → 11 → 12 → 13 → 14 → 15 → 16 → 17 → 18 (10 trials in total). With this utilization in mind, the ultimate sequence (if an egg never breaks) will be 10 → 19 (10 + 9) → 27 (10 + 9 + 8) → 34 (10 + 9 + 8 + 7) → 40 → 45 → 49 → 52 → 54 → 55, i.e. 10 trials can test up to 55 floors. Using the formula for triangle numbers, trials can test for [m(m+1)]/2 floors, i.e. m 13 trials can test 13 * 14 / 2 = 91 floors14 trials can test 14 * 15 / 2 = 105 floors Thus it takes 14 trials to test a 100-floor building. Let’s view the solution in combinatorics. To derive the general solution of the egg dropping puzzle with any number of eggs, let’s review the 2-egg case again. We will interpret the solution in an alternative way. To keep things simple, we are going to work with 15 floors only. We will drop the eggs (IF an egg does not break) on floors 5, 9, 12, 14, 15, which implies that a maximum of 5 trials is sufficient to obtain the answer. The table below shows all the possible outcomes. Remarks: An egg is broken in trials highlighted in yellow. The “Answer” refers to the highest floor known not to break an egg. There are in total 16 cases, corresponding to the answers 0 to 15 for the 15-story building. By analyzing the distribution of the trials that break the egg, i.e. the yellow cells, we can see that the 16 cases are indeed divided into 3 groups: 0 yellow cells: 1 case (rows in orange) 1 yellow cell: 5 cases (rows in green) 2 yellow cells: 10 cases (rows in cyan) To utilize all the trials and the eggs, the number of cases should be the same as the number of total possible combinations of the yellow cells, i.e. Therefore the 15-floor building can be represented by: And we can generalize the solution for 2 eggs given trials: m Maximum number of floors that can be tested will be… Now how about egg dropping puzzle with 3 eggs? As usual, we will start with a simple case: 3 eggs with 4 trials. If the first trial breaks the (first) egg, there will be 2 remaining eggs with 3 trials, which, according to the above, can test 6 floors. This means we should drop the first egg from the 7th floor. If it breaks by dropping from the 7th floor, we will follow the strategy for testing a 6-floor building with 2 eggs in 3 trials, i.e. throwing out from floor: 3, 5 and 6 (if the eggs do not break). If an egg does not break by dropping from the 7th floor, we can repeat the rationale above to determine the next floor we should drop an egg. If the next drop breaks the egg, there will be 2 remaining eggs with 2 trials, which can test 3 floors. It means that the second trial will be on the 11th floor, leaving floor: 8, 9, 10 for the 2 remaining trials with 2 eggs (if an egg breaks by dropping from the 11th floor). Following the same strategy, if an egg does not break on the 11th floor, we will try floor 13, and then 14 if an egg does not break on the 13th floor. A picture is worth a thousand words (or so they say): The combinatorial view can be applied here too! The reason is that the optimal strategy should utilize all the possible trials with the given number of eggs, where every different egg-breaking combination (a total of 15 combinations in this case) should produce a different answer. To express this numerically, it will be: Remarks: An egg is broken in trials highlighted in yellow. The “Answer” refers to the highest floor known not to break an egg. The general solution with eggs and m trials. x Based on the above discussion, the general solution will be: With eggs and trials, the maximum number of floors of a building we can test is given by: x m Considering the possible case where > , we should write the general solution as: x m A quick question for the readers: what is the implication when x > m? An extract of the numerical values of the general solution is shown below. The answer for the initial problem with 2 eggs and a 100-floor building is highlighted, i.e. 100 is bound by 91 and 105 hence the answer is 14 trials. with these numerical values and a number-of-trial calculator is available. A full spreadsheet For those of you who want to explore even further… For programmers, write a program to obtain the number of trials needed for testing on an n-story building given eggs. (Need hint? ) x https://en.wikipedia.org/wiki/Dynamic_programming#Egg_dropping_puzzle Why can the trials utilize all the possible combinations? Given eggs with trials, which floor will you drop the egg on the trial (given that no eggs will break even on the highest floor)? x m kth Originally published at code.oursky.com on July 18, 2016. Any comments? Share with us below! 😻 At we’re all about helping brands and entrepreneurs make their ideas happen. Get in touch if you’re looking for a partner to help build your next digital product. Oursky

Google

Microsoft

ORANGE

Yellow

Dissecting the Famous Egg Dropping Puzzle

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

How To Code To Prevent Sensitive Data Exposure

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

How To Code To Prevent Sensitive Data Exposure

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps