Dynamic programming interview questions, with answers

The questions, with answers

1. 1.What is dynamic programming, and how do you recognise a DP problem?

   In short: DP is recursion that remembers: use it when a problem breaks into smaller subproblems that repeat, and the best answers to those subproblems combine into the best overall answer.

   The two conditions have names. Overlapping subproblems: the recursive solution asks the same smaller question many times. Optimal substructure: the best answer to the whole is built from best answers to its parts. Merge sort also builds its answer from the answers to subproblems, but its halves never repeat, so it is divide and conquer, not DP. The wording of a question usually gives DP away: count the ways, find the minimum cost or the maximum value, or decide whether something is possible, where each step is a choice (take this item or not, climb one stair or two) and the choices interact. When you see that shape, the first job is not the table; it is naming the state, the smallest set of values that describes one subproblem, such as 'the first i houses' or 'the amount still to make'.

2. 2.How do you go from a plain recursive solution to memoisation to a table?

   In short: Write the recursion first, add a cache keyed by the subproblem, then fill the same values bottom-up in an order where each one is ready before anything needs it.

   Take the house robber problem: houses in a row hold amounts, you cannot rob two adjacent houses, and you want the maximum. The recursion says that at house i you either skip it and keep the best of the first i − 1 houses, or rob it and add its value to the best of the first i − 2. As plain recursion that is exponential, because the best of i − 2 is recomputed inside the best of i − 1. With a memo array each value is computed once, so the time drops to O(n). Tabulation fills the values left to right, which removes the recursion depth, and since each value needs only the previous two, two variables can replace the array for O(1) space. For the houses 6, 7, 1, 30, 8, 2, 4 every version returns 41: the houses holding 7, 30 and 4.

   int rob(int[] v, int i) {                          // 1. plain recursion: exponential
       if (i < 0) return 0;
       return Math.max(rob(v, i - 1), rob(v, i - 2) + v[i]);
   }
   
   int robMemo(int[] v, int i, Integer[] memo) {      // 2. memoisation: O(n)
       if (i < 0) return 0;
       if (memo[i] != null) return memo[i];
       return memo[i] = Math.max(robMemo(v, i - 1, memo), robMemo(v, i - 2, memo) + v[i]);
   }
   
   int robTable(int[] v) {                            // 3. table as two variables: O(n) time, O(1) space
       int prev2 = 0, prev1 = 0;                      // best of the first i-2 and i-1 houses
       for (int x : v) {
           int cur = Math.max(prev1, prev2 + x);
           prev2 = prev1;
           prev1 = cur;
       }
       return prev1;
   }

3. 3.When is memoisation the better choice, and when is tabulation?

   In short: Memoise when only some subproblems are ever reached or the evaluation order is awkward; tabulate when every subproblem is needed, recursion depth is a risk, or you want to cut the space.

   Both compute each subproblem once, so they share the same time complexity; the difference is in what surrounds it. Memoisation is the recursion you already wrote plus a cache, it evaluates only the states the answer actually depends on, and it needs no evaluation order worked out. Its price is the call stack: the memoised house robber above, run on 100,000 houses, overflows Java's default stack, and Python's default recursion limit is 1,000. Tabulation needs the order worked out — usually row by row for a two-dimensional table — but it has no depth limit and makes space savings visible: when row i needs only row i − 1, keep two rows instead of the whole table. In an interview, say the recursion, memoise it, and offer the table as the follow-up.

4. 4.What are the classic dynamic programming problems, and what is each one's recurrence?

   In short: Eight cover most fresher rounds: climbing stairs, house robber, coin change, 0/1 knapsack, longest common subsequence, longest increasing subsequence, edit distance and grid paths.

   Learn each one as a state and a recurrence, not as code; the block below gives each recurrence with its base cases on the lines marked base. Two patterns cover all eight. The one-dimensional problems look back a fixed or bounded distance: climbing stairs and house robber look back two steps, and coin change looks back by one coin's value. The two-dimensional problems pair two things: longest common subsequence and edit distance compare the first i characters of one string with the first j of the other, knapsack pairs the first i items with the capacity left, and grid paths pair a row with a column. Once the recurrence is right, the number of states gives the space, and the number of states times the work per state gives the time.

   climb(n) = climb(n-1)
            + climb(n-2)
     base: climb(0) = climb(1) = 1
   
   rob(i) = max(rob(i-1),
                rob(i-2) + v[i])
     base: rob(-1) = rob(-2) = 0
   
   coins(a) = 1 + min(coins(a-c))
     over every coin c <= a
     base: coins(0) = 0
   
   knap(i, w) = max(knap(i-1, w),
     val[i] + knap(i-1, w-wt[i]))
     (second only if wt[i] <= w)
     base: knap(0, w) = 0
   
   lcs(i, j) = lcs(i-1, j-1) + 1
     if s[i] == t[j], else
     max(lcs(i-1, j), lcs(i, j-1))
     base: lcs(0, j) = 0,
           lcs(i, 0) = 0
   
   lis(i) = 1 + max(lis(j))
     over j < i with a[j] < a[i],
     or 1 if there is no such j
     answer: the largest lis(i)
   
   edit(i, j) = edit(i-1, j-1)
     if s[i] == t[j], else
     1 + min(edit(i-1, j),
             edit(i, j-1),
             edit(i-1, j-1))
     base: edit(i, 0) = i,
           edit(0, j) = j
   
   paths(r, c) = paths(r-1, c)
               + paths(r, c-1)
     base: paths(0, c) = 1,
           paths(r, 0) = 1

