Egg Dropping Puzzle with 2 Eggs and 100 Floors || Microsoft Interview Puzzles

I felt like dropping from the 100th floor on seeing solution 4!! 🙆😵‍💫

Didn't he said there are only 2eggs
Nd also i didn't get why binary search approach isn't best solution here

Let's say answer is 100th floor
With binary search
1st drop: 50
2nd drop: 75
3rd drop: 88
4th drop: 94
5th: 97
6th: 99
By 6 drops won't u know the solution?!

Even if the floors increased to 200 no of drops in binary approach increases by 1, where as balanced linear is increased by 6 eggs which is 20 eggs in total
Can anyone explain please.

I got it in 14 steps but with other logic but just slightly different logic

Thank you very much

Actually you can optimize even further.... After the first egg breaks, instead of jumping by 1, jump by 2.

Just using a normal binary search is O(log N) for a 100 that is 7 drops, always.... I don't think this solution is correct like at all

First Floor. It is an egg. If one of the floors is the highest an egg can be dropped without breaking, that floor must be the first floor because no egg is surviving being dropped off the second floor. I still have both eggs intact and I got the job.

Before watching the solution: 14 drops, first drop at floor 15. If the first egg keeps surviving, then 28, 40, 51, 61, 70, 78, 85, 91, 96 (if the first egg survives at floor 96 then just throw it away). Then start the second egg at one above the last known good floor (1 is known good), going up one at a time until it breaks or reaches floor 100 and survives. Maximum 14 drops.

After watching the solution: It's equivalent to what I said, but not quite as clean. The solution given in the video drops at floor 1, but this is pointless because the problem statement guarantees an egg will not break when dropped from floor 1.

How is 50 times the worst case for binary search. Isn't the worst case log 2 n ?

After 1st egg breaks the second can go only even floors:2,4,6...cause if breaks is lower odd number the last :)

break an egg and measure the force. weigh the egg. calculate the hight to make that force.

I will assume that at least one floor is good, therefore floor 1 is at least floor. Not using the floor 2 because I have 2 eggs, therefore using the 3rd floor, if breaks I use the 2nd floor to test it, if breaks it's floor 1, else it's floor 2.
In case at 3rd floor it doesn't break, I would say floor 4.

In 2nd approach, Binary Search, you assumed 1st binary then brute. A complete binary search is 2^n, means worst case number should be 7, not 50.

Am I right to say that there are two equally optimised solutions?
Solution 1, test every 10 levels, followed by every other level within the ten which broke the first egg, excluding the last throw since it will be the 9th within the 10. So total maximum 14 drops.
Solution 2: same thing but do for every twenty levels until the egg broke, and then every other level in the 20, excluding the last, hence 5+9= 14.

I think one thing the answer missed out is if U are testing level 21-30, u only need to drop the second egg on 22, 24, 26, 28. Not required to drop every level.

Oh I just thought of a solution to get answer within maximum 13 steps.

Same as my previous solution of testing every 10 levels, but u only need to test till 98 levels.

So if the egg does not break on 98th, the second egg will help u see if the answer is 99 or 100. If it does breaks at 98th, u only need to test 92>94>96. Hence 13 drops.

Same as my earlier

You are not obligated to deliver second egg intact, so You dont have to check every floor between 1 and 13 - You can drop second egg only from 2, 4, 6, 8, 10, 12 - if it brake, the answer is one floor below.

Although the answer is correct, I think the way you got there is flawed. It assumes the optimal pattern decrements steps by 1. ie. 14, 13, 12, 11... How do we know that pattern is optimal? Seems like dynamic programming is necessary to be confident we have the optimal solution.

There is an error in the last line. Where you put 100 it should say 96-98.

You can take it as 99 floors instead as you will know the answer is the first floor if the egg cracks at the 2nd floor

What kind of egg can stand a 2 floor drop?

Why 2 eggs? You can't solve the worse case scenario by any of the methods mentioned except the Brute Force strategy. And for that, I'd modify that method to drop an egg from every even floor, then when the first egg breaks check the floor below it using the second egg. But if we're going to discuss other methods like Binary Search, why limit the number of eggs instead of making the goal using as few eggs as possible...

