Dynamic programming Interview Questions

What Dynamic programming interviews cover

Sample Dynamic programming interview questions

• Explain the difference between memoization and tabulation in DP.
  What a strong answer covers

  • Memoization is a top-down approach that caches results of expensive function calls.
  • Tabulation is a bottom-up approach that builds a table iteratively from base cases.
  • Memoization uses recursion with lazy evaluation; tabulation typically uses iteration.
  • Memoization may have overhead due to recursion and cache lookups; tabulation avoids recursion overhead.
  • Both reduce time complexity by solving overlapping subproblems once.

  View a sample answer

  Memoization and tabulation are two fundamental techniques in dynamic programming to solve problems with overlapping subproblems. Memoization works top-down: it starts with the original problem and recursively breaks it into subproblems, caching results as they are computed. This approach is often easier to implement because it directly mirrors the recursive formulation. However, it can suffer from recursion depth limits and overhead from function calls and cache management. Tabulation, on the other hand, is bottom-up: it solves all subproblems in a systematic order, typically starting from the smallest base cases and building up to the desired solution. Tabulation avoids recursion entirely, which can be more efficient in terms of space and time, and is often preferred when the order of subproblem dependencies is straightforward. The choice between them depends on the problem, language, and constraints. For example, memoization is natural for problems where the subproblem graph is not fully known, while tabulation is better when the entire table size is predictable.

• Implement Fibonacci numbers using DP (both top-down and bottom-up).
  What a strong answer covers

  • Top-down DP uses memoization with recursion and a cache array.
  • Bottom-up DP iteratively computes from base cases up to n.
  • Both achieve O(n) time and O(n) space.
  • Base cases: fib(0)=0, fib(1)=1.
  • Code must handle edge cases like n=0.

  View a sample answer

  The Fibonacci sequence is a classic example to demonstrate dynamic programming because it has overlapping subproblems. The top-down approach uses recursion with memoization: we store previously computed Fibonacci numbers in an array to avoid redundant calculations. The bottom-up approach builds a table iteratively from the base cases up to the desired n. Both have linear time complexity O(n) and linear space O(n) if we store all values. We can optimize space to O(1) in the bottom-up approach by keeping only the last two numbers. The code below shows both methods, including comments and time/space complexity.

  def fib_top_down(n, memo=None):
      if memo is None:
          memo = {0: 0, 1: 1}
      if n in memo:
          return memo[n]
      memo[n] = fib_top_down(n-1, memo) + fib_top_down(n-2, memo)
      return memo[n]
  
  def fib_bottom_up(n):
      if n <= 1:
          return n
      dp = [0] * (n+1)
      dp[0], dp[1] = 0, 1
      for i in range(2, n+1):
          dp[i] = dp[i-1] + dp[i-2]
      return dp[n]
  
  # Time: O(n) for both, Space: O(n) for memo/tabulation, O(1) space possible for bottom-up

• Given a set of items with weights and values, solve the 0/1 knapsack problem for maximum value.
  What a strong answer covers

  • 0/1 knapsack: each item can be taken at most once.
  • Use a 2D DP table where dp[i][w] = max value with first i items and capacity w.
  • Transition: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) if weight[i] <= w.
  • Space can be optimized to 1D array by iterating capacity backward.
  • Time complexity O(n*W), space O(W) after optimization.

  View a sample answer

  The 0/1 knapsack problem involves selecting a subset of items with given weights and values to maximize total value without exceeding capacity. The standard DP solution uses a 2D table where rows represent items and columns represent remaining capacity. The recurrence relation considers whether to include the current item or not. To save space, we can reduce the DP to a 1D array by iterating capacity from high to low, ensuring each item is used at most once. The code below implements the optimized version.

  def knapsack(weights, values, capacity):
      n = len(weights)
      dp = [0] * (capacity + 1)
      for i in range(n):
          for w in range(capacity, weights[i]-1, -1):
              dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
      return dp[capacity]
  
  # Time: O(n*capacity), Space: O(capacity)

• Find the length of the longest increasing subsequence in an array.
  What a strong answer covers

  • LIS: find longest subsequence (not necessarily contiguous) that is strictly increasing.
  • O(n^2) DP: dp[i] = length of LIS ending at index i.
  • Transition: dp[i] = 1 + max(dp[j]) for j < i and arr[j] < arr[i].
  • O(n log n) using patience sorting: maintain tails array of smallest possible tail for each length.
  • Both return length; LIS itself can be reconstructed with parent pointers.

  View a sample answer

  The longest increasing subsequence problem asks for the length of the longest subsequence where elements are in sorted order. The basic DP approach uses an array dp where dp[i] stores the length of the longest increasing subsequence ending at index i. We compute dp[i] by scanning previous elements. This yields O(n^2) time. For larger inputs, we can use a binary search approach (patience sorting) with a tails array that maintains the smallest possible tail value for each subsequence length, achieving O(n log n). The code below implements both methods with comments.

  def length_of_LIS(nums):
      # O(n^2) DP
      if not nums:
          return 0
      n = len(nums)
      dp = [1] * n
      for i in range(n):
          for j in range(i):
              if nums[j] < nums[i]:
                  dp[i] = max(dp[i], dp[j] + 1)
      return max(dp)
  
  def length_of_LIS_optimized(nums):
      # O(n log n) tails array
      import bisect
      tails = []
      for x in nums:
          i = bisect.bisect_left(tails, x)
          if i == len(tails):
              tails.append(x)
          else:
              tails[i] = x
      return len(tails)
  
  # Time: O(n^2) for first, O(n log n) for second; Space: O(n)

