Dynamic Programming Interview Question #1 - Find Sets Of Numbers That Add Up To 16

hey everyone in this video I'm gonna give you a programming slash coding interview problem for which you can use dynamic programming if you're not familiar with then I'm roaming I'd recommend my dynamic programming introduction video first so here's the problem you're given an array of integers for example 2 4 6 and 10 and you're supposed to find subsets of this array which add up to a certain number for example 16 so in this case there are two such subsets the first one is 6 and 10 and the second such subset is 2 4 and 10 and just to make the problem a little bit simpler you don't have to actually find the subsets themselves you just need to find the number of subsets that add up to the given number so in this example your function should take this number 16 as well as this array and return 2 because there are two subsets of this array that add up to 16 now when you're given a coding interview problem like this one the typical first step is to ask some clarifying questions so you might ask as a clarifying question is it possible to have negative numbers here the answer is no we only have positive integers here so there's no zeros or negative numbers and is this array already sorted actually it doesn't matter too much if it's sorted or not but let's just say it's sorted and are there any duplicates in this array so is it possible to have two of the same number the answer is no there are no duplicates and what if you're given instead of 16 zero as one of the arguments what should we return then in that case you should return one from your function because technically the empty array or the empty set as up to zero so you count just this set and you return one from your function so think about this problem for a second and then come back for a solution so if I was given this problem I would first ask myself how would I solve this problem on a whiteboard or on paper the way I would do that is I would start with an empty set and I would try and construct all the possible subsets of this array so for the rightmost element or you can start at the leftmost element but let me start with the rightmost element for that one we need to ask ourselves do we want to include it in the subset that we're trying to construct if the answer is yes we'll have a subset of just one element ten and if the answer is no we'll still have an empty set and we'll need to do the same thing for the next element six and for each of these subsets so if we decide to include six to this subset or add six to this subset we'll have six and ten and if we decide not to include that in this one we'll have just ten and so on so just like that you'll be able to find all the possible subsets of this entire array and for each of these subsets you can just ask yourself in theory does it add up to for example 16 and then add up all of those subsets and we have the answer and when I see this structure if I was in the actual interview I might say well since since it's a tree it actually looks like a recursion tree and so maybe I can solve this problem using recursion so let's see how we can do that of course the idea of recursion is to break down the large problem the original problem into smaller subproblems that are similar in nature so let's see how we can do that let's call the number of subsets that add up to 16 out of the entire array and that's the answer that we're looking for and this n is actually the sum of two numbers and the first such number is the number of subsets that add up to 16 which include 10 and the second such number is the number of subsets that add up to 16 which do not include 10 and actually this first number the number of subsets that add up to 16 which include 10 is equivalent to the number of subsets that add up to 6 out of these three elements so the subsets that add up to 6 out of these three elements are 2 4 and just 6 and you can sort of merge each of these subsets with this subset with only 10 and get a subset that adds up to 16 we can get 2 of them so we can put 2 here as the first number and the second number that the number of subsets that add up to 16 which do not include 10 is equivalent to the number of subsets that add up to 16 out of these three elements because we don't have this in play anymore and there's no such subset that adds up to 16 out of these three elements because if you add all of them up you'd only have 12 as the total sum so you'd have 0 right here as the second number so in this particular example the answer that we're looking for is and is equal to 2 plus 0 which is 2 so what we just did is we broke down the large original problem of finding the number of subsets that add up to 16 out of this whole array into two smaller subproblems and we can actually keep going like that further down the tree as well just keep breaking down the problems into smaller and smaller problems so this is the basic idea of my recursive solution but one thing to note here is that you don't really have to create or store these individual subsets because we are only interested in the number of subsets that add up to a certain number for example 16 we only need to store the sum of each subset so the sum of this subset would be 10 and then the sum of the empty subset is of course there and the sum of this one is 16 and the sum of 10 is 10 and so on okay let's now see what this solution might look like in code okay here's my recursive solution in code I'm defining two functions here count sets and rec count sets will be our main function it will take the array the SKU an array and the total amount that we are trying to find the subsets for and this is going to return the number of subsets that add up to the total amount and then rec will be our recursive function so it will call itself recursively and it'll take the given array the total amount and I as an index and this is going to return the number of subsets that add up to the total amount but while considering only the elements up to the index I so if you are given for example this array r & 6 as the total amount and 2 as the index that would be right here we're only considering these 3 elements to find the subsets that add up to the given amount and in that case your functional rec should return 2 because there are two such subsets 2 4 & 6 both of them add up to 6 and the only thing we need to do in count sets is to return rec with the arguments or total and our dot length minus 1 because our dot length minus 1 would be the last index of this array in this particular example that would be 3 okay the first thing we need to do in the rec function or the recursive function is we need to take care of some base cases the first one to take care of is when total is equal to zero in that case we should return 1 because when totally is zero the only subset that adds up to zero is the empty subset and there is only one of them and the second base case to take care of is when total is less than 0 and if that's the case there is no subset that adds up to 0 so which is just returned zero since there are no negative numbers in this array and if I is less than zero that would mean I is already outside of this array and since we know that total is neither zero nor less than zero total here is a positive number and since we don't have any more numbers to create a subset with that add up to hopefully total we'll just return zero and if none of these cases are true we'll then go to our recursive cases the first recursive case that we need to deal with is when total is less than our square brackets I or the last item that we are examining so for example if I is equal to two we'd be examining this item six would be the value of our square brackets I and if the given total here is let's say four there would be no way of finding a subset out of these three elements that add up to four which includes the current item six so that means the number of subsets that add up to the total amount out of these three elements is equivalent to the number of subsets that add up to the total amount out of these two elements instead to express that we'll just need to write return rec or total I minus one so or on total or unchanged and we'll just need to go to the next item or the item that's left to the currently item that we're examining our case we need to deal with is everything else so let's say I is equal to 2 here so we're examining this item currently and the total that we're looking for is 6 if that's the case we'll need to deal with two different cases just like I explained before the first case is when we don't include 6 in the subset that we're trying to construct and it's the same as before so we'll just need to write rec or total I minus 1 and the second case is when we do include this item the subset that we are trying to construct and just like I explained before the way you can think about it is this the number of subsets that add up to the given total six right here which include this number six is equivalent to the number of subsets that add up to total minus the current item so total minus R square brackets I out of these two elements only so you can find that with rec or total minus RS square brackets I so that'll be the new total that we'll be looking for subsets four and I minus one to go to the next element and that's my recursive solution okay and this solution works but the problem is it's not very efficient the problem is that we're gonna call this function rec with the same arguments or total and I over and over again and this will be particularly the case when the given array is very long very large and the given total is very large as well so of course then IMing programming says why not just store some of those return values for the same total and I so that we don't have to repeat the same competition over and over again so let's see what a dynamic programming solution or a memorized solution looks like in code okay here's my dynamic programming or memorized solution just like before we're gonna write two functions DP and count sets DP count sets DP will be our main function which will return the number of subsets that add up to total given the array and the P will be the function that will call itself recursively but note here that we have an additional argument here called mem which we're going to use to store the returned values for some arguments for this function the first thing we'll need to do in count sets DP is we need to initialize an empty dictionary or hash table depending on the language and then assign it to mem because this is what we're going to use for storing the return values and then call DP with the arguments our total or length minus one and then men okay in DP the return values for certain arguments will be stored in ma'am in key value pairs each key will represent a unique set of arguments and there will be an Associated value with it and that's going to be the return value that's stored for this function DP so we need a way to create a key which is going to be a string in this particular case from the pair or arguments that changed total and I there are several different ways of doing this but what we're going to use here is a very simple method we're going to convert total and I which are integers to strings and then we're going to concatenate them with a column between them so for example if we had 10 as total and 3 as I will have this string 10 colon 3 as the key and we don't necessarily have to use this particular string but we just need a way to uniquely identify each argument pair with a string and then if this key already exists mmm that would mean that we've already calculated the return value for this particular total and I pair so we're just going to return the stored value the value that's associated with this particular key instead of going through this whole function and if we don't have any stored value associated with this key yet we're gonna go through this whole function and it's going to be very similar to what we had earlier for the recursive solution first of all the base cases are exactly the same so we're just gonna skip that and else if total is less than or square brackets i we have DP of our total i minus 1 mem which is almost exactly the same as what we had earlier in our recursive solution but instead of returning this right away we're gonna store it and the to return variable and then we're going to return it at the end and we're gonna take care of the other case the same way we have DP of our total minus R square brackets I - 1 min and then the same thing as what we had right here so add them up and instead of returning it we're gonna store it and to return and after that before returning to return we're gonna store it in the ma'am dictionary or hash table with the key key which we calculated earlier so that we can use this value later when we see the same pair of arguments and of course at the end of this function we're gonna return to return and we're done this is my dynamic programming solution but let's see if we can calculate the time complexity for this function to find the time complexity for this method we first need to find the number of times we call our recursive function DP and then multiply by the time it takes to execute each of those calls so let's first see if we can count the number of calls we call DP there are only two ways we call DP the first one is from right here from the original function counts sets DP and then the second way is from this block right here either on this line or this line now the important thing to notice here is that the number of times we call this block is at most total times and times where n is the number of items in the given array and you can think about it this way there are any potential values for I ranging from 0 through and minus 1 and the number of potential values for this argument total is the original value of total so if the original value of total is 16 and if you're given this array and would be 4 so you'd have 16 times 4 potential value pairs for the pair total and I and for each unique pair we only go through this entire function and then get to this block once because after the first time will already have returned here and if either total or I is out of range from those particular for example if I is minus 1 then we'll already have returned before we get to this block for example right here as well and so we get to this block at most total times n times and each time we get to this block will call DP only at most twice so the maximum number of times we're gonna call DP is going to be total times and times 2 and if you want you can add 1 to account for the first time we call DP from count sets DP so now we have an upper bound for the number of times we're gonna call this function DP and that's total times n times 2 plus 2 and of course total here is the original value of total and what about the time it takes to execute each of those calls if you look at each line in this function except for those recursive calls each line only takes a constant amount of time or Big O of one to execute and of course when you add up a bunch of different operations each taking constant amount of time they will only take a constant amount of time as a whole so the time it takes to execute each of those calls excluding those recursive calls is Big O of one or a constant amount of time and when you multiply these two numbers together Big O of 1 and total times n times 2 plus 2 you get Big O of total times n and being the number of items in the given array and so that's the time complexity for this particular function ok just like usual let me know in a comment below if anything is unclear and if you like this video I would also recommend my course on udemy called 11 essential coding interview questions in which I cover 11 of the most essential coding interview questions to master although I don't cover dynamic programming in this course but I'm gonna put a link to this course in the description below and if you want to make sure that you don't miss my future videos the best way to do that is to subscribe to my newsletter by going to CS dojo dot io / news my K from CS dojo and I'll see you in the next video

Channel: CS Dojo

Views: 413,604

Rating: 4.8082514 out of 5

Keywords: dynamic programming, coding interview question and answer, programming interview question and answer, dynamic programming tutorial, software engineer interview question and answer, coding interview, programming interview, cracking the coding interview

Id: nqlNzOcnCfs

Length: 20min 5sec (1205 seconds)

Published: Fri Jan 05 2018