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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Dynamic Programming