Skip to content
Tutorials Center
My learning

Topics

Lesson 47 of 77 ยท CS Fundamentals Interview Questions

Recursion and Dynamic Programming Questions

Master recursion and dynamic programming interview questions: memoization, knapsack, longest increasing subsequence, edit distance and backtracking in Python.

Dynamic programming (DP) has a reputation for being the hardest interview topic, but it follows one recipe. You write a plain recursive solution, notice that it solves the same subproblems again and again, and then store the answers. This lesson walks through that recipe and applies it to the problems you are most likely to be asked, ending with backtracking, the sibling technique for "generate all the ways".

Background: Memoization and tabulation, Knapsack and Backtracking.

The DP recipe

State What do I need to know to solve a subproblem?
Recurrence How does a big answer use smaller ones?
Base case Where does the recursion stop?
Cache Memoize or fill a table.
1 / 2

Recursion and memoization

Q: What are the two ingredients of recursion? A base case that stops, and a recursive step that moves toward it. Missing the base case causes a RecursionError (stack overflow in other languages). Q: When does DP apply? When the problem has overlapping subproblems (the same call repeats) and optimal substructure (the best answer is built from best answers of smaller pieces).

Fibonacci is the standard demonstration. The naive version makes an exponential number of calls because fib(n - 2) is recomputed inside fib(n - 1). Caching each result makes it O(n).

Python Naive recursion versus memoization

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last function is tabulation (bottom-up): fill answers from the smallest case up. Because each value needs only the previous two, you can keep two variables instead of a whole table, which is O(1) space. Top-down memoization is easier to write; bottom-up avoids recursion limits.

0/1 knapsack

Q: Given items with weights and values and a bag of capacity W, maximize value when each item is used at most once. State: dp[w] is the best value using capacity w. For each item, you either skip it or take it: dp[w] = max(dp[w], dp[w - weight] + value). Loop capacity downward so an item is not used twice in the same pass. Time is O(n * W), space O(W).

Python Knapsack with a one-dimensional table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With capacity 4, taking the weight-4 item gives 30, but taking the weight-1 and weight-3 items gives 35. If items can be reused (unbounded), the weight-1 item four times gives 60. The only change is iterating capacity upward. Related: coin change and "partition equal subset sum" are knapsack in disguise.

Longest increasing subsequence

Q: Find the length of the longest strictly increasing subsequence. A subsequence keeps order but not adjacency. The simple DP is O(nยฒ): dp[i] is the length of the best subsequence ending at index i, which equals 1 plus the best dp[j] over earlier j with nums[j] < nums[i]. A faster O(n log n) version keeps a tails list, where tails[k] is the smallest possible last value of an increasing subsequence of length k + 1, and uses binary search to place each number.

Python LIS in O(nยฒ) and O(n log n)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Warn the interviewer that tails is not the subsequence itself, only a tool to get its length. Using bisect_left keeps the subsequence strictly increasing; bisect_right would allow equal values.

Edit distance

Q: What is the minimum number of insertions, deletions and substitutions to turn word A into word B? State: dp[i][j] is the distance between the first i letters of A and the first j letters of B. If the letters match, copy the diagonal. Otherwise take 1 plus the minimum of delete (up), insert (left) and substitute (diagonal). The first row and column are the cost of building from or reducing to an empty string. Time and space are O(len(A) * len(B)).

Python Edit distance table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If asked to optimize space, note that each row depends only on the previous row, so two rows suffice.

Backtracking

Q: Generate all subsets, permutations or valid combinations. Backtracking is recursion that builds a candidate step by step: choose an option, explore with a recursive call, then un-choose (undo) so the next option starts clean. Prune branches that cannot succeed. Unlike DP, you want every solution, so the cost is usually exponential and you cannot avoid it.

Python Subsets and combinations that sum to a target

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two details interviewers look for: copy the path (path[:]) before storing it, otherwise every result points at the same list that keeps changing, and sort the candidates so the break prune is valid. Passing i (not i + 1) lets the same number be reused.

Greedy and DP classics: job sequencing, Huffman, matrix chain and two subsequence variants

These five show up in "top algorithms" lists. Two are greedy, three are dynamic programming. Before coding, say which family it is and why: greedy works when a locally best choice can be proven safe (an exchange argument), DP works when the problem has optimal substructure and overlapping subproblems.

Job sequencing with deadlines (greedy)

Problem: each job takes one unit of time, has a deadline (the latest slot it may occupy) and a profit. Schedule a subset to maximize total profit.

