9:20 , 100 is not necceserily an answer if it didn't break on 99th, 99 can be the answer if it broke on 100. 100 only gives the final answer but not need to be the result.
You don’t need to check the lowest floor of a series, since the question guaranteed there is a safe drop floor. Example, if the egg broke on floor 10, then just check floors 2-9. If it survives you know the answer is floor 1, no need to check.
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.
@@MrPetrovita The condition for 13 steps only applies if the eggs don't break on the 90th floor. If one does up to the 90th floor, you follow the pattern in the video for a 14 steps scenario (7:36).
@@mahadevparmekar2565 Well it's a conditional improvement. With the way described in the video you're guaranteed 14 and in a very lucky case also get 12, but the spirit of the whole exercise here is to go further and look deeper and deeper to find the optimizations even if it means to do them midway if given the opportunity.
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.
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.
I think best case in 3rd solution actually needs just two drops. You drop egg at floor 10 and it breaks so you start with linear search of floors 1 to 9. You drop egg at floor 1 and it breaks immediately, so result is 0 (meaning not even 1st floor is safe for an egg). What you were talking about (10 drops) is worst case for best case segment :-)
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.
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
but you don't know how high is the building, for all you know it could be very small where dropping it from 1st floor is like 1mm height where egg can actually survive
@@emeraldday4755 Yes, but if you're going to say that normal assumptions don't apply then I'm going to imagine that the whole building exists on a planet with a much higher gravity than earth such that even a 1mm fall would break the egg
@@sammason2300 no asumptions apply, by assuming anything you just failed the assignment. You have only so much info and your answer needs to be based on that. You are not the quest giver so you dont dictate the specifics.
@@emeraldday4755 Lots of assumptions are implied. For instance, that gravity exists, that the egg is a hens' egg (rather than a flea egg which would just blow away in the wind) or that every floor in the building has windows. If you want to treat a candidate on pure logic without any implied assumptions then just ask a purely mathematical question
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
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
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.
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.
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
There is no need to drop at 1 since if second egg breaks at 2 you know 1 is the answer while if it doesn't break at 2 then you know implicitly that it wouldn't have at 1 either so if you're lucky first breaks at 14 you only need 13 in total.
@@jimsteinmanfan80you're right. The problem states there is a non egg breaking floor. If the egg breaks on the first floor then no such floor exists making the entire premise invalid. Therefore the first floor need never be tested.
No, if at 99 it doesn't break the answer is 99, but if at 99 it does break, then drop at 97 - if it breaks, the answer is 96, if it doesn't, 97. So 11 or 12 drops.
@@DonaldFranciszekTuskIt could be that it doesn’t break at 100, so you have to test it. The rule says: One of the floors is the highest floor an egg can be dropped without breaking. This could be floor 100. There is no rule that the highest floor does break the egg. Then for testing after a break, all other smart people needed to step up one by one, except you. Please give a reason.😀
@@DonaldFranciszekTusk Sure that‘s what one thinks, but read the rules carefully, if you care, and try to pinpoint the location in the video, which supports your claim.
Can we do step3 and step2 together to find the answer. Divde a little Conqure more (3:47) instead of 10, we can use 20. So possible options are 20,40,60,80,100. Then do binary search (3:13) if am taking 20 and 40... Possible options are 30(20-40),25(20-30),23(20-25),21.. So total options are 5+4=9 or10 (if there is any mistake in my last step) Please correct if am wrong
by doing this method we may lost 2eggs before finding the height let us consider divide little conqure by 20,40,60,80,100 consider that egg breaks at 80 we have totallly 4 drops so between 60-80 the maximum worst case 19 and when ever we use binary search we must hold mininum of 2 egg because in this case we have only one egg left and maximum height is acheived only when egg is broken in this case ,for binary search if we choose 65 floor and if egg broken we dont have eggs to find to floor between 60-65
@@bjbboy71697there is no way to find it with just 2 eggs. Even the solution in the video is assuming an infinite number of eggs. Binary search is the method with minimum number of drops i.e 7
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.
Worst case is when the first breaking floor is the 50th floor. With binary search, you start at 50th floor (mid) and the egg breaks. Now you have to check all the floors from 1 to 49 with the second egg. You will have to do this linearly because this is your last egg. So you start from the very bottom and drop from all 49 floors. So 49 drops here + 1 drop with the first egg = 50 worst case 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!
I understand why the solution works but not why this is a minimized solution. After 5:58 i simply don‘t understand what you are talking and why you are going on with the sequence x + (x-1) + (x-2) + … as being the minimized solution. There is no mathematical Formular to support that and if you explained it with words in that section i didn‘t understand them … sadly there are no subtitles. Can someone summarize why this is supposed to be the best solution.
What happens is if you guess 14 and it breaks you can't take any more chances with your last egg, so you check the floors one by one. So, the worst case is you have to check all 14 floors. If it survives 14 and you decide to just add 14 again and try 28, if it breaks, you'll have to play it safe and check 15 to 27 one by one. That's another 14 floors you have to check but you also checked 14 so the worst case you have to check 15 levels. If it doesn't break at 28 and you add 14 again, again the worst case will be 16. So, to avoid the worst case going up by one every time you drop an egg, and it doesn't break, you minus 1 from the next level. So, if it does break, the worst case is still the same. And the reason it's 14 and not 13 is because if you do the same trick with 13, adding 12 then 11 then 10 floor increments etc. you'll reach a step size of 0 before you reach 100. I believe the numbers from 13 to 1 add up to 91. So, 13 is too small. Hope that helps.
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.
So I thought the same, but this isn't finding the floor with any number of eggs. Given you have 2 eggs, your egg could break in the 2nd try and you only have a range, and have narrowed it down to only a 4th of the space, that is still 25 floors to evaluate, but no eggs left.
It's so easy. Just figure out the aerodynamics of the egg, the gravity of the planet that the building is on, the distance between floors, and get a board. Keep hitting the egg with increasing force equivalent to dropping it from the next floor until the egg breaks. There you go... Zero drops!
I thought so too but it’s actually not true. If you drop at floor 95 no break, then 99and it breaks, u can’t drop at 97 because if it breaks u won’t have another egg to test if floor 96 will break.
No you cant. If you drop it at 1st floor and it doesnt break but when you drop it at 3rd it breaks, you wont be able to tell if it breaks at 2nd floor or not.
You can't skip second @@lsrrr3857 but you can skip first (even though that only makes it 14-1=13, not 12 as stated). If first egg breaks at 14 then if second egg breaks at 2 you know 1 is the answer while if it doesn't break at 2 then you know implicitly that it wouldn't have at 1 either.
It's true if the first breaks at 14 @@longformconversations. Then you can skip 1 as if second egg breaks at 2 you know 1 is the answer while if it doesn't break at 2 then you know implicitly that it wouldn't have at 1 either.
2 minor nitpicks: If the egg breaks when dropped from the 99th floor you still have to test the other egg from 96, 97 and 98. And when it does not break you do have to test from the 100th,. because when that breaks 99 is the answer and not 100. But crucially, you can omit testing for the 1st floor! Because it is given that there is a floor that the egg won't break from, and the 1st floor will either be that floor or below it. So the highest floor you can test for with n tries is n(n + 1)/2 + 1; with n=14 that is 106.
@@kamalaparkerballs It is the other way round; if it does not break at the 99th you still have to test it at the 100th, because it may break there and then 99 is the answer ;)
@@barttemolder3405If theres only 100 floors and the egg will break at one of them and 99 is not that floor then you don’t need to check 100 because by process of elimination its the only one left so it must be the answer
@@richb1576 But you don't know for certain that it will break from the 100th floor. The only thing you know for certain is that there's a highest floor from which it does not break. And that floor could be the 99th or the 100th, so you have to test the 100th floor too if it does not break from the 99th.
Ok So the highest floor means it wont break at any floor below it. There are only 100 floors and it will break at one of them. If it does not break at floor 50 then it will not break at any floor below that. If it does not break at floor 99. It will not break at any floor below that. Since we know there are only 100 floors and since we know it will break at one of those floors and we know that it did not break at floor 99 the only answer is floor 100 and that does not need to be tested.
@@richb1576 Not OK. You take it for a fact that there is a floor that the egg will break from. But the puzzle does not say that. It says "One of the floors is the highest floor an egg can be dropped from without breaking." There's no reason why that can't be the top floor. So that is a possibility that you must take into account.
Jst a thought ,every time u drop the egg with out breaking it ..THE STRUCTURAL INTEGRITY will be compromised causing the that egg to break bfr the full impact strength can be properly discovered..so resulting in a egg that u dropped a few time will break bfr at a lower elevation then a fresh egg ..just a thought ..love u all ,have great day
You didn't listen to the problem statement properly. Clever 'real-world' gotchas are irrelevant in logic puzzles and only show you don't understand the purpose of the exercise
Since the egg has a chance of not breaking from the first floor we must assume that they are unlike any other eggs found on planet earth . These would make them extremely valuable and to break even one would be an irresponsible act . They must be treasured instead .
This is quite interesting, I reached the 10 floor step solution and wondere if there was a better solution, I suspected it was but, given that the worse case is quite unlikely I actually thought, probably is better to not waste resources trying to find a better solution for the unlikely worse case...
I explored all 99 cases for the last floor from which an egg falls safely. The worst case is quite often. Using 2 eggs means 196 times 14 trials and 247 times 13 trials. In the split shown in the video, it is even more, the total number of trials for all cases will be 115 more. Because i start with max. 13 trials from 2nd floor on floor 14, followed by 12 trials between 15 and 26 .... and use the 7-floor step 2 times for reaching the 99. I think it is useful to accept the conditions of the riddle. Because it is only a mind game. So why should we argue with practical reasons?
No, if at 99 it doesn't break the answer is 99, but if at 99 it does break, then drop at 97 - if it breaks, the answer is 96, if it doesn't, 97. So 11 or 12 drops.
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.
oh that's how it is. thx mate i was confused why we took that expression x + (x-1) + (x+2) .. but now i know we are deducting the jumps count from next x floors that will ensure that we will get ans in x steps and also making the sum of seires such that it reaches last floor.
The question is what is the number of drops that you can definitely solve the problem in. Say the building only lets you use the lift 14 times. Now you know that you can solve the problem no matter what the answer is.
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.
The puzzle is beautiful but the assignment is terrible. Is the maximum possible drops or average possible drops supposed to be minimal? All I can say now is that the minimum is two. Another issue with the assignment is that it does not say whether the floor can be 100. Anyway. If it's about minimizing maximum number of drops, then I will go for 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 96, 97, 98 and if it broke in one of the midle ones, then I go one by one next. So the maximum drops would be 13. I am gonna continue watching the video now.
@sebastianki-t2m I see. Thanks. I never finished watching the video. I just closed it thinking I was obviously right. I feel like I was thinkining I dont need to check the 26th floor because if it does not break at 25, it's gonna be 26. But obviously I would still not know whether it's 27 or 26. No idea what made me think that.
I found the explanation of the math behind solution 4 quite confusing, as x seems to be both the step interval and the number of steps and I don't understand what x+(x-1) refers to. If x is the fixed step interval (measured in number of floors) for the first egg drop and n is the total number of floors, then the worst case scenario (i.e the breaking floor being n-1) is (n/x)+(x-1) This is because (n/x) is the maximum number of drops to figure out that the egg must break somewhere between floor n-x+1 and and floor n, and (x-1) is the number of times we have to drop the second egg to figure out that the egg breaks at floor n-1. So I really don't understand where the x+(x-1) comes from.
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.
Let's be honest, this is an example where mathematics and the real world have a breakdown. The egg is going to break in less than 14 floors, therefore the brute force method will result in a best result every time when tested in the real world. The mathematics being used also fail badly when you have an infinitely tall building. My proposal would be to estimate the break chance, and then select the method based on that. For example if we are using eggs I'd estimate that the floor will be very low. I'd likely then test on floor 3, if it breaks move to floor 2, and then if that breaks I know my answer is floor 1 (assuming that there is a floor where the egg won't break and the answer can't be 0). If it didn't break on floor three then I can move to floor 5, then four if it breaks on 5 or 7 if it doesn't break. This lets me test all the way up to floor 25 in less than 14 drops. It will also get an answer faster than the brute force unless the answer is one or two, and it doesn't run into a problem of being less efficient on a taller building. If we were using something tougher, then balancing linear drops would likely be a better answer, but it isn't on something like an egg. It kind of makes me think that Google is using this as a trick question, the best answer is someone that can explain why balancing linear drops looks best but really isn't, and then propose something that is still better than brute force.
Now solve the reverse question. What is the maximum number of storeys a building can have in order for you to find the highest floor in that building from which an egg can be dropped safely given the fact that you are only allowed a total of X drops and you start with 2 eggs :)
I understand the sum. We have X tries. So, we drop the egg from the X floor. Regardless of the outcome, we will have (X-1) tries remaining. Then (x-2) .... until we are left with only one try. But what does the +1 in front of the sum represent?@@d6ftg7yhu
To minimize the number of drop is always take under root of the total number of floor. And divide the floor according to that to drop the egg..and then follow below.. If egg didn't crack, move to the another group level until egg crack. Once the egg crack start dropping egg from 1st level of that spicific group.. This solution is not only helpful for 100 floors. But also for any other highest floors..like 500... Example - if the building has 500 floor. As we know there is no perfect under root of 500.. We ll consider the nearest round off value. For 500 floor, we ll group the floors in set of 22. First drop from 22, if 1st egg crack then start from 1St floor and move upward until it 2nd egg cracks. If 1st didnot crack at 22 floor. Then go to 44 floor and drop. If it cracks then start dropping 2nd egg from 23 floor until crack... We can use the same formula for 100/200/300 or any other floor.. ..
1 drop, take the egg to the elevator on the 100th floor, step into the elevator and ride (drop) it to the ground floor. In this scenario, the egg will not break and you are done in one step. Lack of specificity in the scenario allows for creative out-side the box thinking and solutions. ;)
What about dividing every every drop by 50% of floors for each drop. 1st egg drop at floor 50 (Doesn't break) 2nd egg drop between 50 and 100 (so floor 75) So forth. You'd end up using 7 drops of you keep dividing the target area by 50%
Thanks for your comment. Your approach valid for best cases and breaks in worst case scenarios. What if egg bread @ 50th floor and breaks again @ 25th floor ?
@@SimplyLogical So, If it breaks at floor 50, then you move on to test the lower 50%. If it breaks at 25, then you drop at 50% (or close) if that, so drop the egg at floor 13. If it doesn't break, now you devide 50% between floors 13 and 25 and thats where the next drop would be (floor 19) and drop from there. Eventually when you keep splitting possible area, you've only used 7 eggs. It works the same if you move either up or down.
@@adriang6672 you're assuming you have an infinite number of eggs, but you don't, you only have 2. Like he explained in the video, if you drop at 50 and it breaks, you're left with one egg. Then you say to drop at 25, and if it breaks there, you have no more eggs, and you still don't know what is the highest floor you can drop an egg at, since you still have 24 floors left to check.
@@dorondavid4698 I think his point is. The worst case scenarios for binary search where @Adrian G is pointing out should be 7 trials instead of 50 trials.
The answer...1 drops. I've sat on my eats for 8 weeks, until 2 chicks have hatched, waiting 3 months until they have full feathers and what both chickens from the top floor hover gracefully to the ground.....
There are some little adjustments to improve Your solution. By the way, in the table is a mistake: If egg breaks from 99th floor, not 100th need to be checked, but 96, 97, 98. So we find up to 14 trials, too. From 100th floor the egg will break because the given information includes there is a level from which the egg will break. At least it is the top. Further we do not need to test the 1st floor because there is a level from which the egg will fall safely. At least this is the lowest one. With we steps 14, 13, 12 and so on we could reach a testing range of 105 floors, but we only need 98 to be checked. So we have 7 floors free to bring down the number of trials. I prefer to make the first 7 tests shorter by 1: Place 1st egg on 14, 26, 37, 47, 56, 64, 71, (and now again a 7-floor-step to) 78, 84, 89, 93, 96, 98, 99. If each case of the floor which is highest level for an unbroken egg (1, 2, 3, ..... 99) occurs once, 1015 trials will be necessary. This is an average of nearly 10.3. And 195 eggs will break during all these performances. I explored how the process will change by using 3 eggs. I found 734 trials for all of these cases with 242 broken eggs. And finally with 4 eggs, my chosen splitting showed 672 trials using 294 eggs. Thank You for this interesting puzzle ☺
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.
use a bit of physics first. An egg has a terminal velocity of 35m/s which is a 60m free fall (all roughly) Assuming a floor being 3m, the impact speed will not change after floor 20. So you only need to check the first 20 floors...
I start dropping on floor 1. Because I know the egg won't survive a two-story drop. It's an egg. Math is nice. But experience trumps math in engineering.
you are not getting it. If the egg does not break, you can use it again. The solution provided guarantee you finding the level with at most 2 broken eggs, while binary division can leave up to 7 eggs broken
So THIS is what the egg-heads at Microsoft is wasting time on instead of making correct software? What about moving the "Delete" option in the right-click popup menu in file explorer AS FAR AWAY AS POSSIBLE from the "Copy" choice instead of putting it right beside the "Copy" option?
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
I’m not going to do the calcs here but, even if you have 100 eggs 1 try would never suffice of course, U mean there should be a minimum number of tries regardless of the number of eggs, so there should be a MC number of eggs beyond which other eggs are useless , it turn out 3 eggs require max 8 drops, 4 eggs 7 drops , 5 eggs 5 drops. So 5 is the minim drops in absolute, because 6 eggs cannot do better than 5 drops, otherwise if let’s say 4 drops are the solution to 6 eggs, than 4 would be the solution for 4 eggs too, which is not
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.
@@bjbboy71697 if you check (the twelves) and it doesn’t break you then move up to the 2’s if it breaks on 2 then the one before must be safe moving up by two each time if it breaks then the safe one must be the odd number prior. The twelves also mean that only 3-4 need to be checked on every alternate round
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?
My solution was to drop eggs from all even numbers, and once it breaks, then second egg from previous odd number. But the answer is definitely more mathematically accurate.
While your demonstration was good, the actual maw tries is one less:13. You do not need to perform a test if you already narrowed down to one remaining floor...
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...
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.
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.
I'm not entirely sure that the 3rd is the best solution -- Given the predicate knowledge we are talking about eggs, that would suggest the lower number of floors more likely , and the third oulution should be reversed , ie minimum steps first to give a higher probablility of reaching the answer quicker. maybe if eggs were hollow steel fo instance this would be wrong...
Probably the best explanation I could ever find!!!
9:20 , 100 is not necceserily an answer if it didn't break on 99th, 99 can be the answer if it broke on 100. 100 only gives the final answer but not need to be the result.
@@TymexComputing Has no any infulence on correct result.
Nah this was garbage
You don’t need to check the lowest floor of a series, since the question guaranteed there is a safe drop floor.
Example, if the egg broke on floor 10, then just check floors 2-9. If it survives you know the answer is floor 1, no need to check.
So worst case is actually 13 drops, not 14 that the video says.
Everyone in the comments talking about the puzzle. Me over here thinking that maybe Microsoft ain't the place for me. 🤣
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.
You can't guarantee 13 steps that way. What if the egg breaks on the 90th floor? Then you will have 18 steps to the solution.
@@MrPetrovita The condition for 13 steps only applies if the eggs don't break on the 90th floor. If one does up to the 90th floor, you follow the pattern in the video for a 14 steps scenario (7:36).
even better optimisation mathematically was taking x(x+1)/2=99 instead of 100. x would be then 13.580, 14 steps either ways.
The worst case scenario is still 14. So, it doesn't improve on the solution.
@@mahadevparmekar2565 Well it's a conditional improvement. With the way described in the video you're guaranteed 14 and in a very lucky case also get 12, but the spirit of the whole exercise here is to go further and look deeper and deeper to find the optimizations even if it means to do them midway if given the opportunity.
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.
Welcome to Microsoft.
Zero-based array index. Floor 1 is not assumed to be safe.
@@alish2950 😂
That is quite evident form your profile photo.
@@mattiullah9676 Looks can be deceiving. (Don't judge a book by its cover.)
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.
yup it was only after coming to same conclusion that I realised what “balancing linear” means!
nice explanation
I think best case in 3rd solution actually needs just two drops. You drop egg at floor 10 and it breaks so you start with linear search of floors 1 to 9. You drop egg at floor 1 and it breaks immediately, so result is 0 (meaning not even 1st floor is safe for an egg). What you were talking about (10 drops) is worst case for best case segment :-)
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.
This question is stupid, eggs would break on floor one.
no, stupid is to throw eggs out the window and then call stupid those who do the same at the floor above
The BEST EXPLANATION which went from NOOB -> PRO in 9 minutes. Loved your photos for reference too. Really great work!!
I wonder how the numbers would change if you used an averege instead a worst case.
Then probably still the balancing linear drops would be the best solution.
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
but you don't know how high is the building, for all you know it could be very small where dropping it from 1st floor is like 1mm height where egg can actually survive
@@emeraldday4755 Yes, but if you're going to say that normal assumptions don't apply then I'm going to imagine that the whole building exists on a planet with a much higher gravity than earth such that even a 1mm fall would break the egg
@@sammason2300 no asumptions apply, by assuming anything you just failed the assignment. You have only so much info and your answer needs to be based on that. You are not the quest giver so you dont dictate the specifics.
@@emeraldday4755 Lots of assumptions are implied. For instance, that gravity exists, that the egg is a hens' egg (rather than a flea egg which would just blow away in the wind) or that every floor in the building has windows.
If you want to treat a candidate on pure logic without any implied assumptions then just ask a purely mathematical question
If these eggs can survive a fall from even one floor , it's much more important to try to hatch them and see what kind of Super Chicken emerges .
Exactly what I was thinking. Also what material are they dropping an egg onto? Eggs are famously bad at not breaking.
Most practical answer I've heard😂
😂😂😂
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
Then u must be smart enough to forward the video too.
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
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.
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.
Your explanation is so comprehensive!
I was finding difficult to understand the logic , you made it very clear thanks for the detailed explanation
Good theory and methodology thinking. But practically, egg will break even dropping from worktop, forget about floors 😂
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
Then how can you tell if the egg breaks at 13 or 14? because for both cases they will break at 14 and not break at 12
@@lsrrr3857😳I humbly stand corrected
There is no need to drop at 1 since if second egg breaks at 2 you know 1 is the answer while if it doesn't break at 2 then you know implicitly that it wouldn't have at 1 either so if you're lucky first breaks at 14 you only need 13 in total.
True, except the worst-case scenario is still 14. But you are right, you only need 13 drops for that first line.@@jimsteinmanfan80
@@jimsteinmanfan80you're right. The problem states there is a non egg breaking floor. If the egg breaks on the first floor then no such floor exists making the entire premise invalid. Therefore the first floor need never be tested.
9:09 The so called perfect solution table omits the checks of 96, 97 and 98 after the egg breaks at 99
No, if at 99 it doesn't break the answer is 99, but if at 99 it does break, then drop at 97 - if it breaks, the answer is 96, if it doesn't, 97.
So 11 or 12 drops.
@@DonaldFranciszekTuskIt could be that it doesn’t break at 100, so you have to test it. The rule says: One of the floors is the highest floor an egg can be dropped without breaking. This could be floor 100. There is no rule that the highest floor does break the egg. Then for testing after a break, all other smart people needed to step up one by one, except you. Please give a reason.😀
@@DasHemdchen No, the question suppose that eggs can break from at least one floor, the floor 100.
@@DonaldFranciszekTusk Sure that‘s what one thinks, but read the rules carefully, if you care, and try to pinpoint the location in the video, which supports your claim.
Really very good explanation
Can we do step3 and step2 together to find the answer. Divde a little Conqure more (3:47) instead of 10, we can use 20. So possible options are 20,40,60,80,100. Then do binary search (3:13) if am taking 20 and 40... Possible options are 30(20-40),25(20-30),23(20-25),21.. So total options are 5+4=9 or10 (if there is any mistake in my last step)
Please correct if am wrong
by doing this method we may lost 2eggs before finding the height let us consider divide little conqure by 20,40,60,80,100 consider that egg breaks at 80 we have totallly 4 drops so between 60-80 the maximum worst case 19 and when ever we use binary search we must hold mininum of 2 egg because in this case we have only one egg left and maximum height is acheived only when egg is broken in this case ,for binary search if we choose 65 floor and if egg broken we dont have eggs to find to floor between 60-65
Yeah your assuming infinite eggs. In which case you should just binary search the whole thing guaranteeing the answer in 7 drops.
@@bjbboy71697there is no way to find it with just 2 eggs. Even the solution in the video is assuming an infinite number of eggs.
Binary search is the method with minimum number of drops i.e 7
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.
@@amitgaur9324 No, it doesn't provide all possible exact answers.
Why does the binary search method take 50 drops (in the worst case)? Can anybody explain?
Worst case is when the first breaking floor is the 50th floor. With binary search, you start at 50th floor (mid) and the egg breaks. Now you have to check all the floors from 1 to 49 with the second egg. You will have to do this linearly because this is your last egg. So you start from the very bottom and drop from all 49 floors. So 49 drops here + 1 drop with the first egg = 50 worst case drops
Wow a alternative explanation than the one offered in Ted Ed video 🙏
Your explaination is superb sir!
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!
Hey! Can you explain in your words why are we using intervals with different sizes ? I like the way you write and think
Very good explanation! Subscribed right away
I understand why the solution works but not why this is a minimized solution. After 5:58 i simply don‘t understand what you are talking and why you are going on with the sequence x + (x-1) + (x-2) + … as being the minimized solution.
There is no mathematical Formular to support that and if you explained it with words in that section i didn‘t understand them … sadly there are no subtitles. Can someone summarize why this is supposed to be the best solution.
What happens is if you guess 14 and it breaks you can't take any more chances with your last egg, so you check the floors one by one. So, the worst case is you have to check all 14 floors. If it survives 14 and you decide to just add 14 again and try 28, if it breaks, you'll have to play it safe and check 15 to 27 one by one. That's another 14 floors you have to check but you also checked 14 so the worst case you have to check 15 levels. If it doesn't break at 28 and you add 14 again, again the worst case will be 16. So, to avoid the worst case going up by one every time you drop an egg, and it doesn't break, you minus 1 from the next level. So, if it does break, the worst case is still the same.
And the reason it's 14 and not 13 is because if you do the same trick with 13, adding 12 then 11 then 10 floor increments etc. you'll reach a step size of 0 before you reach 100. I believe the numbers from 13 to 1 add up to 91. So, 13 is too small. Hope that helps.
Thank you very much
brilliant explanation
Thanks for ur explanation👍
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.
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.
So I thought the same, but this isn't finding the floor with any number of eggs. Given you have 2 eggs, your egg could break in the 2nd try and you only have a range, and have narrowed it down to only a 4th of the space, that is still 25 floors to evaluate, but no eggs left.
It's so easy. Just figure out the aerodynamics of the egg, the gravity of the planet that the building is on, the distance between floors, and get a board. Keep hitting the egg with increasing force equivalent to dropping it from the next floor until the egg breaks. There you go... Zero drops!
You don't have to drop the 2nd egg at every floor. you can skip 1 floor. Hence you can optimise it to 12 steps
I thought so too but it’s actually not true. If you drop at floor 95 no break, then 99and it breaks, u can’t drop at 97 because if it breaks u won’t have another egg to test if floor 96 will break.
No you cant. If you drop it at 1st floor and it doesnt break but when you drop it at 3rd it breaks, you wont be able to tell if it breaks at 2nd floor or not.
You can't skip second @@lsrrr3857 but you can skip first (even though that only makes it 14-1=13, not 12 as stated). If first egg breaks at 14 then if second egg breaks at 2 you know 1 is the answer while if it doesn't break at 2 then you know implicitly that it wouldn't have at 1 either.
It's true if the first breaks at 14 @@longformconversations. Then you can skip 1 as if second egg breaks at 2 you know 1 is the answer while if it doesn't break at 2 then you know implicitly that it wouldn't have at 1 either.
True,. Worst-case is still 14 though.@@jimsteinmanfan80
2 minor nitpicks: If the egg breaks when dropped from the 99th floor you still have to test the other egg from 96, 97 and 98. And when it does not break you do have to test from the 100th,. because when that breaks 99 is the answer and not 100.
But crucially, you can omit testing for the 1st floor! Because it is given that there is a floor that the egg won't break from, and the 1st floor will either be that floor or below it. So the highest floor you can test for with n tries is n(n + 1)/2 + 1; with n=14 that is 106.
@@kamalaparkerballs It is the other way round; if it does not break at the 99th you still have to test it at the 100th, because it may break there and then 99 is the answer ;)
@@barttemolder3405If theres only 100 floors and the egg will break at one of them and 99 is not that floor then you don’t need to check 100 because by process of elimination its the only one left so it must be the answer
@@richb1576 But you don't know for certain that it will break from the 100th floor. The only thing you know for certain is that there's a highest floor from which it does not break. And that floor could be the 99th or the 100th, so you have to test the 100th floor too if it does not break from the 99th.
Ok
So the highest floor means it wont break at any floor below it.
There are only 100 floors and it will break at one of them.
If it does not break at floor 50 then it will not break at any floor below that.
If it does not break at floor 99. It will not break at any floor below that.
Since we know there are only 100 floors and since we know it will break at one of those floors and we know that it did not break at floor 99 the only answer is floor 100 and that does not need to be tested.
@@richb1576 Not OK. You take it for a fact that there is a floor that the egg will break from.
But the puzzle does not say that. It says "One of the floors is the highest floor an egg can be dropped from without breaking." There's no reason why that can't be the top floor. So that is a possibility that you must take into account.
Jst a thought ,every time u drop the egg with out breaking it ..THE STRUCTURAL INTEGRITY will be compromised causing the that egg to break bfr the full impact strength can be properly discovered..so resulting in a egg that u dropped a few time will break bfr at a lower elevation then a fresh egg ..just a thought ..love u all ,have great day
no mames
That's an engineer's answer to a maths question.
You didn't listen to the problem statement properly. Clever 'real-world' gotchas are irrelevant in logic puzzles and only show you don't understand the purpose of the exercise
Since the egg has a chance of not breaking from the first floor we must assume that they are unlike any other eggs found on planet earth . These would make them extremely valuable and to break even one would be an irresponsible act . They must be treasured instead .
This is quite interesting, I reached the 10 floor step solution and wondere if there was a better solution, I suspected it was but, given that the worse case is quite unlikely I actually thought, probably is better to not waste resources trying to find a better solution for the unlikely worse case...
The difference between 20 and 14 is not that extreme and the algo is simpler and easier to understand.
I explored all 99 cases for the last floor from which an egg falls safely.
The worst case is quite often. Using 2 eggs means 196 times 14 trials and 247 times 13 trials. In the split shown in the video, it is even more, the total number of trials for all cases will be 115 more. Because i start with max. 13 trials from 2nd floor on floor 14, followed by 12 trials between 15 and 26 .... and use the 7-floor step 2 times for reaching the 99.
I think it is useful to accept the conditions of the riddle. Because it is only a mind game. So why should we argue with practical reasons?
Can we implement binary search
What if you have 3 or 4 eggs?
You deserves more views and subscribers
i think last row in final solution table shall be 99 : 96 -> 97 -> 98 drops : 11 + 3 (if the actual floor is 98)
No, if at 99 it doesn't break the answer is 99, but if at 99 it does break, then drop at 97 - if it breaks, the answer is 96, if it doesn't, 97.
So 11 or 12 drops.
Dont test first floor, x(x+1)/2=99 is good to go. Mathematically more accurate even thought the number of min drops would still be 14.
Optimizing for worst case; Should you not to optimize for average case?
You are the best
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.
Great video!!
oh that's how it is. thx mate i was confused why we took that expression x + (x-1) + (x+2) ..
but now i know we are deducting the jumps count from next x floors that will ensure that we will get ans in x steps
and also making the sum of seires such that it reaches last floor.
The last solution is applied with Gauss summation, right?
why optimize the max amount of drops to be as low as possible? we should be maximizing the average amount of drops to be as low as possible.
The question is what is the number of drops that you can definitely solve the problem in. Say the building only lets you use the lift 14 times. Now you know that you can solve the problem no matter what the answer is.
Sure, that was my thought. But „sadly“, my solution found 17 avg (by testing at 33 and 66), while the root solution is 14 in avg and max, both.
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.
Doesn't the binary search find a solution only for 19 floors as we would ran out of egg to drop in every other cases?
The puzzle is beautiful but the assignment is terrible. Is the maximum possible drops or average possible drops supposed to be minimal? All I can say now is that the minimum is two. Another issue with the assignment is that it does not say whether the floor can be 100.
Anyway. If it's about minimizing maximum number of drops, then I will go for 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 96, 97, 98 and if it broke in one of the midle ones, then I go one by one next. So the maximum drops would be 13. I am gonna continue watching the video now.
The maximum of trials is still 14. If 1st egg breaks from 27th floor, you find 12 floors unchecked (15 - 26) and 2 attempts are already done.
@sebastianki-t2m I see. Thanks. I never finished watching the video. I just closed it thinking I was obviously right.
I feel like I was thinkining I dont need to check the 26th floor because if it does not break at 25, it's gonna be 26. But obviously I would still not know whether it's 27 or 26. No idea what made me think that.
@7:19 "Solve for eggs" 😏
I found the explanation of the math behind solution 4 quite confusing, as x seems to be both the step interval and the number of steps and I don't understand what x+(x-1) refers to.
If x is the fixed step interval (measured in number of floors) for the first egg drop and n is the total number of floors, then the worst case scenario (i.e the breaking floor being n-1) is
(n/x)+(x-1)
This is because (n/x) is the maximum number of drops to figure out that the egg must break somewhere between floor n-x+1 and and floor n, and (x-1) is the number of times we have to drop the second egg to figure out that the egg breaks at floor n-1. So I really don't understand where the x+(x-1) comes from.
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.
Let's be honest, this is an example where mathematics and the real world have a breakdown. The egg is going to break in less than 14 floors, therefore the brute force method will result in a best result every time when tested in the real world. The mathematics being used also fail badly when you have an infinitely tall building. My proposal would be to estimate the break chance, and then select the method based on that. For example if we are using eggs I'd estimate that the floor will be very low. I'd likely then test on floor 3, if it breaks move to floor 2, and then if that breaks I know my answer is floor 1 (assuming that there is a floor where the egg won't break and the answer can't be 0). If it didn't break on floor three then I can move to floor 5, then four if it breaks on 5 or 7 if it doesn't break. This lets me test all the way up to floor 25 in less than 14 drops. It will also get an answer faster than the brute force unless the answer is one or two, and it doesn't run into a problem of being less efficient on a taller building. If we were using something tougher, then balancing linear drops would likely be a better answer, but it isn't on something like an egg. It kind of makes me think that Google is using this as a trick question, the best answer is someone that can explain why balancing linear drops looks best but really isn't, and then propose something that is still better than brute force.
your voice is like an interviewer
Now solve the reverse question. What is the maximum number of storeys a building can have in order for you to find the highest floor in that building from which an egg can be dropped safely given the fact that you are only allowed a total of X drops and you start with 2 eggs :)
1 + sum(1, 2, 3, ... , X) I reckon
I understand the sum. We have X tries. So, we drop the egg from the X floor. Regardless of the outcome, we will have (X-1) tries remaining. Then (x-2) .... until we are left with only one try. But what does the +1 in front of the sum represent?@@d6ftg7yhu
@@d6ftg7yhuyeah basically. You just want it to be in the sequence of the sum of the first n integers (+1 cause the first floor don't count).
To minimize the number of drop is always take under root of the total number of floor. And divide the floor according to that to drop the egg..and then follow below..
If egg didn't crack, move to the another group level until egg crack.
Once the egg crack start dropping egg from 1st level of that spicific group..
This solution is not only helpful for 100 floors. But also for any other highest floors..like 500...
Example - if the building has 500 floor. As we know there is no perfect under root of 500.. We ll consider the nearest round off value.
For 500 floor, we ll group the floors in set of 22. First drop from 22, if 1st egg crack then start from 1St floor and move upward until it 2nd egg cracks.
If 1st didnot crack at 22 floor. Then go to 44 floor and drop. If it cracks then start dropping 2nd egg from 23 floor until crack...
We can use the same formula for 100/200/300 or any other floor..
..
I felt like dropping from the 100th floor on seeing solution 4!! 🙆😵💫
1 drop, take the egg to the elevator on the 100th floor, step into the elevator and ride (drop) it to the ground floor. In this scenario, the egg will not break and you are done in one step. Lack of specificity in the scenario allows for creative out-side the box thinking and solutions. ;)
What about dividing every every drop by 50% of floors for each drop.
1st egg drop at floor 50
(Doesn't break)
2nd egg drop between 50 and 100 (so floor 75)
So forth. You'd end up using 7 drops of you keep dividing the target area by 50%
Thanks for your comment. Your approach valid for best cases and breaks in worst case scenarios. What if egg bread @ 50th floor and breaks again @ 25th floor ?
@@SimplyLogical So, If it breaks at floor 50, then you move on to test the lower 50%.
If it breaks at 25, then you drop at 50% (or close) if that, so drop the egg at floor 13.
If it doesn't break, now you devide 50% between floors 13 and 25 and thats where the next drop would be (floor 19) and drop from there.
Eventually when you keep splitting possible area, you've only used 7 eggs.
It works the same if you move either up or down.
But according to the puzzle, maximum number of eggs you can use is 2.
@@adriang6672 you're assuming you have an infinite number of eggs, but you don't, you only have 2.
Like he explained in the video, if you drop at 50 and it breaks, you're left with one egg.
Then you say to drop at 25, and if it breaks there, you have no more eggs, and you still don't know what is the highest floor you can drop an egg at, since you still have 24 floors left to check.
@@dorondavid4698 I think his point is. The worst case scenarios for binary search where @Adrian G is pointing out should be 7 trials instead of 50 trials.
The answer...1 drops.
I've sat on my eats for 8 weeks, until 2 chicks have hatched, waiting 3 months until they have full feathers and what both chickens from the top floor hover gracefully to the ground.....
I got one drop. Because an egg is definitely gonna break if you drop it from the second story of a building.
There are some little adjustments to improve Your solution.
By the way, in the table is a mistake: If egg breaks from 99th floor, not 100th need to be checked, but 96, 97, 98. So we find up to 14 trials, too.
From 100th floor the egg will break because the given information includes there is a level from which the egg will break. At least it is the top.
Further we do not need to test the 1st floor because there is a level from which the egg will fall safely. At least this is the lowest one.
With we steps 14, 13, 12 and so on we could reach a testing range of 105 floors, but we only need 98 to be checked. So we have 7 floors free to bring down the number of trials. I prefer to make the first 7 tests shorter by 1:
Place 1st egg on
14, 26, 37, 47, 56, 64, 71, (and now again a 7-floor-step to) 78, 84, 89, 93, 96, 98, 99.
If each case of the floor which is highest level for an unbroken egg (1, 2, 3, ..... 99) occurs once, 1015 trials will be necessary. This is an average of nearly 10.3. And 195 eggs will break during all these performances.
I explored how the process will change by using 3 eggs. I found 734 trials for all of these cases with 242 broken eggs. And finally with 4 eggs, my chosen splitting showed 672 trials using 294 eggs.
Thank You for this interesting puzzle ☺
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.
Both require 3 eggs I am afraid
How does this change with 3 eggs?
At 7:16 I must be an idiot. I am struggling with how he got from the sequence list to a fixed equation.
I got it in 14 steps but with other logic but just slightly different logic
What kind of egg can stand a 2 floor drop?
use a bit of physics first. An egg has a terminal velocity of 35m/s which is a 60m free fall (all roughly) Assuming a floor being 3m, the impact speed will not change after floor 20. So you only need to check the first 20 floors...
After 1st egg breaks the second can go only even floors:2,4,6...cause if breaks is lower odd number the last :)
I start dropping on floor 1. Because I know the egg won't survive a two-story drop. It's an egg.
Math is nice. But experience trumps math in engineering.
if you use binary search then in worst case you only need 7 attempts, isn't it the best soln?
No, because you only have 2 eggs.
@@finlay5789 Bro other soln which he is saying the best , that requires even more eggs than 7
@@finlay5789 other soln requires 11 and 14 eggs which is even worst
you are not getting it. If the egg does not break, you can use it again. The solution provided guarantee you finding the level with at most 2 broken eggs, while binary division can leave up to 7 eggs broken
@@lsrrr3857 ohhhhhhhh ok now got it
So THIS is what the egg-heads at Microsoft is wasting time on instead of making correct software? What about moving the "Delete" option in the right-click popup menu in file explorer AS FAR AWAY AS POSSIBLE from the "Copy" choice instead of putting it right beside the "Copy" option?
''Priorities''
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
Please generalized the solution for n number of eggs
I’m not going to do the calcs here but, even if you have 100 eggs 1 try would never suffice of course, U mean there should be a minimum number of tries regardless of the number of eggs, so there should be a MC number of eggs beyond which other eggs are useless , it turn out 3 eggs require max 8 drops, 4 eggs 7 drops , 5 eggs 5 drops. So 5 is the minim drops in absolute, because 6 eggs cannot do better than 5 drops, otherwise if let’s say 4 drops are the solution to 6 eggs, than 4 would be the solution for 4 eggs too, which is not
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.
Check every 12 to start. If breaks then check every second number up. =14 as well
Won't work. Checking every second you cannot determine the exact floor it would break on
@@bjbboy71697 if you check (the twelves) and it doesn’t break you then move up to the 2’s if it breaks on 2 then the one before must be safe moving up by two each time if it breaks then the safe one must be the odd number prior. The twelves also mean that only 3-4 need to be checked on every alternate round
What is the best strategy for three eggs? Four? Beyond that I don't think I could follow the logic. 😅
The answer is the first floor, not even that. Unless the eggs aren't eggs, they won't survive a drop from more than a meter at best.
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?
You are saying there is possibility that an egg would not break if it is dropped.
My solution was to drop eggs from all even numbers, and once it breaks, then second egg from previous odd number. But the answer is definitely more mathematically accurate.
If we separate in 12 group so 12*8=96
And after when it broke check 12 group by 2 jump so worst case 8+5=13
8+(12/2)=14 still same
12 groups worst case you need to test 12 times at worst case scenario, and then another 7 to find the exact level so 19 times at worst.
4:00 what is yen?
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.
How do we prove solution 4 is the optimum solution please?
Interviewer asked me same question
which company?
While your demonstration was good, the actual maw tries is one less:13.
You do not need to perform a test if you already narrowed down to one remaining floor...
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...
How does binary search gives worst case of 50? shouldn't be log2(n) which is 10?
What is the Big O of the final solution?
O(n^(1/2))
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.
I thought this too. But imagine you checked floor 20, then you check 22 and it breaks. Is 21 the highest floor, or is 20?
@@SlightlyInsane69 oh in this case, then test 21,23, 25, 27, 29? Then it would be 14 instead of 13 maximum steps
@@sjsjsjj1 It keeps happening. Once youve checked 21, then you check 23 and it breaks, is 22 the highest floor or 21?
Do you please have the actual code solution and can you share it ? I was asked this problem at JP Morgan.
What if we consider the best case scenario 😅
Except that the egg cracks a bit upon every drop and you are screwed.
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.
I'm not entirely sure that the 3rd is the best solution -- Given the predicate knowledge we are talking about eggs, that would suggest the lower number of floors more likely , and the third oulution should be reversed , ie minimum steps first to give a higher probablility of reaching the answer quicker. maybe if eggs were hollow steel fo instance this would be wrong...
If you're not 100% sure that the 3rd solution isn't the correct solution, then you didn't watch the whole video