5. 5.How do you work out the time and space complexity of a DP solution?

   In short: Time is the number of distinct states times the work done per state; space is the number of states you keep, which a rolling array often cuts to a single row.

   House robber has n states and constant work per state, so O(n) time. Longest common subsequence has (m + 1) × (n + 1) states with constant work each, so O(mn) time and space, or O(min(m, n)) space if only the length is needed, because each row reads only the row above it. The straightforward longest increasing subsequence has n states but scans every earlier element for each one, so O(n²). Knapsack needs care: n items times capacity W gives O(nW), which looks polynomial but is called pseudo-polynomial, because W is a number in the input rather than a count of things — adding one digit to W multiplies the work by ten. Say the state count and the per-state cost out loud; the interviewer is checking that you can, not that you have memorised the result.

6. 6.How do you solve the coin change problem, and why does greedy fail?

   In short: Build the fewest coins for every amount from 0 upwards, each from a smaller amount plus one coin; greedy fails because taking the largest coin first can lock out a better combination.

   With coins 1, 5, 6 and 9, the fewest coins for 11 is two — 5 and 6 — but greedy takes the 9 first and then needs 1 and 1, three coins in all. The DP avoids the trap by trying every coin as the last one: the fewest for an amount is one more than the fewest for that amount minus some coin, minimised over the coins that fit, with the fewest for 0 being 0. Filling the table from 0 to 11 takes O(amount × number of coins) time. The counting version, the number of ways to make the amount, has a trap of its own: loop over the coins on the outside and the amounts on the inside, or every ordering of the same coins is counted separately. With coins 1, 2 and 5 there are four ways to make 5 but nine ordered sequences.

   int fewestCoins(int[] coins, int amount) {
       int[] best = new int[amount + 1];
       java.util.Arrays.fill(best, Integer.MAX_VALUE);
       best[0] = 0;
       for (int a = 1; a <= amount; a++)
           for (int c : coins)
               if (c <= a && best[a - c] != Integer.MAX_VALUE)
                   best[a] = Math.min(best[a], best[a - c] + 1);
       return best[amount] == Integer.MAX_VALUE ? -1 : best[amount];
   }
   
   long countWays(int[] coins, int amount) {          // coins outside: each combination once
       long[] ways = new long[amount + 1];
       ways[0] = 1;
       for (int c : coins)
           for (int a = c; a <= amount; a++)
               ways[a] += ways[a - c];
       return ways[amount];
   }

7. 7.How do you recover the actual choices, not just the best value?

   In short: Keep the table and walk backwards from the answer: at each state, check which option produced the stored value, take that step, and repeat until a base case.

   For house robber with values 6, 7, 1, 30, 8, 2, 4 and houses numbered from 0, the best values are 6, 7, 7, 37, 37, 39, 41. Start at house 6: its 41 differs from house 5's 39, so house 6 was robbed; jump two back. House 4's 37 equals house 3's, so house 4 was skipped. House 3's 37 differs from house 2's 7, so house 3 was robbed; jump two back. House 1's 7 differs from house 0's 6, so house 1 was robbed. The robbed houses are 1, 3 and 6, holding 7, 30 and 4. The same walk recovers the actual subsequence for longest common subsequence and the operations for edit distance. The two-variable space saving throws this information away, so if the question asks for the choices, keep the full table or record the decision taken at each state.

8. 8.How is dynamic programming different from greedy algorithms and from backtracking?

   In short: Greedy commits to the best-looking choice and never revisits it; backtracking explores choices and undoes them; DP explores every choice too but solves each distinct subproblem only once.

   Greedy is fastest, and it is right only when a locally best choice is provably part of a globally best one — true for coin systems like 1, 2, 5, 10, 20 and 50, false for the coins 1, 5, 6 and 9 above. Backtracking enumerates candidate solutions and prunes the hopeless ones, which suits questions that want every solution, such as all subsets or all valid arrangements, where subproblems rarely repeat. DP applies when the same subproblems keep reappearing and only a best value, a count or a yes-or-no answer is wanted: it collapses the repeated branches of the backtracking tree into single table entries. A useful way to put it in an interview: backtracking with repeated states plus a cache is memoised DP.

How the diagnostic asks it

One question from the DSA bank, exactly as a sitting would show it. The bank has 12 on dynamic programming and 67 across DSA.