Greedy rule: consider jobs by decreasing profit and put each one in the latest free slot at or before its deadline. A late slot leaves the early slots free for jobs with tighter deadlines. If no slot is free, drop the job. Sorting costs O(n log n) and the naive slot search makes the whole thing O(nยทd); a disjoint-set union over slots brings the search down to nearly constant time.

Python Job sequencing with a slot table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Huffman coding (greedy)

Problem: assign a binary code to each symbol so that no code is a prefix of another and the encoded message is as short as possible, given symbol frequencies.

Greedy rule: repeatedly take the two least frequent nodes from a min-heap, merge them into a parent whose weight is their sum, and push it back. Rare symbols end up deep in the tree (long codes) and common ones near the root (short codes). The result is optimal among prefix codes. With a heap the cost is O(n log n).

Different tie-breaking gives different (but equally good) trees, so compare code lengths and the total bits, not the exact bit strings.

Python Huffman code lengths from a heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Matrix chain multiplication (interval DP)

Problem: multiplying matrices is associative, but the order changes the number of scalar multiplications. Given dimensions dims where matrix i is dims[i-1] x dims[i], find the cheapest order.

Define cost[i][j] as the minimum cost to multiply matrices i..j. Try every split point k between them: cost[i][k] + cost[k+1][j] + dims[i-1]*dims[k]*dims[j]. Fill the table by increasing chain length. That is O(nยณ) time and O(nยฒ) space. This is the model "interval DP" problem; burst balloons and optimal BST have the same shape.

Python Cheapest multiplication order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Maximum sum increasing subsequence

Problem: among strictly increasing subsequences of an array, find the one with the largest sum (not length).

This is the longest increasing subsequence with a different value. Let best[i] be the largest sum of an increasing subsequence that ends at index i. Then best[i] = a[i] + max(best[j] for j < i if a[j] < a[i]), or just a[i] if there is no such j. The answer is the maximum over all i. It is O(nยฒ); unlike plain LIS there is no simple O(n log n) binary-search trick, though a Fenwick tree over values gets there.

Python Best increasing sum, with the subsequence

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Longest repeating subsequence

Problem: find the longest subsequence that appears at least twice in a string, where the two copies may not use the same index in the same position.

Run the longest common subsequence (LCS) of the string with itself, but forbid matching a character with itself: when s[i-1] == s[j-1] and i != j, take 1 + dp[i-1][j-1]; otherwise take the larger of the two neighbors. Time and space are O(nยฒ).

Python LCS of a string with itself, minus the diagonal

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Greedy or DP? How to tell

If a counterexample breaks the greedy rule (coin change with coins 1, 3, 4 and target 6: greedy picks 4+1+1, optimal is 3+3), use DP. If the greedy choice can be justified by an exchange argument (job sequencing, Huffman, activity selection), the greedy code is shorter and faster. Interviewers care that you can name the argument.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which two properties tell you that dynamic programming applies?

    Repeated subproblems make caching worthwhile, and optimal substructure lets you combine smaller best answers.
  2. 2. Why does the one-dimensional 0/1 knapsack loop over capacity from high to low?

    Going downward means dp[w - weight] still holds the value from before this item was considered.
  3. 3. What is the time complexity of the O(n log n) LIS algorithm's key step?

    Each of the n numbers does one binary search (O(log n)) to find where it belongs.
  4. 4. In backtracking, why do you store path[:] instead of path?

    path is mutated by append and pop, so a stored reference would end up showing the final (empty) state.
  5. 5. The edit distance between "kitten" and "sitting" is:

    Substitute k with s, substitute e with i, and insert g: three operations.

Summary

  • Write the plain recursion first, then add a cache where subproblems repeat.
  • Memoization is top-down; tabulation is bottom-up and can often shrink space.
  • Knapsack: iterate capacity downward for 0/1, upward for unlimited reuse.
  • LIS: O(nยฒ) DP, or O(n log n) with a tails list and binary search.
  • Edit distance: a two-dimensional table with delete, insert and substitute.
  • Backtracking: choose, explore, un-choose, and prune; copy results before storing.
  • Job sequencing and Huffman are greedy (sort by profit, merge the two lightest nodes); matrix chain, max-sum increasing subsequence and longest repeating subsequence are DP.
  • Choose greedy only when an exchange argument proves the local choice safe; coins 1, 3, 4 with target 6 is the classic counterexample.

Next: OOP, SOLID and Design Patterns Questions.