Gain insights into dynamic programming in JavaScript with strategies developed by FAANG engineers. Practice with real-world interview questions and get interview-ready in just a few hours.

Some of the toughest questions in technical interviews require dynamic programming solutions. Dynamic programming (DP) is an advanced optimization technique applied to recursive solutions. However, DP is not a one-size-fits-all technique, and it requires practice to develop the ability to identify the underlying DP patterns. With a strategic approach, coding interview prep for DP problems shouldn’t take more than a few weeks.

This course starts with an introduction to DP and thoroughly discusses five DP patterns. You’ll learn to apply each pattern to several related problems, with a visual representation of the working of the pattern, and learn to appreciate the advantages of DP solutions over naive solutions.

After completing this course, you will have the skills you need to unlock even the most challenging questions, grok the coding interview, and level up your career with confidence.

This course is also available in C++, Java, and Python—with more coming soon!

Grokking Dynamic Programming Interview in JavaScript

align-center

Help me debug only the function countWays.I don't need the corrected code.I don't want explanations or code reviews. Just provide me the exact and to-the-point error that helps me run the code successfully on the test cases provided.

Please help me understand why this code failed for the last failed test case. Please don't give me the corrected code. Just provide me exact and to-the-point advice on how to correct the code so that it runs successfully on the test cases provided. 

Your current task is to review countWays function And Answer the following questions: Ensure that the Unbounded Knapsack  pattern used? Does the code follow proper language guidelines. At the end, review the code.

Please provide a brief time complexity analysis of the function countWays.While calculating time complexity, include the time complexity of built-in Javascript functions invoked by the code. The Answer should be to the point and in a few lines.

Please provide a brief Space complexity analysis of the function countWays.While calculating space complexity, include the space complexity of built-in Javascript functions invoked by the code. The Answer should be to the point and in a few lines.

def evaluate_results(self) -> object:
        """
        self.__inputs is the list of inputs that are passed as input to function
        self.__actual_output is a list of outputs that is produced by the learner's code
        return : self.__edu__result object
        """
        # multiple outputs will be added at each index respectively for a single test_case
        expected_outputs = [] 
        # store the 1st expected output that should be displayed to the user 
        expected_outputs.append(self.__inputs[0] + self.__inputs[1])

        if json.dumps(self.__inputs[0] + self.__inputs[1]) == json.dumps(self.__actual_outputs[0]):
            self.__edu_result.store_result(expected_outputs, TestCaseResult.PASS)
        else:
            self.__edu_result.store_result(expected_outputs, TestCaseResult.FAIL)

        return self.__edu_result

// the first parameter, coins, is a list of type number
// the second parameter, amount, is of type number
// this function returns a value of type number
function countWays(coins, amount){

    // replace this placeholder return statement with your code
    return -1;
}

export { countWays }

testcases:
  - name: "testcase 1"
    inputs:
    - 1: [9]
    - 2: 12
    output:
    - 1 : 0
  - name: "testcase 2"
    inputs:
    - 1 : [10, 20] 
    - 2 : 30
    output: 
    - 1 : 2
  - name: "testcase 3"
    inputs:
    - 1: [1, 2, 5]
    - 2: 7
    output:
    - 1 : 6
  - name: "testcase 4"
    inputs:
    - 1: [4, 5, 6]
    - 2: 0
    output:
    - 1 : 1
  - name: "testcase 5"
    inputs:
    - 1: [23, 82, 211, 469, 499, 154, 285]
    - 2: 500
    output:
    - 1 : 1
  - name: "testcase 6"
    inputs:
    - 1: [162, 18, 11, 284, 465]
    - 2: 700
    output:
    - 1 : 16
  - name: "testcase 7"
    inputs:
    - 1: [1310,3198,2445,4157,2691,1315,2272,1683,2096,317,2288,3914,3758,1114,2137,1087,790,1761,3372,4592,2032,3235,4585,868,3556,1124,2899,4714,2833,1792,4832,674,4918,1829,1020,412,633,1771,1989,4977,4976,1937,3999,2660,3484,352,2695,65,1073,323,3332,4777,2979,3493,3940,350,2791,861,4558,1689,421,4988,1040,4931,2090,2727,1433,301,3883,570,1657,820,1746,2642,292,3780,3497,3363,2469,2631,1497,4451,1234,2211,4661,1448,4391,310,4878,2213,2497,2626,232,2581,2604,688,518,2636,2882,1850]
    - 2: 5000
    output:
    - 1: 1609875