my solution without watching video
as the building as 100 floors so it's root is 10
so drop the first egg every 10 floor starting from its bottom until it breaks then let's assume the first floor broke at 60 so the highest floor must be between 50 and 60 so drop it from 51 upto until it breaks so that we could get the highest point
the reason behind choosing the interval of 10 floor as this method requires testing first in interval then continuously so for least outcome we should choose it's root otherwise one of the case will increase the cases unnecessarily

In binary test there would probably be no more than 7 drops (not 50), because after each drop we know which direction to try. 100/2=50, 50/2=25, 25/2=12,5 (assume 13), 13/2=6,5 (assume 7), 7/2=3,5 (assume 4), 4/2=2, 2/2=1 - which makes 7 drops ;)

This problem was very interesting! I was able to find the third solution, but I didn't find the fourth.

I started from the idea of binary search and, given the limitation of two eggs, I imagined the solution was about dividing the floors into intervals, using the first egg to find the correct interval and then use the second egg to scan that interval in a linear way. I started with two intervals (like in the binary search) followed by a linear scan of 50 floors, then I divided it into three intervals with 33-34 floors on each one, and I iterated untill finding the solution of 10 intervals with 10 floors each. I felt that a worst case of 19 drops (attempts) was quite high and there should have been a better solution, but I was stuck into thinking about intervals of the same size, leading to the worth case of egg breaking at floor 99 or 100 requiring 19 drops.

The correct solution to this problem will be definitely part of my bag of coding tricks, especially the idea of using intervals with different sizes; so Thank You.



The problem is not a common scenario I would face at work (maps data structures or binary search on arrays do the job well most of the times when it comes to finding an element), but there could be some situation where the cost of an action (the broken egg of the original problem) is so high that it's best to limit that cost instead, hence the fourth solution.



