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

description
My Udemy course, 11 Essential Coding Interview Questions: https://www.udemy.com/11-essential-coding-interview-questions/?couponCode=DPQUESTION1 My dynamic programming intro video: https://youtu.be/vYquumk4nWw NOTE: There's an outline of this video in the comment section below! Keep in touch on Facebook: https://www.facebook.com/entercsdojo Support me on Patreon: https://www.patreon.com/csdojo

detail
{'title': 'Dynamic Programming Interview Question #1 - Find Sets Of Numbers That Add Up To 16', 'heatmap': [{'end': 945.783, 'start': 927.197, 'weight': 1}], 'summary': 'Discusses dynamic programming interview problems, covering topics such as finding subsets of an array that add up to a given number, counting subsets code solution, handling subsets and recursive subset sum, dynamic programming for subset sum, explanation of dynamic programming, and time complexity analysis within the context of coding interview questions and course recommendations.', 'chapters': [{'end': 381.111, 'segs': [{'end': 89.874, 'src': 'embed', 'start': 47.849, 'weight': 0, 'content': [{'end': 51.47, 'text': 'you just need to find the number of subsets that add up to the given number.', 'start': 47.849, 'duration': 3.621}, {'end': 60.295, 'text': 'So in this example, your function should take this number 16 as well as this array, and return 2,', 'start': 52.27, 'duration': 8.025}, {'end': 63.978, 'text': 'because there are two subsets of this array that add up to 16..', 'start': 60.295, 'duration': 3.683}, {'end': 71.042, 'text': "Now, when you're given a coding interview problem like this one, the typical first step is to ask some clarifying questions.", 'start': 63.978, 'duration': 7.064}, {'end': 76.106, 'text': 'So you might ask, as a clarifying question is it possible to have negative numbers here??', 'start': 71.643, 'duration': 4.463}, {'end': 82.829, 'text': "The answer is no, we only have positive integers here, so there's no zeros or negative numbers.", 'start': 76.846, 'duration': 5.983}, {'end': 89.874, 'text': "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.", 'start': 83.75, 'duration': 6.124}], 'summary': 'Find subsets adding up to 16 from array of positive integers. clarify if array is sorted or contains negative numbers.', 'duration': 42.025, 'max_score': 47.849, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nqlNzOcnCfs/pics/nqlNzOcnCfs47849.jpg'}, {'end': 259.446, 'src': 'embed', 'start': 220.304, 'weight': 2, 'content': [{'end': 222.888, 'text': 'And so maybe I can solve this problem using recursion.', 'start': 220.304, 'duration': 2.584}, {'end': 224.45, 'text': "So let's see how we can do that.", 'start': 223.348, 'duration': 1.102}, {'end': 234.633, 'text': 'Of course, the idea of recursion is to break down the large problem, the original problem, into smaller subproblems that are similar in nature.', 'start': 225.231, 'duration': 9.402}, {'end': 236.674, 'text': "So let's see how we can do that.", 'start': 235.454, 'duration': 1.22}, {'end': 242.856, 'text': "Let's call the number of subsets that add up to 16 out of the entire array, n.", 'start': 237.334, 'duration': 5.522}, {'end': 244.276, 'text': "That's the answer that we're looking for.", 'start': 242.856, 'duration': 1.42}, {'end': 259.446, 'text': 'And this n is actually the sum of two And the first such number is the number of subsets that add up to 16, which include 10.', 'start': 244.996, 'duration': 14.45}], 'summary': 'Using recursion to find subsets adding up to 16, including 10.', 'duration': 39.142, 'max_score': 220.304, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nqlNzOcnCfs/pics/nqlNzOcnCfs220304.jpg'}], 'start': 0.449, 'title': 'Dynamic programming interview problem', 'summary': 'Discusses a programming interview problem where the task is to find subsets of an array that add up to a given number, exemplifying the approach using recursion and breaking down the problem into smaller subproblems.', 'chapters': [{'end': 381.111, 'start': 0.449, 'title': 'Dynamic programming interview problem', 'summary': 'Discusses a programming interview problem where the task is to find subsets of an array that add up to a given number, exemplifying the approach using recursion and breaking down the problem into smaller subproblems.', 'duration': 380.662, 'highlights': ['The problem involves finding subsets of an array that add up to a given number, such as 16, and returning the count of such subsets.', 'The chapter emphasizes the importance of asking clarifying questions when given a coding interview problem, such as the presence of negative numbers or duplicates in the array.', 'The speaker explains the approach of constructing all possible subsets of the array and using recursion to break down the original problem into smaller subproblems, demonstrating this with an example involving the number 16.']}], 'duration': 380.662, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nqlNzOcnCfs/pics/nqlNzOcnCfs449.jpg', 'highlights': ['The problem involves finding subsets of an array that add up to a given number, such as 16, and returning the count of such subsets.', 'The chapter emphasizes the importance of asking clarifying questions when given a coding interview problem, such as the presence of negative numbers or duplicates in the array.', 'The speaker explains the approach of constructing all possible subsets of the array and using recursion to break down the original problem into smaller subproblems, demonstrating this with an example involving the number 16.']}, {'end': 507.157, 'segs': [{'end': 451.686, 'src': 'embed', 'start': 381.911, 'weight': 0, 'content': [{'end': 391.1, 'text': '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.', 'start': 381.911, 'duration': 9.189}, {'end': 404.949, 'text': 'So the sum of this subset would be 10, and then the sum of the empty subset is of course zero, and the sum of this one is 16, and the sum of 10 is 10,', 'start': 391.66, 'duration': 13.289}, {'end': 405.409, 'text': 'and so on.', 'start': 404.949, 'duration': 0.46}, {'end': 408.691, 'text': "Okay, let's now see what this solution might look like in code.", 'start': 406.01, 'duration': 2.681}, {'end': 411.593, 'text': "Okay, here's my recursive solution in code.", 'start': 409.311, 'duration': 2.282}, {'end': 415.856, 'text': "I'm defining two functions here, countSets and rec.", 'start': 412.393, 'duration': 3.463}, {'end': 418.779, 'text': 'countSets will be our main function.', 'start': 416.597, 'duration': 2.182}, {'end': 425.345, 'text': "It'll take the array, this given array and the total amount that we're trying to find the subsets for,", 'start': 419.32, 'duration': 6.025}, {'end': 429.79, 'text': 'and this is going to return the number of subsets that add up to the total amount.', 'start': 425.345, 'duration': 4.445}, {'end': 435.254, 'text': "And then rec will be our recursive function, so it'll call itself recursively.", 'start': 430.41, 'duration': 4.844}, {'end': 440.778, 'text': "And it'll take the given array, the total amount, and i as an index.", 'start': 436.094, 'duration': 4.684}, {'end': 451.686, 'text': '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.', 'start': 441.438, 'duration': 10.248}], 'summary': 'The transcript explains a recursive solution to find the number of subsets that add up to a given total amount.', 'duration': 69.775, 'max_score': 381.911, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nqlNzOcnCfs/pics/nqlNzOcnCfs381911.jpg'}], 'start': 381.911, 'title': 'Counting subsets code solution', 'summary': 'Discusses a code solution for counting the number of subsets that add up to a certain number using recursive functions and base cases, with a specific example of finding subsets that add up to 6.', 'chapters': [{'end': 507.157, 'start': 381.911, 'title': 'Counting subsets code solution', 'summary': 'Discusses a code solution for counting the number of subsets that add up to a certain number, utilizing recursive functions and base cases, with a specific example of finding subsets that add up to 6.', 'duration': 125.246, 'highlights': ['The recursive function rec takes the given array, total amount, and index as parameters, returning the number of subsets that add up to the total amount while considering only the elements up to index i, with a specific example returning 2 subsets for an array and total amount of 6.', 'The main function countSets takes the given array and the total amount as parameters, returning the number of subsets that add up to the total amount, utilizing the recursive function rec and returning the result of rec with the arguments rTotal and r.length minus one.', 'The storing of the sum of each subset is highlighted, with examples of the sum of specific subsets and the empty subset, emphasizing the approach of only needing to store the sum of subsets that add up to a certain number, for instance 16.']}], 'duration': 125.246, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nqlNzOcnCfs/pics/nqlNzOcnCfs381911.jpg', 'highlights': ['The recursive function rec takes the given array, total amount, and index as parameters, returning the number of subsets that add up to the total amount while considering only the elements up to index i, with a specific example returning 2 subsets for an array and total amount of 6.', 'The main function countSets takes the given array and the total amount as parameters, returning the number of subsets that add up to the total amount, utilizing the recursive function rec and returning the result of rec with the arguments rTotal and r.length minus one.', 'The storing of the sum of each subset is highlighted, with examples of the sum of specific subsets and the empty subset, emphasizing the approach of only needing to store the sum of subsets that add up to a certain number, for instance 16.']}, {'end': 723.139, 'segs': [{'end': 557.574, 'src': 'embed', 'start': 507.798, 'weight': 0, 'content': [{'end': 510.9, 'text': 'The first one to take care of is when total is equal to zero.', 'start': 507.798, 'duration': 3.102}, {'end': 521.467, 'text': 'In that case we should return one, because when total is zero, the only subset that adds up to zero is the empty subset,', 'start': 511.801, 'duration': 9.666}, {'end': 522.688, 'text': 'and there is only one of them.', 'start': 521.467, 'duration': 1.221}, {'end': 528.413, 'text': 'And the second base case to take care of is when total is less than zero.', 'start': 523.229, 'duration': 5.184}, {'end': 533.116, 'text': "And if that's the case, there is no subset that adds up to zero.", 'start': 529.373, 'duration': 3.743}, {'end': 538.24, 'text': 'so we should just return zero, since there are no negative numbers in the survey.', 'start': 533.116, 'duration': 5.124}, {'end': 544.984, 'text': 'and if i is less than zero that would mean i is already outside of the survey.', 'start': 538.24, 'duration': 6.744}, {'end': 551.669, 'text': 'and since we know that total is neither zero nor less than zero, total here is a positive number.', 'start': 544.984, 'duration': 6.685}, {'end': 557.574, 'text': "Since we don't have any more numbers to create a subset with that add up to, hopefully, total,", 'start': 552.649, 'duration': 4.925}], 'summary': 'Return 1 if total is zero, 0 if less than zero, else positive number.', 'duration': 49.776, 'max_score': 507.798, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nqlNzOcnCfs/pics/nqlNzOcnCfs507798.jpg'}, {'end': 618.588, 'src': 'embed', 'start': 589.096, 'weight': 4, 'content': [{'end': 599.179, 'text': '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.', 'start': 589.096, 'duration': 10.083}, {'end': 612.205, 'text': '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.', 'start': 599.779, 'duration': 12.426}, {'end': 618.588, 'text': "To express that, we'll just need to write return rec r total i-1.", 'start': 612.785, 'duration': 5.803}], 'summary': 'Finding subsets that add up to total: 3 elements = 2 elements', 'duration': 29.492, 'max_score': 589.096, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nqlNzOcnCfs/pics/nqlNzOcnCfs589096.jpg'}, {'end': 731.402, 'src': 'embed', 'start': 701.853, 'weight': 3, 'content': [{'end': 708.435, 'text': "So that'll be the new total that we'll be looking for subsets for and i-1, to go to the next element,", 'start': 701.853, 'duration': 6.582}, {'end': 710.836, 'text': "And that's my recursive solution.", 'start': 709.095, 'duration': 1.741}, {'end': 715.377, 'text': "Okay, and this solution works, but the problem is, it's not very efficient.", 'start': 711.596, 'duration': 3.781}, {'end': 723.139, 'text': "The problem is that we're going to call this function, rec, with the same arguments, r total and i, over and over again.", 'start': 715.837, 'duration': 7.302}, {'end': 731.402, 'text': 'This will be particularly the case when the given array is very long, very large, and the given total is very large as well.', 'start': 723.839, 'duration': 7.563}], 'summary': 'Recursive solution inefficient due to repetitive function calls with large arrays and totals.', 'duration': 29.549, 'max_score': 701.853, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nqlNzOcnCfs/pics/nqlNzOcnCfs701853.jpg'}], 'start': 507.798, 'title': 'Handling subsets and recursive subset sum', 'summary': 'Discusses handling subsets and total values, explaining the base cases when the total is equal to zero and less than zero, and the logic for returning one or zero based on these conditions, ensuring a positive total value for subset creation. it also explains a recursive solution to find the number of subsets that add up to a given total, and its inefficiency due to redundant function calls.', 'chapters': [{'end': 557.574, 'start': 507.798, 'title': 'Handling subsets and total values', 'summary': 'Discusses handling subsets and total values, explaining the base cases when the total is equal to zero and less than zero, and the logic for returning one or zero based on these conditions, ensuring a positive total value for subset creation.', 'duration': 49.776, 'highlights': ['The need to return one when the total is zero, as the only subset adding up to zero is the empty subset, and there is only one of them.', 'Returning zero when the total is less than zero, as there are no negative numbers in the survey, ensuring a positive total value for subset creation.', "Explaining that if 'i' is less than zero, it means 'i' is already outside of the survey, indicating the boundary condition for subset creation."]}, {'end': 723.139, 'start': 557.574, 'title': 'Recursive subset sum', 'summary': 'Explains a recursive solution to find the number of subsets that add up to a given total, and its inefficiency due to redundant function calls.', 'duration': 165.565, 'highlights': ['Recursive solution for finding the number of subsets that add up to a given total is explained, including handling cases when the total is less than the current item and when it is equal to the current item, with the explanation that the solution is not very efficient due to redundant function calls.', 'The number of subsets that add up to a total amount out of a certain number of elements is equivalent to the number of subsets that add up to the total amount out of a lesser number of elements, demonstrated with an example of finding subsets that add up to a given total, and an explanation of the inefficiency of the solution due to redundant function calls.', "Explanation of the recursive solution's inefficiency due to repeated function calls with the same arguments, leading to inefficiency in the solution."]}], 'duration': 215.341, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nqlNzOcnCfs/pics/nqlNzOcnCfs507798.jpg', 'highlights': ['The need to return one when the total is zero, as the only subset adding up to zero is the empty subset, and there is only one of them.', 'Returning zero when the total is less than zero, as there are no negative numbers in the survey, ensuring a positive total value for subset creation.', "Explaining that if 'i' is less than zero, it means 'i' is already outside of the survey, indicating the boundary condition for subset creation.", 'Recursive solution for finding the number of subsets that add up to a given total is explained, including handling cases when the total is less than the current item and when it is equal to the current item, with the explanation that the solution is not very efficient due to redundant function calls.', 'The number of subsets that add up to a total amount out of a certain number of elements is equivalent to the number of subsets that add up to the total amount out of a lesser number of elements, demonstrated with an example of finding subsets that add up to a given total, and an explanation of the inefficiency of the solution due to redundant function calls.', "Explanation of the recursive solution's inefficiency due to repeated function calls with the same arguments, leading to inefficiency in the solution."]}, {'end': 869.452, 'segs': [{'end': 764.66, 'src': 'embed', 'start': 723.839, 'weight': 0, 'content': [{'end': 731.402, 'text': 'This will be particularly the case when the given array is very long, very large, and the given total is very large as well.', 'start': 723.839, 'duration': 7.563}, {'end': 738.985, 'text': 'so of course, dynamic programming says why not just store some of those Return values for the same total and I,', 'start': 731.402, 'duration': 7.583}, {'end': 742.386, 'text': "so that we don't have to repeat the same computation over and over again?", 'start': 738.985, 'duration': 3.401}, {'end': 747.788, 'text': "So let's see what a dynamic programming solution or a memorized solution looks like in code.", 'start': 742.386, 'duration': 5.402}, {'end': 751.911, 'text': "Okay, here's my dynamic programming or memoized solution.", 'start': 748.428, 'duration': 3.483}, {'end': 757.455, 'text': "Just like before, we're gonna write two functions, dp and countSets dp.", 'start': 752.371, 'duration': 5.084}, {'end': 764.66, 'text': 'countSets dp will be our main function, which will return the number of subsets that add up to total given the array.', 'start': 757.855, 'duration': 6.805}], 'summary': 'Using dynamic programming to avoid repetitive computations in finding subsets that add up to a given total.', 'duration': 40.821, 'max_score': 723.839, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nqlNzOcnCfs/pics/nqlNzOcnCfs723839.jpg'}], 'start': 723.839, 'title': 'Dynamic programming for subset sum', 'summary': 'Discusses the implementation of dynamic programming to find the number of subsets adding up to a given total, emphasizing the significance of storing return values to avoid repeated computations.', 'chapters': [{'end': 869.452, 'start': 723.839, 'title': 'Dynamic programming for subset sum problem', 'summary': 'Discusses the implementation of a dynamic programming solution for finding the number of subsets that add up to a given total in a given array, emphasizing the significance of storing return values to avoid repeated computations.', 'duration': 145.613, 'highlights': ['The chapter discusses the implementation of a dynamic programming solution for finding the number of subsets that add up to a given total in a given array It explains the use of dynamic programming for efficiently solving the subset sum problem, highlighting the significance of this approach for large arrays and totals.', 'emphasizing the significance of storing return values to avoid repeated computations It emphasizes the importance of using memoization to store return values, thereby reducing the need for repetitive computations, leading to improved efficiency.']}], 'duration': 145.613, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nqlNzOcnCfs/pics/nqlNzOcnCfs723839.jpg', 'highlights': ['The chapter discusses the implementation of a dynamic programming solution for finding the number of subsets that add up to a given total in a given array.', 'It explains the use of dynamic programming for efficiently solving the subset sum problem, highlighting the significance of this approach for large arrays and totals.', 'Emphasizing the significance of storing return values to avoid repeated computations.', 'It emphasizes the importance of using memoization to store return values, thereby reducing the need for repetitive computations, leading to improved efficiency.']}, {'end': 965.29, 'segs': [{'end': 892.429, 'src': 'embed', 'start': 869.772, 'weight': 0, 'content': [{'end': 880.339, 'text': "And then, if this key already exists in mem, that would mean that we've already calculated the return value for this particular total and i pair.", 'start': 869.772, 'duration': 10.567}, {'end': 888.125, 'text': "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.", 'start': 880.339, 'duration': 7.786}, {'end': 892.429, 'text': "and if we don't have any stored value associated with this key yet,", 'start': 888.125, 'duration': 4.304}], 'summary': 'If key exists in mem, return stored value instead of recalculating.', 'duration': 22.657, 'max_score': 869.772, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nqlNzOcnCfs/pics/nqlNzOcnCfs869772.jpg'}, {'end': 966.211, 'src': 'heatmap', 'start': 927.197, 'weight': 1, 'content': [{'end': 929.678, 'text': "And we're going to take care of the other case the same way.", 'start': 927.197, 'duration': 2.481}, {'end': 939.661, 'text': 'We have dp of r total minus r square brackets i, i minus one mem, and then the same thing as what we had right here.', 'start': 930.218, 'duration': 9.443}, {'end': 945.783, 'text': "So add them up, and instead of returning it, we're going to store it in to return.", 'start': 940.301, 'duration': 5.482}, {'end': 956.427, 'text': "and after that, before returning to return, we're going to store it in the mem dictionary or hash table with the key key which we calculated earlier,", 'start': 946.503, 'duration': 9.924}, {'end': 961.829, 'text': 'so that we can use this value later when we see the same pair of arguments.', 'start': 956.427, 'duration': 5.402}, {'end': 965.29, 'text': "and, of course, at the end of this function we're going to return to return.", 'start': 961.829, 'duration': 3.461}, {'end': 966.211, 'text': "and we're done.", 'start': 965.29, 'duration': 0.921}], 'summary': 'Using dynamic programming to store and return calculated values for future use.', 'duration': 39.014, 'max_score': 927.197, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nqlNzOcnCfs/pics/nqlNzOcnCfs927197.jpg'}], 'start': 869.772, 'title': 'Dynamic programming explanation', 'summary': 'Explains a dynamic programming solution for computing return values for a given pair, storing values in a dictionary for future use, and optimizing future function calls.', 'chapters': [{'end': 965.29, 'start': 869.772, 'title': 'Dynamic programming explanation', 'summary': 'Explains a dynamic programming solution for computing return values for a given pair, storing values in a dictionary for future use, and returning the calculated value if available, as well as the process of adding and storing values to optimize future function calls.', 'duration': 95.518, 'highlights': ['The function checks if a precalculated value exists in the dictionary for a given pair, and if so, returns the stored value, optimizing performance.', 'The process involves storing calculated values in a dictionary, allowing for future use and optimization of the function by avoiding redundant calculations.', 'The function involves adding and storing computed values in a dictionary, improving efficiency by avoiding repetitive calculations and optimizing performance.']}], 'duration': 95.518, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nqlNzOcnCfs/pics/nqlNzOcnCfs869772.jpg', 'highlights': ['The function checks if a precalculated value exists in the dictionary for a given pair, and if so, returns the stored value, optimizing performance.', 'The process involves storing calculated values in a dictionary, allowing for future use and optimization of the function by avoiding redundant calculations.', 'The function involves adding and storing computed values in a dictionary, improving efficiency by avoiding repetitive calculations and optimizing performance.']}, {'end': 1204.577, 'segs': [{'end': 1156.891, 'src': 'embed', 'start': 1051.5, 'weight': 0, 'content': [{'end': 1058.705, 'text': 'And for each unique pair, we only go through this entire function and then get to this block once.', 'start': 1051.5, 'duration': 7.205}, {'end': 1062.668, 'text': "Because after the first time, we'll already have returned here.", 'start': 1059.466, 'duration': 3.202}, {'end': 1071.455, 'text': 'And if either total or i is out of range from those particular pairs, for example, if i is minus 1,', 'start': 1063.229, 'duration': 8.226}, {'end': 1076.899, 'text': "then we'll already have returned before we get to this block, for example, right here as well.", 'start': 1071.455, 'duration': 5.444}, {'end': 1081.881, 'text': 'And so we get to this block at most total times n times.', 'start': 1077.219, 'duration': 4.662}, {'end': 1087.683, 'text': "And each time we get to this block, we'll call dp only at most twice.", 'start': 1082.401, 'duration': 5.282}, {'end': 1094.965, 'text': "So the maximum number of times we're going to call dp is going to be total times n times two.", 'start': 1088.103, 'duration': 6.862}, {'end': 1101.688, 'text': 'And if you want, you can add one to account for the first time we call dp from count sets dp.', 'start': 1095.566, 'duration': 6.122}, {'end': 1106.513, 'text': 'So now we have an upper bound for the number of times.', 'start': 1102.488, 'duration': 4.025}, {'end': 1110.577, 'text': "We're gonna call this function DP and that's total times.", 'start': 1106.513, 'duration': 4.064}, {'end': 1116.043, 'text': 'n times 2 plus 2 and of course total here is the original value of total.', 'start': 1110.577, 'duration': 5.466}, {'end': 1119.907, 'text': 'and What about the time it takes to execute each of those calls?', 'start': 1116.043, 'duration': 3.864}, {'end': 1121.989, 'text': 'if you look at each line in this function?', 'start': 1119.907, 'duration': 2.082}, {'end': 1130.775, 'text': 'except for those recursive calls, each line only takes a constant amount of time or O to execute.', 'start': 1122.95, 'duration': 7.825}, {'end': 1137.739, 'text': 'And, of course, when you add up a bunch of different operations, each taking constant amount of time,', 'start': 1131.055, 'duration': 6.684}, {'end': 1141.141, 'text': 'they will only take a constant amount of time as a whole.', 'start': 1137.739, 'duration': 3.402}, {'end': 1148.645, 'text': 'So the time it takes to execute each of those calls, excluding those recursive calls is O or a constant amount of time.', 'start': 1141.581, 'duration': 7.064}, {'end': 1156.891, 'text': 'And when you multiply these two numbers together big O of 1 and total times n times 2 plus 2,', 'start': 1149.525, 'duration': 7.366}], 'summary': 'Function dp is called at most total times n times and each call takes o(1) time.', 'duration': 105.391, 'max_score': 1051.5, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nqlNzOcnCfs/pics/nqlNzOcnCfs1051500.jpg'}, {'end': 1204.577, 'src': 'embed', 'start': 1179.863, 'weight': 4, 'content': [{'end': 1183.844, 'text': 'in which I cover 11 of the most essential coding interview questions to master.', 'start': 1179.863, 'duration': 3.981}, {'end': 1187.626, 'text': "although I don't cover dynamic programming in this course.", 'start': 1184.504, 'duration': 3.122}, {'end': 1194.65, 'text': "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,", 'start': 1187.626, 'duration': 7.024}, {'end': 1200.814, 'text': 'the best way to do that is to subscribe to my newsletter by going to csdojo.io slash news.', 'start': 1194.65, 'duration': 6.164}, {'end': 1204.577, 'text': "I'm YK from CS Dojo and I'll see you in the next video.", 'start': 1201.435, 'duration': 3.142}], 'summary': 'Covers 11 essential coding interview questions; encourages subscribing to newsletter for future content.', 'duration': 24.714, 'max_score': 1179.863, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nqlNzOcnCfs/pics/nqlNzOcnCfs1179863.jpg'}], 'start': 965.29, 'title': 'Dynamic programming time complexity and analysis', 'summary': 'Explains the time complexity of dynamic programming solution, with a maximum of n times total, and the time complexity of a function which is o(total * n), with a maximum of total * n * 2 + 2 calls to the dp function, each taking o(1) time, and is covered within the context of coding interview questions and a course recommendation.', 'chapters': [{'end': 1076.899, 'start': 965.29, 'title': 'Dynamic programming time complexity', 'summary': 'Explains the time complexity of a dynamic programming solution, highlighting the number of calls to the recursive function and its relation to the size of the input array, with a maximum of n times total, where n is the number of items in the array.', 'duration': 111.609, 'highlights': ['The number of times we call the recursive function dp is at most n times total, where n is the number of items in the given array and total is the original value of total.', "For each unique pair of total and i, the function goes through the entire process and reaches the block once, resulting in a clear understanding of the function's time complexity."]}, {'end': 1204.577, 'start': 1077.219, 'title': 'Time complexity analysis of dp function', 'summary': 'Explains the time complexity of a function, which is o(total * n), with a maximum of total * n * 2 + 2 calls to the dp function, each taking o(1) time, and is covered within the context of coding interview questions and a course recommendation.', 'duration': 127.358, 'highlights': ['The time complexity of the function is O(total * n), where n is the number of items in the given array, with a maximum of total * n * 2 + 2 calls to the DP function.', 'Each call to the function, excluding recursive calls, takes a constant amount of time, denoted as O(1).', "The chapter also mentions the author's course on Udemy, '11 Essential Coding Interview Questions', and recommends subscribing to the newsletter for future videos."]}], 'duration': 239.287, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nqlNzOcnCfs/pics/nqlNzOcnCfs965290.jpg', 'highlights': ['The time complexity of the function is O(total * n), with a maximum of total * n * 2 + 2 calls to the DP function.', 'The number of times we call the recursive function dp is at most n times total, where n is the number of items in the given array and total is the original value of total.', 'Each call to the function, excluding recursive calls, takes a constant amount of time, denoted as O(1).', "For each unique pair of total and i, the function goes through the entire process and reaches the block once, resulting in a clear understanding of the function's time complexity.", "The chapter also mentions the author's course on Udemy, '11 Essential Coding Interview Questions', and recommends subscribing to the newsletter for future videos."]}], 'highlights': ['The problem involves finding subsets of an array that add up to a given number, such as 16, and returning the count of such subsets.', 'The chapter discusses the implementation of a dynamic programming solution for finding the number of subsets that add up to a given total in a given array.', 'The recursive function rec takes the given array, total amount, and index as parameters, returning the number of subsets that add up to the total amount while considering only the elements up to index i, with a specific example returning 2 subsets for an array and total amount of 6.', 'The need to return one when the total is zero, as the only subset adding up to zero is the empty subset, and there is only one of them.', 'The time complexity of the function is O(total * n), with a maximum of total * n * 2 + 2 calls to the DP function.']}