Egg Dropping Problem: Dynamic Programming Fundamentals & Understanding Subproblem Decomposition

all right so what we're going to look at in this video is another dynamic programming problem it is called egg drop and this is another pretty I wouldn't say famous but well-known dynamic programming problem and just to get this out of the way yeah I know this was the same sweater I had in the last video I'm in the same basement and yeah alright so this problem asks us given a certain amount of floors and given a certain amount of eggs what is the least amount of egg drops the least amount of egg drops that I need to perform to find the pivotal floor we're right below it if I drop the egg it won't break and right above it if I drop the egg it will break we're looking for that pivotal floor so for example if I'm at 3 if I drop it it doesn't break but as soon as I hop up to 4 if I drop it and it breaks I know my pivotal floor is 3 that is the floor where if I go up even one higher my egg is gonna break if I drop it and so the key is we have a limited amount of eggs and we want to minimize the amount of eggs we use that is the whole point of this problem so our job is not actually to find that floor art our job is to tell me tell the caller if I give you a certain amount of floors and I give you a certain amount of eggs tell me the least amount of eggs that you will need to drop to find the pivotal floor I as a caller I don't care about the floor I care about you telling me what is the least amount of eggs that you are going to drop in the worst case to ensure ensure that what you tell me is true so if you tell me that the least amount of your eggs you'll ever have to drop to find the pivotal floor is - I have to be guaranteed of that so as a programmer what I want to do is I want to find the worst amount of eggs that I will have to drop to find a floor because that guarantees that that amount is the worst amount we'd have to drop and that guarantees that I'm going to find the floor because I'm accounting for that worst case if that makes sense so let's do a walk-through Elmi core sense this is a very difficult problem to grasp at first so what we're going to do is we're going to walk through these simulations and we're going to define base cases so let's define our first base case so imagine we have one egg what we're going to do is we're going to see if you give me six floors and one egg what is the least amount of eggs that you're going to have to drop to find that pivotal floor so if I have one egg what is my strategy going to be well I can't start at floor six I can't drop from floor six what if my egg breaks if my egg breaks when I drop from floor six then I'm going to have zero eggs if you drop an egg and it breaks you don't have that egg you lose that egg and you no longer have any eggs to do testing on the rest of the floors so if I drop my one egg from floor six that's a bad thing to do because if it breaks I don't know which of these floors are the pivotal floor so my strategy instead is going to be I'm going to drop from floor zero and instead my strategy is going to be I'll drop one egg from floor one if it breaks then I know that my pivotal floor is one below me I'm going to drop from floor two if my egg breaks then I know that the pivotal floor is floor one if it doesn't breaker one or two I'll drop it from three I still have the egg because it didn't break if I drop it from floor three and it doesn't break I go to floor four and then five and then if it breaks a five I know that the pivotal floor is floor four so in the worst case our floor where our egg is going to break is at the very top floor so what we're going to do is we're going to break this sub problem down like this so you give me one egg and you give me any amount of floors I don't care if you give me zero floors or give me a thousand floors my strategy is going to be I start from floor 0 or 1 whatever you choose is like a base and then we're going to go upwards we're gonna try every every floor going up until our egg breaks so what is the worst because remember my caller wants a guarantee I need to guarantee my caller that the amount I'm returning them is the least amount of drops I can do to guarantee I find that pivotal floor so what we care about as a programmer is we care about finding the worst amount of drops that I have to do is going to guarantee my caller I'm going to guarantee them that this is the worst I'd ever do and that means this is an upper bound on the amount of eggs I will ever drop and therefore this is the least amount to guarantee to you caller that this is the amount of eggs that I'm going to have to drop at least to guarantee to you that I have an ability to find that floor you want if I have one egg the upper bound is going to be the amount of floors I'm given at worst this egg breaks up here and I will have to do this many drops I'll have to drop it one drop it 2 3 4 5 6 drop at all the floors and that's the worst case so what is this equal and this is base case number one when we have one egg I don't care what floors you give me give me any amount of floors my upper bound on the work I'm going to do is going to be the amount of floors that's the worst amount of drops I will have to do to guarantee to my caller that I'm going to give them a guarantee of me finding that pivotal position so this is base case number one we have one other base case so let's look at that right now okay so now let's investigate base case number two our first base case related to the amount of eggs we have now our base case relies on the amount of floors we have and and our caller does this okay my caller says here you go here's a hundred eggs and here is one floor what is the minimum amount of drops you can do to guarantee to me that you're going to give me the pivotal floor so if I just have one floor you could give me a million eggs it does not matter the amount of drops I'm going to have to do in the worst case is one drop I just drop it from floor one if it breaks that means that is the pivotal floor I can't fix that means that is a floor where the egg breaks the pivotal floor would be technically floor zero if that's even a true floor so the equivalents for this is no matter how many eggs I get if I have just one floor the amount of drops I have to do is going to be one it's going to be the same amount as the floors I get so give me any amount of eggs if I have one floor the answer is going to be one drop at worst to give my caller that pivotal floor I only need to drop one egg that's all I have to do my worst case is I drop one I have an answer so this is what we give our caller our caller wants this as the answer so what if our caller asks us this our caller gives us 10,000 eggs we have zero floors to drop from this is technically base case three or if you merge these two base cases we just looked at base case two if I have 10,000 eggs give me all the eggs you want if I have no floors to work with what is the worst amount of drops that I have to do to guarantee my caller I can find the pivotal floor well that's going to be 0 drops we can't do any drops so it's going to be the number of floors we got 0 so I can return to my caller 0 and remember this maps to this we get 10,000 eggs 0 floors the worst amount of drops I do to guarantee my caller is going to be 0 drops so let me reexpress the base cases to you in code pseudocode so this can really drill in before we continue with our understandings okay so the reason I'm taking is so slow is I really want you to understand the base cases it all starts with our fundamental understandings of the base cases so this is why I really want to drill this in so again here's what we just reviewed or here's what we just talked about so here are the floors if I get one floor or zero floors I don't care about whatever amount of eggs I get what I return is the amount of floors if I have one floor I'm gonna do only one trial at worst if I have zero floors I'm gonna do zero trials at worst so the eggs if I have a total amount of eggs of one no matter what I do I am going to play it conservative I'm going to go from zero one two three four five six and I'm going to be conservative going from bottom to top and I'll keep dropping the egg because remember if I drop the egg and it breaks game over I have no more eggs to work with and I can't guarantee my caller that I can find that pivotal floor so we return the total amount of floors because of this conservative linear strategy we follow so these are the base cases and now that we fully understand what we're converging to now we can see how we perform that reduction of subproblems how we split things down into subproblems so let's look at another example with two or three eggs so what I always want you to think about is think about your base cases first after you think about the base cases think about how these subproblems reduce think of subproblem decomposition after you do that you can decompose towards your base cases so let's see an example of this and how we do that for this problem by using three eggs and we're going to have six floors so this is what the caller asks of us okay so you see how our caller wanted the amount of minimum drops to find the pivotal floor for three eggs and six floors so our job is to run a simulation our job is to act as if I dropped from floor 1 I dropped from floor two I dropped from 3 4 5 6 I'm going to act as if I'm going to drop from each of these floors and start my approach from each of these floors we're just simulating what would happen because we want to find the worst case we want to find the situation we put ourselves in that gives us the worst outcome because that worst outcome amount of drops is going to be the worst amount of drops we do to guarantee we find the pivotal floor which is what our caller wants so what we're going to do is we're going to break this down into a sub problem we're going to look to answer this sub problem I need to know the answers to all of these sub problems so I can see which one is the worst and then once I know the worst one what I'm going to do is I'm going to have that as the answer for this sub problem ok so I need you to stay with me here because this is where it starts to get confusing so if I drop from each of these floors again we're still working with this sub problem I have three eggs in my hand and I have 6 floors to work with I'm going to pretend that I start from each different floor with each amount of eggs what were the two possibilities that I need to express what were the two possibilities that can happen I drop an egg and it breaks or I drop an egg and it does not break so what does each of these entail again this is going to allow us to express the answer to each of these in terms of more subproblems so this is what it looks like so I don't want to fill these out yet but I just want you to see our sub problem starts here what we do is we want to do a worst case simulation and what we do is we try a very floor with the amount of eggs and what happens is we do more decomposition so if I have six floors and three eggs there are two ways that these can go and do you see how more subproblems happen the reason this is dynamic programming because we're going to need to cash solutions we might repeat work so that's a later concern that isn't going to concern us right now but we know we're going to be doing more subproblems and so now this is another mental leap I need you to make this is a hard problem and this might not all click it once but we're going to see how these subproblems fork so okay I have six floors and three eggs if I drop an egg what can happen the egg can break or the egg cannot break so what's going to happen is my total eggs will either stay the same notice how I just put a three for the no break for the no break that means that my egg did not break so what I'm gonna do is I'm going to put a three-fer are called we're going to keep the amount of eggs the same none of the eggs broke but which way do I go imagine I drop a floor three my egg does not break where do I go I go upwards right I'm going to try the floors above me so what does the sub-problem decomposed into so what we see here is we have six floors and three eggs if I drop at the sixth floor my egg does not break I have three eggs and if I have three eggs and now what I'm gonna do is I'm gonna go upwards well there's nowhere to go upwards but here is what we're going to do we subtract six the total floors from the amount of floors we just simulated 6 minus 6 is zero so if I go upwards I have 0 floors to work with this looks familiar that's a base case so we'll materialize that later so I put this down here again the total floors of the subproblem we're working on - the simulation floor which is 6 6 minus 6 is 0 so let's go down here the simulation of 5 floors and 3 eggs i drop an egg it does not break where do I go I go upwards because I need to invest further and what's gonna happen is five is the current floor the total floors is six floors 6 minus 5 is 1 so do you see that do you see how we're sub problem you down because if I try the fifth floor and I don't break how many floors do I have left to work with if I go up all I have is one floor so does that make sense that's why we do that there and again this is a difficult problem you don't have to absorb all of this right now but just follow me through the sub problem and eventually will understand this together and then we have four floors to work with so our n is dropped it does not break so then what we do is 6 minus 4 is 2 if I drop from 4 and I need to go up because more investigation needs to happen up I do 6 minus 4 to 1 to 2 floors are above 4 so we put 2 there okay so we have three floors and 3 eggs my egg does not break 6 minus 3 3 if I go up I have 1 2 3 floors so let's put that and then the same thing for 2 we're just finishing off if we do not break 6 minus 2 is 4 and then if we're at floor 1 I drop an egg it does not break I go upwards and then I'll have 1 2 3 4 5 floors to work with 6 minus 1 is 5 so this becomes 5 ok great so we finished our no breaks and now we understand why we branched that way because we're doing simulations of the worst case sub problems and remember we're converging to the base case we're breaking this down so we get to our base cases I don't know the answer to this I don't know the answer to these I know the answer to my base cases though and as long as I converge to them then I'm going to get the answer I want so what we're going to do now is investigate if we break so if we break what happens so if I have 6 floors and 3 eggs I drop it for them from floor 6 how many eggs do I have left I have 2 eggs and then let's fill it out for all these other subproblems that branch towards the break ok so now we see that this is 2 and if I drop an egg and it breaks I lose an egg and which way do I go I don't go upwards cuz my egg is gonna keep breaking if I drop upward I move one floor down if my egg breaks a floor four I try floor three so what I'm gonna do is try floor three so if I have six floors my egg breaks I'm gonna go down to floor five if I have five floors and three eggs and my eggs breaks I'm going to go down to floor four if I have four floors I'm gonna go down to floor three if I have three floors I'm going to go down to floor two if I have two floors I go down to floor one and if I have one floor I go down to floor zero and I want you to notice that what we're doing here is we're sub-problem account and notice that these are base cases we know the answer to zero floors we know the answer to zero floors we know the answer to one floor and this is going to keep breaking down until we get to our ultimate answer okay so we have our dynamic programming table each of these cells mean something specific that cell right there is our original sub-problem if I have 3x + 4 floors what is the answer that cell right there says if I one egg and four floors what is my answer if I have zero eggs and one floor what is the answer so what we want is right there that is the original sub-problem and what we're gonna do is we're gonna build up to that sub-problem and again the code is in the description if I haven't said that you can look at the code I have a huge example a ton of comments there so this can be really clear for you if you check the code out watch this which ever helps you learn better so what we can do here is define our base cases so this is kind of not something I mentioned but if we have no eggs then I can't do any drops so no matter what floors you give me I'll just have 0 as the answer okay and if I have 0 floors how many drops can I do to guarantee an answer well it's going to be 0 remember we won't have to do any drops if I'm not given any floors if I have just one floor it does not matter how many eggs you give me I'm going to be doing one drop that was our first base case so let's define that now okay so if I have one egg how many drops am I going to have to do remember we upper bound to the worst amount which is the amount of floors were given so this is what this looks like so you could do that with four loops you can do it in any order you want as long as you have those properties and again the link is in the description for the code so what we're going to do is we're going to start right here we're going to try to solve this sub-problem so what is the answer to this sub-problem okay so we want the answer to that sub problem right there and remember what I said simulations we want to simulate so we know the worst case at the cell so I'll simulate dropping from one floor with two eggs and I'll simulate dropping from two floors with two eggs so we'll do this okay it is a competition who is the winner who is going to do the worst I need to upper bound the worst I do it the sub problem so I can guarantee my caller that I'm going to find the pivotal floor so in order to resolve the competition I need to do a simulation at the floor and there's two possibilities the egg breaks or it does not break so if it breaks then we lose an egg and we go downwards if it does not break then we're going to keep an egg and we're going to go upwards so let's do each of those simulations okay so here's the simulation if it does not break I keep the same amount of eggs does not break I keep the same amount of eggs but I go upwards because I want to investigate upwards I do the amount of floors that I'm testing for this cell minus the floor that I'm simulating on so two minus the simulation floor one so two minus the simulation floor of two so what does that materialize into it turns into that so what we have here as well is if it does break we go downwards by one floor so one minus one the Sydney lesion floor - one simulation floor - one and what do they become alright so my camera died so I'm just gonna finish the video here so our original sub problem was right there and what we did was we made a simulation we made a simulation right oh my god right there right here and what we do is we already know the answer to those two sub problems so they materialize and what we want to do is we want the answer to this sub problem is going to be one plus the worst of our simulations right so when we take the worst of our simulations why do we add one the addition of the 1 is to signify the fact that we're going to be dropping from this sub problem so what we did was all those simulations we did were different floors we could have dropped from and this is because we're trying to bounce the worst amount of drops right so we did all those simulations and we want the worst of those simulations so what we do is we add one to the worst simulation and therefore that's going to simulate the actual drop happening so when we simulate the actual drop happening we're going to take the worst guy and we add one to him to simulate the actual drop and the answer to our sub problem becomes 1 + the worst outcome so that is why we add 1 this this will become more clear if you look at the code I put a lot of comments and description there but let's get back to Ben with the time and space for this all right so for the time and space complexity we're going to have an upper bounding of total floors times total X sub problems how long does it take to compute each sub problem an upper bound of total floors we're going to be performing some fractional work of total floors at every single subproblem so that is the upper bound on the work we can perform at each sub-problem so what happens is we multiply these together and our overarching upper bounds on the asymptotic complexity becomes total floors squared times total X so this is the time complexity for the solution presented so the space complexity is going to be total floors times total eggs we're going to hold an upper bounding of this many subproblems in our in our cache so again the code is in the description if you want to see that I have the top-down and bottom-up approaches to this problem there are more optimal solutions but it's unlikely that you would get to them in a 45-minute interview and I think that's kind of the point of all of this for me it's to get the answers or set of thinking that you would actually ever use instead of learning the actual mathematical ways that are kind of a waste of time to learn because you can't memorize every problem all right so that is all for this video if you liked this video hit the like button and subscribe to the channel again I want to make this one of the world's largest resources for software engineering preparation and interviews because I think we need a lot more you know down-to-earth clear explanations where things are explained as a student should learn them so that's kind of my mission and goal with this channel and with these videos [Music]

Channel: Back To Back SWE

Views: 81,447

Rating: 4.7737951 out of 5

Keywords: egg drop, egg dropping problem, egg drop dynamic programming, egg dropping, Back To Back SWE, Software Engineering, computer science, programming, programming interviews, coding interviews, coding questions, algorithms, algorithmic thinking, Google internship, Facebook internship, software engineering internship, swe internship, big n companies

Id: iOaRjDT0vjc

Length: 25min 38sec (1538 seconds)

Published: Mon Feb 18 2019