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

#SimplyLogical #MicrosoftInnterview #GoogleInterview

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

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.
There are two eggs Given, find the highest floor an egg can be dropped from without breaking, with as few drops as possible.

Watch The Video For Detailed Solution.
**********************************************************
**********************************************************

Other Viral videos : @Simply Logical

**Interview Puzzles :

**Logical Interview Puzzles - Part1 :

**Logical Interview Puzzles - Part2 :

#SimplyLogical: If you are looking for puzzles, you have come to the right place. We have an extensive library of number puzzles, brainteasers, lateral thinking problems, riddles, Logical Interview Puzzles, and advanced puzzles for geeks and brainiacs. New puzzles are added frequently, so be sure to come back for a new challenge. Did you like solving these puzzles? Do let me know your experience, suggestions & solutions in the comments below. I am excited to see if you can think any differently! Do you think you have solved the hardest of riddles already? Then you need to look at the puzzles YouTube playlist brought to you by Simply Logical. They sure will give you a tough time solving them. Take your time and sit comfortably on your couch while you try to solve the following Hard Puzzles. When you are done with all of them, watch the video for the solution.

[freezefrancis]

Probably the best explanation I could ever find!!!

[KenPaulsenArchitect]

Based on experience, dropping an egg from a countertop, I'd immediately conclude that dropping an egg from the first floor would cause a break. So I'd start at the 2nd floor wherein upon it breaking I'd know floor 1 is the expected answer.

[birchgarden]

As a bonus, there is an advanced optimized thinking to this: Once you reached the 90th floor with your 9th attempt and the eggs still haven't broken, you can introduce a new linear deviation to guarantee results within 13 attempts, by going 90 (9th step) -> 94 -> 97 -> 99 -> 100 (13th step). You can only do this 10% of the time, but it kinda does justice to the x = 13.651 steps.

[sampsunsmith]

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

[markkreitler]

Found the justification for solution 4 a bit confusing at first. It helped to think of it this way: in the 3rd solution with 10 divisions of equal size, your best case solution might require 10 drops, while your worst case requires 19. How could you divide up the floors so that all your segments had the same maximum number of drops? In this case, the lowest segment has the most floors, since you use 1 drop to learn the egg breaks in the first division. The second lowest segment will have 1 less floor because you used 2 drops to learn the egg breaks in the second segment, etc.

[kunalbandooni]

The BEST EXPLANATION which went from NOOB -> PRO in 9 minutes. Loved your photos for reference too. Really great work!!

[GregCannon]

It wasn't stated in the question that we're solving for the worst case. In the average case, the answer is 10.3 drops, solved with dynamic programming. The best initial drop would be the 15th floor, which narrows it down to either 14 with one egg (EV = 7.428 drops), or 86 with two eggs (EV = 9.605 drops).

Interestingly, the first floor to drop from isn't strictly increasing. For example, with 49 floors, the best first drop is the 11th floor. But 50 floors, the best first drop is the 10th floor!

Very interesting puzzle.

[ploughable]

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.

[butlazgazempropan-butank]

I wonder how the numbers would change if you used an averege instead a worst case.

[sammason]

If i was asked this question in an interview i would have assumed it was a trick question. Of course the egg will break when dropped from the first floor. Great explanation of the mathematics though

[zendruoflynstin]

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.

[KicKandRoll]

Very nice explantion of how to search with a computer. Only thing i miss are the assumtions, like the possibility of an egg breaking is equal to each floor and we have to optimize for the worst case.
If we assume to do it in real life, the Brute force method is the best, because the egg will break dirctly on floor 0/1 or at the latest 1/2 (depending if you count the ground floor as 0 or 1)

As you said, this is an interview question, the solution should be to impress the interviewer as much as possible.
So after you explaination (which probably is what any IT comany like Microsoft wanna hear) bonus points could be aquired by asking about project management. First lesson anybody learns for procet management should be to to ask questions, until the goal is absolutly clear and reach it, instead of making own assumtions.
So with asking aboutthe goal of likely cases or the worst case is preffered, one can not only show understanding of logic but also project management.

My personal favorite answer without beeing able to clarify the optimization goal, would be to start from floor 2 (if 1 is the first floor). If the egg breaks, i drop it from floor 1 ans see if it also breaks. Because i have not the same assumtion, that i will definitly find the floor from which it will not break or that eggs are hard to break. In that case, i needed 2 drops, to show, the case is not solvable. If the egg does not break, i do the brute force and are likely to find a fast solution, because eggs do break fast.
If the small change occurs, that we got some undestroyable eggs, at least i did not offer the worst solution. And more important, it is unlikly someone wrote something about an answer to start from floor 2. This is important, because, in a predefined question, they will already have prepared answers of their own and brute force is probaly marked as the worst solution. So if i say Brute force is the best but the interviewer beforehand decided it is the worst, i will have a hard time. But if i just argue about my own solution, the likelyhood for acceptance is higher and if i explain that, i can show, that i am both willing to compromise on my own ideas to some degree and can also can account for human behaveiour.
I assume my answer to be prefarable, if the interview is about any job that also need requirement engineering or leads other people, with the answer from video be better, if i wanna be a code guy, who does nothing but coding. Which is one more assumtion that should be clear.

P.S.
I have one more assumption:
You have probaly groaned by reading the word assumtion again and also sufferd because of my bad english.
I am sorry for the english part and as an optimistic person, i do not wish but just assume, you have a good day anyway

[eagleyefly]

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

[idontwantanusername]

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!

[birchgarden]

I first arrived at solution 2 but upon looking at the first words from solution 3, I arrived quickly at solution 3, then thought about it another 30 min and found solution 4. Good puzzle.

[roccov]

0:36 seconds in and I paused the video to give it a go. It was a lot more fun than I thought. I'm not mathematically inclined so I worked it out in Excel. I got an answer of 14 as the maximum number of tries to guarantee finding the solution.

Now to finish watching the video. I'm suspecting I'll see some math.

[andrevth]

Wow a alternative explanation than the one offered in Ted Ed video 🙏

[verkuilb]

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.

[VikramSingh-lesy]

I was finding difficult to understand the logic, you made it very clear thanks for the detailed explanation

[Turn.toJesus]

I got 13.
I used your same logic, but you DONT need to drop the last egg.
Looking at your illustration, if you drop at 14, then go to 1, 2, 3, 4...you can stop at 12, there is no need to drop at 13