By the way, I saw some comments stating it wasn't clear this problem was about the worst case. Unless it's explicitly stated, when talking about "computational complexity" (that's the actual subject of the problem, any developer worth is name should have recognized this immediately), it's always about the worst possible case. The goal of the question is too see if the candidate knows the computational complexity subject (that's a given if you interview for a tech position at a big tech company), if he thinks about the performance of his algorithms/solutions (that should be a given as well) and if the candidate finds the best solution (I would have failed because I wasn't able to go past the third solution by myself... my only hope would have been in a few extra points for recognizing that a worst case of 19 attempts for an input of 100 elements is too high and there should have been a better strategy).

Choosing binary search as a solving strategy would be a hard fail of the test because it means the candidate ignored a requirement ("2 broken eggs at most").


In some real life situation, the average cost may be more important than the worst case, because the worst case may be only a theoric one (or it's so rare that it's not really worth considering it, while the time required for the execution in that case is still "acceptable") and/or the cost of the worst case is actually not so bad, especially in comparison to the average case. But this means we have additional informations about the actual input, in order to say so.
For example, if we knew that, out of 200 pair of eggs (each egg of a pair has the same properties, but each pair can be different from the others, so for example a pair breaks at 13 and another pair breaks at 24), about 75% of those pairs breaks before the 40th floor, then maybe a different strategy would be more appropriate (maybe completely tilted towards that 75% in the first 40 floors, disregarding the performance for the remaining 25% in the upper 60 floors? or maybe it's more appropriate to find a balance, slightly more expensive for that 75% but also less punishing towards that remaining 25%?). I didn't do any math about it, but that could be a matter of discussion (and, unless there's a huge difference between the various solutions, usually there's not a clear right or wrong in a situation like this, but it's open to various evaluations).

Anyway, unless implicitly or explicily stated, when facing a problem about computational complexity, always consider it about the worst case scenario.


Just my 2 cents.


And Thank You again for the idea of using intervals with different sizes, that's a really interesting trick!

Good theory and methodology thinking. But practically, egg will break even dropping from worktop, forget about floors 😂

Incorrect solution. The problem asks you to find the highest floor with the conditions stated. You have to guarantee FINDING THE RIGHT FLOOR with only two eggs. Since you have only two eggs and you have to find the right floor, you can only go up in 2 floor increments, so you have to try 2nd, 4th, 6th, 8th floors, etc. in this order, which means in the worst case you have to try 50 drops. Any other solution does not guarantee that you find the right floor with only two eggs. IF you had three eggs INSTEAD (variation of the problem), you would try 4th, 8th, 12th, 16th floors etc. in this order, for example if the first egg breaks on the 4th floor you then try 2nd floor, if that one breaks the second egg you then try the 1st floor in this variation of the problem with 3 eggs.

What if you have 3 or 4 eggs?

Everyone in the comments talking about the puzzle. Me over here thinking that maybe Microsoft ain't the place for me. 🤣

still couldn't understand the optimal solution

The answer is 0 floors, it’s an egg

I think that at 3rd solution, worst case drop count is 18 steps, if it doesn't break from floor 99(18 tries till now) it mean that the breaking floor is 100.

If you drop an egg one flor it breaks

My thought process went to "how many floors could I cover with X egg drops?"

with 3 egg drops, you can start on 3rd floor, if it breaks try on 1st floor and then on 2nd floor.
If it does not break, try 5th floor next, if it breaks go to 4th floor.
If it also does not break on 5th, then go to 6th floor. These 3 options of 3 egg drops each, can be written with the floor numbers below:

3-1-2 (1st egg breaks on floor 3)
3-5-4 (1st egg breaks on floor 5)
3-5-6 (1st egg breaks on floor 6 or does not break, but the 3 drops are done anyway)

Now with 4 egg drops:
4-1-2-3 (1st egg breaks on 4)
4-7-5-6 (1st egg breaks on 7)
4-7-9-8 (1st egg breaks on 9)
4-7-9-10 (1st egg breaks on 10 or does not break, but the 4 drops are done anyway)

3 drops covers 6 floors or 3+2+1=6
4 drops covers 10 floors or 4+3+2+1=10

Easy to know that 14 drops covers 14+13+...+1=105 floors,
but 13 drops only covers 13+12+...+1= 91 floors.

Note: technically you do not need to drop the egg from the 1st floor so, you could say that 14 egg drops covers a 106 floors building

I think you can skip a step. Eg. if 14 is safe and 27 is bust, than skip to 16, if it brakes, than 15 is safe.

But you only have two eggs

Your explaination is superb sir!

There is error in binary search? In binary search, max. number of steps needed should be 7 (which is log2(100) as we always divide interval by two) and not 50.
EDIT: I have realized later that when we have 2 eggs only and we divide original interval 100 by 2 and do a test in floor 50 and the first egg breaks we then proceed with linear search from floor 1 to floor 49 with 1 floor increment. So that is why the worst case if 50 (1 for inital test plus 49 for linear part). It is correct.

You can do this much faster than 14 drops. As shown in the illustration accompanying the video, this “100-floor building” only has windows on 11pf those floors. Those are therefore the only ones it’s possible to drop from. Using the logic you provided, for 11 windowed floors, X rounds up to 5.

Binary search has the worst case scenario of 6, not 50. log2(50) = 6.

Selection of puzzles are good. But,why do you have to explain the question and he solution TWICE with a 10 sec break ??
Ppl. are smart enuf. to rewind and fwd. You can reduce the video length and improve YT search score

Why does the binary search method take 50 drops (in the worst case)? Can anybody explain?

How does binary search gives worst case of 50? shouldn't be log2(n) which is 10?

You are saying there is possibility that an egg would not break if it is dropped.

everybody know the egg will break on the first floor.. so does not make any sense LOL

I didnt get the last part of the 4th solution. When we drop from 99th floor, how is it that we only check the 100th floor and not 98 -> 97 -> 96. Is it because we came to the penultimate floor?

Same question asked by ion interviewer

Probably the best explanation I could ever find!!!