• Compute the edit distance (Levenshtein distance) between two strings.
  What a strong answer covers

  • Edit distance: minimum operations (insert, delete, replace) to convert string1 to string2.
  • DP table dp[i][j] = distance between first i chars of s1 and first j chars of s2.
  • Base: dp[0][j] = j, dp[i][0] = i.
  • Transition: if s1[i-1] == s2[j-1] then dp[i][j] = dp[i-1][j-1] else dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
  • Time O(m*n), Space O(m*n), can optimize to O(min(m,n)) space.

  View a sample answer

  Levenshtein distance (edit distance) measures the minimum number of single-character edits (insert, delete, substitute) to transform one string into another. The classic DP solution builds a 2D table where each cell (i,j) represents the distance between the first i characters of string1 and first j characters of string2. The recurrence handles equality and the three operations. The base cases correspond to converting an empty string. Space can be optimized to O(min(m,n)) by only keeping two rows if needed, but the code below uses full table for clarity.

  def edit_distance(s1, s2):
      m, n = len(s1), len(s2)
      dp = [[0]*(n+1) for _ in range(m+1)]
      for i in range(m+1):
          dp[i][0] = i
      for j in range(n+1):
          dp[0][j] = j
      for i in range(1, m+1):
          for j in range(1, n+1):
              if s1[i-1] == s2[j-1]:
                  dp[i][j] = dp[i-1][j-1]
              else:
                  dp[i][j] = 1 + min(dp[i-1][j],    # delete
                                     dp[i][j-1],    # insert
                                     dp[i-1][j-1])  # replace
      return dp[m][n]
  
  # Time: O(m*n), Space: O(m*n)

• Solve the coin change problem: minimum number of coins to make a given amount.
  What a strong answer covers

  • Coin change: given coin denominations and amount, find minimum number of coins to make amount.
  • DP: dp[i] = min coins to make amount i.
  • Initialize dp[0]=0, others to infinity.
  • Transition: for each coin, dp[i] = min(dp[i], dp[i-coin]+1).
  • If dp[amount] is infinity, return -1 (impossible).

  View a sample answer

  The coin change problem (minimum coins) is a classic unbounded knapsack problem. The DP solution uses a 1D array dp where dp[i] is the minimum number of coins needed to achieve amount i. We initialize dp[0] = 0 and all other entries to a large number. Then for each amount from 1 to target, we try every coin denomination and update dp[i] if using that coin yields a smaller count. The time complexity is O(amount * number of coins). If the amount cannot be made, we return -1.

  def coin_change(coins, amount):
      dp = [float('inf')] * (amount + 1)
      dp[0] = 0
      for i in range(1, amount+1):
          for coin in coins:
              if coin <= i:
                  dp[i] = min(dp[i], dp[i-coin] + 1)
      return dp[amount] if dp[amount] != float('inf') else -1
  
  # Time: O(amount * len(coins)), Space: O(amount)

• Count the number of ways to climb a staircase with 1 or 2 steps at a time.
  What a strong answer covers

  • Climbing stairs: each step can be 1 or 2 steps, count ways to reach top.
  • DP recurrence: dp[n] = dp[n-1] + dp[n-2] (like Fibonacci).
  • Base: dp[1] = 1, dp[2] = 2.
  • Space can be O(1) using two variables.
  • This is a simple DP, often used to introduce DP concepts.

  View a sample answer

  The staircase problem is a fundamental DP example. The number of ways to reach step n is the sum of ways to reach step n-1 (then take 1 step) and step n-2 (then take 2 steps). This recurrence is identical to Fibonacci, but with base cases: for n=1, only 1 way; for n=2, two ways (1+1 or 2). The solution can be computed iteratively in O(n) time with O(1) space by keeping only the previous two values. Below is the implementation.

  def climb_stairs(n):
      if n <= 2:
          return n
      first, second = 1, 2
      for i in range(3, n+1):
          third = first + second
          first, second = second, third
      return second
  
  # Time: O(n), Space: O(1)

• Describe the step-by-step approach to solve any DP problem, from identifying subproblems to coding the solution.
  What a strong answer covers

  • 1. Identify if problem has optimal substructure and overlapping subproblems.
  • 2. Define the state (usually using indices or parameters).
  • 3. Formulate recurrence relation (transition).
  • 4. Decide base cases.
  • 5. Choose top-down (memoization) or bottom-up (tabulation) and implement.
  • 6. Optimize space if possible.

  View a sample answer

  To solve any DP problem systematically, follow these steps. First, verify that the problem exhibits optimal substructure (optimal solution depends on optimal solutions of subproblems) and overlapping subproblems (same subproblems are solved repeatedly). Second, define the state: decide what variables (e.g., index, remaining capacity) uniquely describe a subproblem. Third, derive the recurrence relation: how does the solution for the current state relate to smaller states? Fourth, identify base cases: the simplest subproblems that can be solved directly (e.g., empty string, zero capacity). Fifth, implement either top-down with memoization (recursive + cache) or bottom-up with tabulation (iterative table). Bottom-up is usually more efficient for dense state spaces. Finally, consider optimizing space, such as reducing a 2D table to 1D or using a few variables. Understanding these steps helps tackle any DP problem, from classic ones to novel challenges.

How to prepare

• Master common DP patterns like knapsack, LCS, and grid problems.
• Practice writing recurrence relations from scratch before coding.
• Start with brute force recursion, then add memoization, then convert to tabulation if needed.
• Use space optimization techniques (e.g., reduce 2D DP to 1D) to improve efficiency.
• Solve at least 3-4 problems from each pattern to build intuition for recognizing DP.

Frequently asked questions