Skip to content
Tech Interview Prep
Technical interview guide

2-D Dynamic Programming

DP where the subproblem needs two indices: grid paths, two-string comparisons, and knapsack-style capacity constraints.

Read
46 min
Practice MCQs
25
Interview Q&A
25
Edition
v7
Editorial status
Reviewed

Scope: Language-neutral, with memoisation and recursion behaviour cited from CPython 3.14.

Curated: · Written: · Reviewed:

25 questions

MCQ-1A toll road has n booths in a line, each charging cost[i]. A driver starts with B free-toll credits, each credit cancelling one booth's charge, and may use at most B credits. The recurrence is dp[i][b] = min(cost[i] + dp[i-1][b-1], dp[i-1][b]), where dp[i][b] is the minimum cash paid to pass the first i booths with b credits still unused. Which statement explains why the table needs both indices rather than i alone?
MCQ-2A robot moves on a grid with 4 rows and 4 columns, from the top-left cell to the bottom-right cell, moving only right or down. The cell at row 1, column 1 (0-indexed) is blocked and cannot be entered. Using the standard path-counting recurrence, how many valid paths exist?
MCQ-3A robot starts at the top-left of a 3×4 grid and moves only right or down to reach the bottom-right. Cells (0,1) and (1,2) are blocked, using 0-indexed (row, column). With dp[i][j] = number of paths to (i,j), how many paths reach (2,3)?
MCQ-4A tolling service prices routes on a 3x3 grid of per-cell charges. Read row by row from the top, the charges are: row 1 = 1, 1, 40; row 2 = 2, 50, 40; row 3 = 2, 2, 2. A vehicle enters at the top-left cell and must leave from the bottom-right, moving only right or down, and pays the charge of every cell it occupies, the entry and exit cells included. The developer fills a table with the recurrence dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) and seeds dp[0][0] with the charge of the entry cell. What is the lowest total charge the vehicle can pay?
MCQ-5A plagiarism checker tokenises two submissions into the strings a = "ABCBDAB" and b = "BDCABA". It scores a pair by the length of their longest common subsequence divided by the length of the shorter string, and flags the pair when that score is at least 0.6. Which outcome does it produce for this pair?
MCQ-23A developer writes this LCS function using a 1-indexed DP table: ```python def lcs(a, b): m, n = len(a), len(b) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if a[i - 1] == b[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[m - 1][n - 1] ``` What does `lcs("ABC", "AC")` return?
MCQ-24X = "ABCBDAB", Y = "BDCABA" (0-based indexing). The LCS table dp[0..7][0..6] is retained. Traceback starts at i=7, j=6, where dp[7][6]=4. The rule is: if X[i-1] == Y[j-1]: take X[i-1]; i -= 1; j -= 1 elif dp[i-1][j] >= dp[i][j-1]: i -= 1 else: j -= 1 The relevant cells are dp[6][6]=4 and dp[7][5]=4. After the first character is appended to the output, which cell is the traceback at?
MCQ-6A fuzzy-match service computes Levenshtein distance between short tokens. Its table is initialized with dp[0][j] = 0 and dp[i][0] = 0, then filled with the standard recurrence. For the pair 'cat' and 'act' it returns 1, but the correct distance is 2. What is the cause?
MCQ-19A diff service computes Levenshtein distance between two 30,000-character strings. Its full DP table is (30,001)² int32 cells: about 3.6 GB, and the service is OOM-killed at its 2 GB limit. An engineer replaces the table with two rolling rows of length 30,001. What should they expect?
MCQ-22A service computes the edit distance between two strings of length 4,000 and 6,000 using top-down memoised recursion in CPython 3.12 (default recursion limit 1,000). Each call f(i, j) recurses on f(i-1, j) or f(i, j-1). What happens on the first request?
MCQ-18A service computes the edit distance between two 20,000-character strings. The DP table is (20,001)^2 32-bit integers. The container has a 512 MiB memory limit and a 5-second CPU budget. The team needs only the final distance, not the alignment. Which plan meets both limits?
MCQ-20Two DNA sequences of 10,000 bases each must be globally aligned, and the alignment itself, not just the score, is required. The DP matrix uses 4-byte cells and the box has 64 MB of free RAM. Which plan produces the alignment within that budget?
MCQ-7A search service scores typed queries against dictionary terms with edit distance, using insert cost 1, delete cost 5, substitute cost 2. It memoizes each pair in a dict keyed by frozenset({query, term}). Computing ('ab', 'abc') stores 1. A later lookup of ('abc', 'ab') hits that entry and returns 1. Which statement is correct?
MCQ-8In the classic dynamic programming formulation for 0/1 knapsack where DP[i][w] denotes the maximum value achievable considering a subset of the first i items with total capacity w, what does the expression DP[i - 1][w - weight[i]] + value[i] represent, and under what condition is this transition valid?
MCQ-9A 0/1 knapsack DP was collapsed from a two-row table to a single array. Items are (weight, value): (2, 3), (3, 4), (4, 5); capacity is 7. The collapsed code is: ```python dp = [0] * 8 for i in range(3): for w in range(wt[i], 8): # capacities run upward dp[w] = max(dp[w], dp[w - wt[i]] + val[i]) ``` What does `dp[7]` hold when both loops finish?
MCQ-10A team fills a boolean table DP[i][s] row by row and must report whether any subset of the given positive integers sums exactly to S, with each element used at most once. Their current code returns true for nums = [4, 6] with S = 8, where the correct answer is false. Which recurrence is correct, and which knapsack problem does it correspond to?
MCQ-25A team is writing a 0/1 knapsack solver. There are n = 100 items; each weight is up to 10^9, each value is at most 10^3, and the capacity is W = 10^9. The first draft states the subproblem as "the best value using the first i items at total weight exactly w" and allocates an (n+1) x (W+1) table of 8-byte longs; the allocation fails. Which restatement of the subproblem should they adopt?
MCQ-21A knapsack-style DP in Python recurses over states (i, w) with 0 ≤ i ≤ 500 and 0 ≤ w ≤ 200,000; instrumentation shows 120,000 distinct states are actually reached. It runs top-down with a dict memo keyed by the packed state index, inside a container limited to 512 MB. A teammate proposes replacing the memo with a dense (501, 200,001) array of 64-bit integers. What happens?
MCQ-13A team counts palindromic substrings of `s = "aabaa"` (0-indexed, `n = 5`) by filling a boolean table `dp`, initialised to `False`, with this Python 3 loop: ```python for i in range(n): for j in range(i, n): if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]): dp[i][j] = True ``` They count one palindrome per `True` cell. What does the loop report, and why?
MCQ-12In the classic matrix chain multiplication DP, dp[i][j] is the minimum scalar multiplication cost for multiplying matrices i through j. What determines the order in which the table must be filled?
MCQ-14An interviewer asks you to write the matrix-chain multiplication recurrence on the whiteboard, with dp[i][j] the minimum scalar multiplications for matrices i through j and matrix i of size p[i-1] x p[i]. Which statement gives the recurrence, the split point k, and the base case correctly?
MCQ-11A team implements interval DP for the minimum-cost stone merge problem: merging a range of piles costs the sum of their weights, and the goal is to merge all piles into one at minimum total cost. Their implementation is below. For weights = [6, 4, 4, 6], what does merge_cost return? ```python def merge_cost(weights): n = len(weights) prefix = [0] * (n + 1) for i, w in enumerate(weights): prefix[i + 1] = prefix[i] + w dp = [[0] * n for _ in range(n)] for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 best = float('inf') for k in range(i, j): best = min(best, dp[i][k] + dp[k + 1][j]) dp[i][j] = best + prefix[j + 1] - prefix[i] return dp[0][n - 1] ```
MCQ-16An interval DP (matrix-chain style) over n = 600 items fills dp[i][j] for every i ≤ j, and for each cell scans every split point k with i ≤ k < j. Roughly how many split-loop iterations does the whole table perform?
MCQ-17A team computes dp[i][j] = min_{i ≤ k < j} (dp[i][k] + dp[k+1][j]) + w(i,j) for 1 ≤ i < j ≤ n, with n = 3000. The plain O(n³) loop is too slow, so they plan to restrict the k loop for each (i,j) to the window [opt(i,j-1), opt(i+1,j)]. Before merging, they dump the optimal split points for row i = 5 from the reference DP: | j | 6 | 7 | 8 | 9 | 10 | |---|---|---|---|---|---| | opt(5,j) | 5 | 5 | 7 | 6 | 8 | What should the reviewer conclude?
MCQ-15A service must count how many integers x in the closed range [0, N] have no two adjacent equal decimal digits, for N = 100. The intended solution fills a table position by position with state (position, last digit placed, tight flag), where tight records whether the prefix so far equals the prefix of N. Which statement correctly describes the state the memo must carry and the resulting count?