testcases:
  - name: "testcase 1"
    inputs:
    - 1: [9]
    - 2: 12
    output:
    - 1 : 0
  - name: "testcase 2"
    inputs:
    - 1 : [10, 20] 
    - 2 : 30
    output: 
    - 1 : 2
  - name: "testcase 3"
    inputs:
    - 1: [1, 2, 5]
    - 2: 7
    output:
    - 1 : 6
  - name: "testcase 4"
    inputs:
    - 1: [4, 5, 6]
    - 2: 0
    output:
    - 1 : 1
  - name: "testcase 5"
    inputs:
    - 1: [23, 82, 211, 469, 499, 154, 285]
    - 2: 500
    output:
    - 1 : 1
  - name: "testcase 6"
    inputs:
    - 1: [162, 18, 11, 284, 465]
    - 2: 700
    output:
    - 1 : 16

def sum(input_1, input_2):
    return input_1+input_2

def validate_inputs(self) -> None:
        """
        self.__inputs is the list of inputs that are passed as input to function
        store the result using the self.store_result(error_msg, status)
        return : void
        """
        # inputs can be accessed using self.__inputs starting from 0 to len(self.__inputs) - 1
        if self.__inputs[0] > 1000:
            self.store_result ("input 1 should be less than 1000", ValidationFunction.FAIL)
        elif self.__inputs[1] > 1000:
            self.store_result("input 2 should be less than 1000", ValidationFunction.FAIL)
        else:
            self.store_result("", ValidationFunction.PASS)


export function printList(lst){
    output = "["
    var i = 0
    for (i = 0; i < lst.length - 1; i++){
        output += lst[i] + ", "
    }
    output += lst[i] + "]"
    return output
}

import { printList } from "./print_list.js";

function countWaysRec(coins, amount, maximum){

  // base case 1
  if (amount == 0) return 1;

  // base case 2
  if (amount < 0) return 0;
  
  var ways = 0;

  // iterate over coins
  for (let i = 0; i < coins.length; i++) {
    
    // to avoid repetition of similar sequences, use coins smaller than maximum
	  if (coins[i] <= maximum  && amount - coins[i] >= 0)

      // notice how maximum is set to the current value of coin in recursive call
		  ways = ways + countWaysRec(coins, amount - coins[i], coins[i]); 
  }
   return ways;
}

function countWays(coins, amount){
	let max = Math.max.apply(Math, coins);
  return countWaysRec(coins, amount, max);
}

export { countWays };

// Driver code
function main() {
  let coinsLists = [[7], [1, 2, 5], [10], [49, 233, 96, 132, 188], 
                    [310, 278, 99, 326, 5, 575, 569, 15, 141, 54], 
                    [2823, 4551, 1750, 49, 3256, 405, 380, 4785, 3893, 874],
                    [17, 1422, 30, 1153, 1275], [1460], [9, 10, 11]];

  let amounts = [9, 5, 10, 225, 350, 3200, 700, 2000, 0];

	// You can uncomment the lines below and check how this recursive solution causes a time-out 

  // coinsLists.push([1310,3198,2445,4157,2691,1315,2272,1683,2096,317,2288,3914,3758,1114,2137,1087,
  //                    790,1761,3372,4592,2032,3235,4585,868,3556,1124,2899,4714,2833,1792,4832,674,4918,
  //                    1829,1020,412,633,1771,1989,4977,4976,1937,3999,2660,3484,352,2695,65,1073,323,3332,
  //                    4777,2979,3493,3940,350,2791,861,4558,1689,421,4988,1040,4931,2090,2727,1433,301,
  //                    3883,570,1657,820,1746,2642,292,3780,3497,3363,2469,2631,1497,4451,1234,2211,4661,
  //                    1448,4391,310,4878,2213,2497,2626,232,2581,2604,688,518,2636,2882,1850])
  // amounts.push(5000)
  
  for (let i = 0; i < coinsLists.length; i++) {
      let numWays = countWays(coinsLists[i], amounts[i]);
      console.log(i + 1 + ".\tCoins:", printList(coinsLists[i]),
                          "\n\tAmount:", amounts[i],
                          "\n\n\tNumber of Ways:", numWays);

      console.log("-".repeat(100));
  }
}

main();

JavaScript

Let's solve the Coin Change II problem using Dynamic Programming.

Getting Started

0/1 Knapsack

Unbounded Knapsack

Recursive Numbers

Longest Common Substring

Palindromic Subsequence

Conclusion

Coin Change II