Micro-questions over the 2-D DP module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. Longest common subsequence
1. State the problem.
Answer
Given two sequences, find the longest sequence appearing in both, in order but not necessarily contiguously.
2. What is the decision?
Answer
Look at the last character of each. Do they match?
3. Give state, transition and base.
Answer
STATE: L[i][j] = LCS length of a[:i] and b[:j].
TRANSITION: if a[i-1] == b[j-1], L[i][j] = L[i-1][j-1] + 1; else L[i][j] = max(L[i-1][j], L[i][j-1]).
BASE: L[0][j] = L[i][0] = 0.
4. Justify the mismatch branch.
Answer
One of the two characters cannot be in the LCS, and you take the better of dropping each.
5. Where does the answer sit?
Answer
The bottom-right cell.
6. What is the only place the table grows, and why does that matter?
Answer
The +1 on the diagonal. Everywhere else it copies the better neighbour — which is why the diagonal steps, traced backwards, spell out the subsequence.
7. Describe reconstruction.
Answer
Start bottom-right and walk backwards, asking which rule produced each cell: on a character match take the diagonal and emit it; otherwise move to whichever neighbour holds the larger value.
8. Is the LCS unique?
Answer
No — several may share the maximum length. The tie-break in the >= comparison decides which one you get, and that comparison is your lever if the problem demands a specific one.
B. 0/1 knapsack
9. State the problem.
Answer
Items with weights and values, a capacity. Each item may be taken at most once. Maximise value.
10. Give state, transition and base.
Answer
STATE: K[i][w] = best value using only the first items within capacity .
TRANSITION: K[i][w] = max(K[i-1][w], K[i-1][w - wt[i]] + val[i]).
BASE: K[0][w] = 0.
11. Which part of the transition is the “0/1”?
Answer
The K[i-1][...] on both branches. Both options consult the row above — the state with item not yet considered — which is exactly what stops the item being used twice.
12. How do you reconstruct which items were taken?
Answer
K[i][w] != K[i-1][w] means the value changed when item became available, so item was taken. Subtract its weight and continue up. Same backwards walk as LCS, asking a different question.
C. The loop direction
13. Collapsing knapsack to one row, which inner loop direction is correct?
Answer
Downwards — for w in range(cap, wt - 1, -1).
14. Explain precisely why.
Answer
Going downwards, larger indices are written first, so when you read row[w - wt] — a smaller index — it has not yet been touched this iteration and still holds the previous row’s value, the state before item was available.
15. What does the upward loop do instead?
Answer
row[w - wt] was already updated this iteration, so it may already include item — and adding val again uses the item twice.
16. Is the upward loop simply broken?
Answer
No — it is the correct solution to the unbounded knapsack, where items may be reused. Two problems, one line of difference, and the line is a loop direction.
17. Why is “which way does the loop go?” a real interview question?
Answer
Because it silently changes which problem you solved, and the bug survives casual testing — the lab’s first instance gives 9 either way.
18. Give an instance that exposes it.
Answer
Weight [3], value [5], capacity 9: 0/1 gives 5, the upward loop gives 15 — the single item used three times.
D. Edit distance
19. What is edit distance, and what is it built into?
Answer
Fewest single-character insertions, deletions and replacements turning one string into another — Levenshtein distance, what spell-checkers and diff are built on.
20. Give state, transition and base.
Answer
STATE: D[i][j] = edits to turn a[:i] into b[:j].
TRANSITION: if characters match, D[i][j] = D[i-1][j-1] (free); else D[i][j] = 1 + min(D[i-1][j], D[i][j-1], D[i-1][j-1]).
BASE: D[i][0] = i, D[0][j] = j.
21. Why do these base cases carry real content, unlike LCS’s?
Answer
Turning "kit" into "" costs 3 deletions, so the first column counts upward. LCS’s row of zeros says only “an empty sequence shares nothing”.
22. What does each of the three neighbours correspond to?
Answer
Above is a deletion, left is an insertion, diagonal is a replacement (or a free match).
23. Why does that correspondence matter?
Answer
It is what turns a number into a usable edit script — which is what diff prints.
E. Traps
24. What is the off-by-one between table and strings?
Answer
The table is , so L[i][j] concerns a[i-1] and b[j-1]. Mixing conventions mid-function is the most common source of a table that is almost right.
25. What happens if you copy one problem’s base row into another’s solution?
Answer
A plausible wrong table. LCS’s row 0 is all zeros; edit distance’s is 0,1,2,3,….
26. Distinguish LCS from longest common substring.
Answer
Substring must be contiguous, and it is a different recurrence — on a mismatch the value resets to 0 rather than taking a max, and the answer is the largest cell anywhere rather than the bottom-right.
27. Is knapsack polynomial?
Answer
No. is pseudo-polynomial, linear in the capacity’s value. A capacity of is infeasible, and 0/1 knapsack is NP-hard.
28. What is the testing lesson?
Answer
One passing example is not a test — which is why the lab runs 300 random instances against brute force.
29. Summarise 2-D DP in one sentence.
Answer
A table indexed by two prefixes, where the decision at each cell is a small fixed set of moves — and the direction you fill it in is the difference between two different problems.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Classic Two-Dimensional DP — the module
- Classic 1-D DP — Question Bank
- Memoisation & Tabulation — Question Bank
Software engineering
Infrastructure & security
Computer science
Hardware & engineering