Dynamic Programming Questions
Solving problems with overlapping subproblems and optimal substructure by memoization (top-down) and tabulation (bottom-up). Covers recognizing DP-amenable problems, defining state, transition and base cases, 1D and 2D sequence and grid formulations (knapsack and its variants, coin change, LIS, LCS, edit distance, sequence alignment, regular-expression and wildcard matching, counting-ways problems), interval DP (matrix chain, palindrome partitioning), space optimization with rolling arrays, solution reconstruction, longest paths in a DAG, game and expected-value DP, bitmask and tree DP, speeding up a DP (monotone queue, convex hull trick, divide-and-conquer optimization, bitsets, meet in the middle), and judging greedy versus DP. Ground covered elsewhere: probabilistic model inference, production caching and debugging practice, and general graph shortest-path algorithms.
In the 1D table for counting coin-change ways, swapping the order of the coin loop and the amount loop changes what is counted. Explain what each ordering counts and why, using a tiny example, and how this relates to shrinking the 2D coins-by-amount table to one dimension.
Sample Answer
The idea
Both loop orders fill the same one-dimensional list ways with the same addition ways[a] += ways[a - coin]. What differs is which thing the value ways[a - coin] stands for at the moment it is read, and that decides whether 1+2 and 2+1 are counted once or twice.
- Coin loop outside, amount loop inside counts combinations (multisets, where order does not matter). While coin
cis being processed, only the coin types processed so far are in play, so every multiset is built in exactly one order: coin types in the order of the list. - Amount loop outside, coin loop inside counts sequences (ordered arrangements, where 1 then 2 differs from 2 then 1). Here
ways[a]is the sum, over every coin that could have been the last one placed, of the number of sequences for the remaining amount. For amount 3 with coins 1 and 2: a sequence ends in a 1 (what came before makes amount 2) or ends in a 2 (what came before makes amount 1), soways[3] = ways[2] + ways[1]. Every possible last coin, at every position, is allowed, so all orders appear.
A tiny example, from the real runs
With coins [1, 2] and amount 3 the program lists the actual objects. The multisets are (1,1,1) and (1,2), so 2. The sequences are (1,1,1), (1,2) and (2,1), so 3. The coin-outside code prints 2 and the amount-outside code prints 3, matching the lists.
The snapshots show why. For combinations, after coin 1 the row is [1, 1, 1, 1] (each amount can be made by 1s only) and after coin 2 it is [1, 1, 2, 2]: amount 3 gains one way, the 2 combined with the single 1 for amount 1. The 1 is never added after the 2, so (2,1) never appears as a separate path. For sequences, ways[3] is ways[2] + ways[1] = 2 + 1 = 3: the last coin is a 1 after any sequence for 2 (two of them), or a 2 after the one sequence for 1.
Relation to shrinking the 2D table
The combination table is dp[i][a], the number of multisets from the first i coin types that sum to a, with dp[i][a] = dp[i-1][a] + dp[i][a - coin_i], dp[i][0] = 1 and dp[0][a] = 0 for a > 0. The row i depends on the row above (dp[i-1][a]) and on itself at a smaller amount. A single list ways can stand for the row being worked on: before coin i is processed it holds row i-1, and after it holds row i. The statement ways[a] += ways[a - coin] is the transition with dp[i-1][a] already sitting in ways[a]. For ways[a - coin] to be the NEW row, the amount loop must run upward, because that entry is updated earlier in the same pass. The side-by-side printed below uses a single coin of 1 and amount 3: each line shows the cell being updated, the value it reads and the list afterwards, once going upward and once downward. The program prints the 2D table for coins [1, 2, 3] and amount 4, and confirms that the one-dimensional list after each coin equals the matching 2D row.
The direction matters. Running the amount loop downward makes ways[a - coin] still the OLD row, dp[i-1][a - coin], so each coin type is used at most once (for every coin type, a take-it-or-leave-it choice, like picking items for a knapsack). On coins [1, 2, 3] and amount 4 the downward version prints 1 (only 1+3), against 4 for the upward one.
The sequence count has no coin dimension to collapse. Its state is the amount alone, ways[a] = sum of ways[a - c] over all coins, which is why the amount loop must be the outer one: all smaller amounts have to be complete before ways[a] is read, for every coin.
The Combination Sum IV follow-up
"Combination Sum IV" (a well-known practice problem: count the ways to reach a target from distinct positive numbers, where different orders count as different) is the sequence count, despite its name. For the numbers [1, 2, 3] and target 4 the program prints 7 sequences and 4 multisets. It is also the staircase problem with steps 1, 2 and 3: for amount 40 the count is 23,837,527,729, so a 32-bit integer overflows, and a modulus or a 64-bit type is needed in fixed-width languages.
Code
import random
def combinations_1d(coins, amount, snapshots=None):
"""Coin loop OUTSIDE, amount loop inside: counts multisets (order ignored)."""
ways = [1] + [0] * amount
for coin in coins:
for a in range(coin, amount + 1):
ways[a] += ways[a - coin]
if snapshots is not None:
snapshots.append((coin, ways[:]))
return ways[amount]
def sequences_1d(coins, amount, snapshots=None):
"""Amount loop OUTSIDE, coin loop inside: counts ordered sequences."""
ways = [1] + [0] * amount
for a in range(1, amount + 1):
for coin in coins:
if a >= coin:
ways[a] += ways[a - coin]
if snapshots is not None:
snapshots.append((a, ways[:a + 1]))
return ways[amount]
def combinations_2d(coins, amount):
"""dp[i][a] = number of multisets from the first i coin types that sum to a."""
dp = [[0] * (amount + 1) for _ in range(len(coins) + 1)]
for i in range(len(coins) + 1):
dp[i][0] = 1
for i in range(1, len(coins) + 1):
for a in range(1, amount + 1):
dp[i][a] = dp[i - 1][a]
if a >= coins[i - 1]:
dp[i][a] += dp[i][a - coins[i - 1]]
return dp
def combinations_1d_descending(coins, amount):
"""Same as combinations_1d but the amount loop runs downward."""
ways = [1] + [0] * amount
for coin in coins:
for a in range(amount, coin - 1, -1):
ways[a] += ways[a - coin]
return ways[amount]
def one_coin_steps(coin, amount, ascending):
"""Print each update ways[a] += ways[a - coin] for one coin type, with the value read."""
ways = [1] + [0] * amount
order = range(coin, amount + 1) if ascending else range(amount, coin - 1, -1)
for a in order:
read = ways[a - coin]
ways[a] += read
print(" a=%d reads ways[%d]=%d -> ways=%s" % (a, a - coin, read, ways))
return ways
def list_combinations(coins, amount):
out = []
def build(i, remaining, chosen):
if remaining == 0:
out.append(tuple(chosen))
return
if i == len(coins):
return
k = 0
while k * coins[i] <= remaining:
build(i + 1, remaining - k * coins[i], chosen + [coins[i]] * k)
k += 1
build(0, amount, [])
return out
def list_sequences(coins, amount):
out = []
def build(remaining, chosen):
if remaining == 0:
out.append(tuple(chosen))
return
for c in coins:
if c <= remaining:
build(remaining - c, chosen + [c])
build(amount, [])
return out
coins, amount = [1, 2], 3
print("coins", coins, "amount", amount)
print("multisets :", list_combinations(coins, amount))
print("sequences :", list_sequences(coins, amount))
snap = []
print("combinations, coin loop outside -> count", combinations_1d(coins, amount, snap))
for coin, row in snap:
print(" after coin", coin, "row =", row)
snap = []
print("sequences, amount loop outside -> count", sequences_1d(coins, amount, snap))
for a, row in snap:
print(" after amount", a, "row[0..%d] =" % a, row)
# Relation to the 2D table
coins, amount = [1, 2, 3], 4
dp = combinations_2d(coins, amount)
snap = []
combinations_1d(coins, amount, snap)
print("coins", coins, "amount", amount)
for i, row in enumerate(dp):
print(" 2D row i=%d" % i, row)
print("each 1D snapshot equals the 2D row of the same coin:", all(snap[i - 1][1] == dp[i] for i in range(1, len(coins) + 1)))
print("multisets:", len(list_combinations(coins, amount)), " sequences:", len(list_sequences(coins, amount)))
print("combinations_1d:", combinations_1d(coins, amount), " sequences_1d:", sequences_1d(coins, amount))
print("amount loop reversed in the combinations code:", combinations_1d_descending(coins, amount),
"(each coin type used at most once)")
print("one coin (1), amount 3, loop upward: ways[a - coin] is already the NEW row")
one_coin_steps(1, 3, True)
print("one coin (1), amount 3, loop downward: ways[a - coin] is still the OLD row")
one_coin_steps(1, 3, False)
print("sequences for coins [1, 2, 3], amount 40:", sequences_1d([1, 2, 3], 40))
random.seed(8)
seen = set()
for _ in range(400):
cs = sorted(random.sample(range(1, 8), random.randint(1, 4)))
a = random.randint(0, 12)
assert combinations_1d(cs, a) == len(list_combinations(cs, a)) == combinations_2d(cs, a)[-1][a]
assert sequences_1d(cs, a) == len(list_sequences(cs, a))
seen.add((tuple(cs), a))
print("random cases checked:", len(seen))
Output:
coins [1, 2] amount 3
multisets : [(1, 2), (1, 1, 1)]
sequences : [(1, 1, 1), (1, 2), (2, 1)]
combinations, coin loop outside -> count 2
after coin 1 row = [1, 1, 1, 1]
after coin 2 row = [1, 1, 2, 2]
sequences, amount loop outside -> count 3
after amount 1 row[0..1] = [1, 1]
after amount 2 row[0..2] = [1, 1, 2]
after amount 3 row[0..3] = [1, 1, 2, 3]
coins [1, 2, 3] amount 4
2D row i=0 [1, 0, 0, 0, 0]
2D row i=1 [1, 1, 1, 1, 1]
2D row i=2 [1, 1, 2, 2, 3]
2D row i=3 [1, 1, 2, 3, 4]
each 1D snapshot equals the 2D row of the same coin: True
multisets: 4 sequences: 7
combinations_1d: 4 sequences_1d: 7
amount loop reversed in the combinations code: 1 (each coin type used at most once)
one coin (1), amount 3, loop upward: ways[a - coin] is already the NEW row
a=1 reads ways[0]=1 -> ways=[1, 1, 0, 0]
a=2 reads ways[1]=1 -> ways=[1, 1, 1, 0]
a=3 reads ways[2]=1 -> ways=[1, 1, 1, 1]
one coin (1), amount 3, loop downward: ways[a - coin] is still the OLD row
a=3 reads ways[2]=0 -> ways=[1, 0, 0, 0]
a=2 reads ways[1]=0 -> ways=[1, 0, 0, 0]
a=1 reads ways[0]=1 -> ways=[1, 1, 0, 0]
sequences for coins [1, 2, 3], amount 40: 23837527729
random cases checked: 315
Complexity
Both orders do (number of coin types) x (amount) constant-time updates, so O(c x A) time, and O(A) space for the list. The 2D combination table is O(c x A) space. The brute-force listings used for checking are exponential and are only for small inputs. Both loop orders agree with the explicit listings on every random case in the run.
Common mistakes
- Picking the wrong order for the question: "how many different coin sets" needs the coin loop outside, "how many different orderings" needs the amount loop outside.
- Running the amount loop downward in the combination code, which silently turns it into a count where each coin type is used at most once (the run prints 1 instead of 4).
Running the code
docker run --rm -v "$PWD":/w -w /w python:3.12 python loop_order.py
A row of houses holds nums[i] dollars each, and you cannot take from two adjacent houses. Return the maximum total you can take in O(n) time. Define the state, the transition and the base cases, and then reduce the space to O(1).
Sample Answer
The idea
At each house you either skip it or take it. If you take house i you cannot have taken house i-1, so the best you can add to it is the best total over houses before i-1. If you skip it, you keep the best total over houses before i. The better of the two is the best total so far, and it only ever depends on the previous two best totals. That is a dynamic programming (DP) solution: a problem solved by combining the answers to smaller versions of itself that overlap.
Numbering used throughout: the houses are nums[0], nums[1], and so on, counted from 0, so "house 2" is nums[2]. The table best is counted differently on purpose: best[i] covers the first i houses, so the last house it includes is house i-1, and that is why the transition below reads nums[i-1].
The five things to state
- What one cell means.
best[i]is the largest total you can take from the first i houses (houses 0 to i-1), with no two adjacent. - The transition.
best[i] = max(best[i-1], best[i-2] + nums[i-1]). The first term skips house i-1; the second takes it, which forces you to skip house i-2 and fall back tobest[i-2]. Every legal choice falls under exactly one of the two terms. - Base cases.
best[0] = 0(no houses) andbest[1] = max(0, nums[0]). Taking no house at all is a legal plan worth 0, so no answer is ever below 0. With non-negative values themax(0, ...)changes nothing; with a negative value it lets you skip the house. - Fill order. Ascending i, since each cell reads
best[i-1]andbest[i-2]. - Where the answer is.
best[n].
Brute force first
The recursion f(i) = max(f(i+1), nums[i] + f(i+2)) tries both choices at every house. Counting calls on [1] * n gives 25 calls for n = 5, 287 for n = 10, 35,421 for n = 20 and 392,835 for n = 25, growing by about a factor of 1.6 per house. Memoizing on i brings that to 2n + 1 calls (11, 21, 41, 51 in the table below), because there are only n + 1 distinct values of i.
The code
import itertools
import random
def rob_brute(nums):
"""Try every subset with no two adjacent houses."""
best = 0
for mask in range(1 << len(nums)):
if mask & (mask >> 1):
continue
best = max(best, sum(v for i, v in enumerate(nums) if mask >> i & 1))
return best
calls = 0
def rob_recursive(nums, i=0):
"""f(i) = best from houses i.. : skip house i, or take it and jump to i+2."""
global calls
calls += 1
if i >= len(nums):
return 0
return max(rob_recursive(nums, i + 1), nums[i] + rob_recursive(nums, i + 2))
def rob_memo(nums):
memo, count = {}, [0]
def f(i):
count[0] += 1
if i >= len(nums):
return 0
if i not in memo:
memo[i] = max(f(i + 1), nums[i] + f(i + 2))
return memo[i]
return f(0), count[0]
def rob_table(nums):
"""best[i] = most you can take from the first i houses."""
best = [0] * (len(nums) + 1)
if nums:
best[1] = max(0, nums[0])
for i in range(2, len(nums) + 1):
best[i] = max(best[i - 1], best[i - 2] + nums[i - 1])
return best
def rob(nums):
two_back, one_back = 0, 0 # best[i-2], best[i-1]
for value in nums:
two_back, one_back = one_back, max(one_back, two_back + value)
return one_back
def rob_wrong(nums):
two_back, one_back = 0, 0
for value in nums:
two_back = one_back # overwritten before it is used
one_back = max(one_back, two_back + value)
return one_back
nums = [2, 7, 9, 3, 1]
print("filled table:", rob_table(nums))
calls = 0
print("recursion:", rob_recursive(nums), "calls:", calls, "| memo:", rob_memo(nums))
print("O(1)-space:", rob(nums), "| wrong update order:", rob_wrong(nums))
for n in (5, 10, 20, 25):
calls = 0
rob_recursive([1] * n)
print(f"n={n:2d} recursion calls={calls:6d} memo calls={rob_memo([1] * n)[1]}")
print("empty:", rob([]), "one house:", rob([4]), "two houses:", rob([3, 8]), "all zeros:", rob([0, 0, 0]))
print("[4, 5, 4]:", rob([4, 5, 4]), "(taking the largest house alone gives 5)")
print("with a negative value:", rob([5, -2, 4]), "(taking is optional)")
print("\nsubsets of 3 houses as bitmasks (bit i is 1 when house i is taken):")
print("mask mask>>1 mask & (mask>>1) allowed")
for mask in range(8):
print(f"{mask:03b} {mask >> 1:03b} {mask & (mask >> 1):03b} {not mask & (mask >> 1)}")
random.seed(11)
for _ in range(400):
n = random.randint(0, 12)
nums = [random.randint(-5, 20) for _ in range(n)]
expected = rob_brute(nums)
assert rob(nums) == rob_table(nums)[n] == rob_memo(nums)[0] == rob_recursive(nums) == expected
print("400 random arrays (length 0..12, values -5..20) agree with subset enumeration")
Output:
filled table: [0, 2, 7, 11, 11, 12]
recursion: 12 calls: 25 | memo: (12, 11)
O(1)-space: 12 | wrong update order: 22
n= 5 recursion calls= 25 memo calls=11
n=10 recursion calls= 287 memo calls=21
n=20 recursion calls= 35421 memo calls=41
n=25 recursion calls=392835 memo calls=51
empty: 0 one house: 4 two houses: 8 all zeros: 0
[4, 5, 4]: 8 (taking the largest house alone gives 5)
with a negative value: 9 (taking is optional)
subsets of 3 houses as bitmasks (bit i is 1 when house i is taken):
mask mask>>1 mask & (mask>>1) allowed
000 000 000 True
001 000 000 True
010 001 000 True
011 001 001 False
100 010 000 True
101 010 000 True
110 011 010 False
111 011 011 False
400 random arrays (length 0..12, values -5..20) agree with subset enumeration
Reading the output
- The filled table
[0, 2, 7, 11, 11, 12]isbest[0]tobest[5]for[2, 7, 9, 3, 1]. The cellbest[3] = 11covers the first three houses (houses 0, 1 and 2). It came from taking house 2 (nums[2], value 9) plusbest[1] = 2, the best over house 0 alone;best[4] = 11is the skip branch because taking the 3 (house 3) would give onlybest[2]+ 3 = 7 + 3 = 10. - Constant space: each step reads only
best[i-1]andbest[i-2], sotwo_backandone_backreplace the list. The assignment must be simultaneous. The wrong version first setstwo_back = one_backand then computesmax(one_back, two_back + value), which isone_back + value, so it adds every house together and prints 22 instead of 12. - The empty array returns 0, one house returns its value, and two houses return the larger one. A negative value is simply never taken, because skipping is always allowed.
- The subset check in
rob_brutewrites each choice of houses as a bitmask, an integer whose bit i is 1 when house i is taken (bit 0 is the rightmost).mask >> i & 1shifts the mask right by i places and keeps the last bit, which reads bit i.mask >> 1slides every bit one place right, so bit i of the shifted copy equals bit i+1 of the original; ANDing the two withmask & (mask >> 1)is nonzero exactly when some bit i and bit i+1 are both 1, that is, two neighbouring houses are taken. The printed table lists all 8 masks for 3 houses:011,110and111are rejected and the other five are allowed. - The check compares the table, the memoized recursion, the plain recursion and the two-variable loop with a brute force over every subset that has no two adjacent houses, on 400 seeded arrays of length 0 to 12 with values from -5 to 20.
Complexity
| Version | States x work per state | Time | Space |
|---|---|---|---|
| Plain recursion | about 1.6^n calls x O(1) | exponential | O(n) call depth |
| Memoized | n + 1 states x O(1) | O(n) | O(n) |
| Table | n + 1 cells x O(1) | O(n) | O(n) |
| Two variables | n steps x O(1) | O(n) | O(1) |
Common mistakes
- Greedy fails: on
[4, 5, 4]taking the largest house gives 5, while houses 0 and 2 give 8, as the driver prints. Prove the transition rather than testing one example. - Using
best[i-1] + nums[i](forgetting the adjacency rule) orbest[i-3](assuming you must skip two houses). - Reading
nums[0]without checking for an empty array. - Overwriting the rolling variable before it is used, as shown above.
Running the code
python3.12 house_robber.py
Standard library only. Save the listing as house_robber.py and run the command above; it prints exactly the output shown.
Extend your edit-distance solution so that it also returns one sequence of edit operations that achieves the minimum, or shows the two strings aligned. How do you recover it, and what does that do to your space optimization?
Sample Answer
The idea
The table of distances already records which choice won in every cell, so the edits come from walking the table backwards. Start at the bottom-right cell. At each cell, find a neighbour that explains its value: the diagonal cell (a match for free, or a substitution for +1), the cell above (a deletion, +1) or the cell to the left (an insertion, +1). Step there, write down the column of the alignment (a column pairs one character of each string, or a character with a gap -), and repeat until you reach the top-left corner. Reading the columns from the corner gives the alignment, and every column that is not a match is one edit. A gap is a - standing where the other string has a character: a gap in the top row is an insertion, a gap in the bottom row is a deletion.
The five things to state
- What one cell means.
dp[i][j]is the fewest edits that turn the first i characters ofainto the first j characters ofb. - The transition.
dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + cost)wherecostis 0 for equal characters and 1 otherwise. - Base cases.
dp[i][0] = ianddp[0][j] = j. - Fill order. Row by row, left to right.
- Where the answer is. The distance is
dp[n][m]; the edits come from walking back from that cell todp[0][0], the reverse of the fill order.
Recovering the alignment
The move at cell (i, j) is valid when it reproduces the cell's value:
- diagonal when
dp[i][j] == dp[i-1][j-1] + cost: the pair(a[i-1], b[j-1])is a column (a match or a substitution); - up when
dp[i][j] == dp[i-1][j] + 1: deletea[i-1], so the column is(a[i-1], -); - left when
dp[i][j] == dp[i][j-1] + 1: insertb[j-1], so the column is(-, b[j-1]).
On the top row only left is possible and on the first column only up. The code walks back using the values alone, with no pointers stored, and the trace below it prints each cell, the valid moves at that cell and the one taken. For sunday to saturday the walk gives s--unday over saturday: two insertions (a, t) and one substitution (n becomes r), for a distance of 3. show prints the alignment with a middle row of marks: | under two equal characters (a match, free), * under two different characters (a substitution, one edit) and a blank wherever either row has a gap (an insertion or a deletion, one edit each). In the output below, s--unday over saturday has marks | |*|||: s and s match, the two gaps are blank, then u, n over u, r gives | and *, and d, a, y match. script_from_alignment turns the columns into positional edits on the original string, and apply_script applies them right to left so earlier positions are not shifted; the result is saturday.
When several answers tie
If more than one move is valid at a cell, each leads to a different but equally cheap alignment. For abc to acb there are three: one with two substitutions, and two with one deletion and one insertion. The walk's preference order picks one: diagonal first gives abc over acb, up first gives a-bc over acb-, left first gives abc- over a-cb. count_optimal counts them with a second table (ways[i][j] sums the ways of every valid predecessor) and the 300-pair check compares that count and the set of alignments against a brute-force enumeration. State the rule you used; unless the problem names one, any optimal alignment is a correct answer.
The code
import random
def edit_table(a, b):
"""dp[i][j] = fewest edits turning a[:i] into b[:j]."""
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(len(a) + 1):
dp[i][0] = i
for j in range(len(b) + 1):
dp[0][j] = j
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
cost = 0 if a[i - 1] == b[j - 1] else 1
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost)
return dp
def align(a, b, dp, order=("diag", "up", "left"), trace=None):
"""Walk back from the corner. At each cell take the first move in `order`
that reproduces the cell's value. Returns two equal-length strings, '-' = gap."""
i, j, top, bottom = len(a), len(b), [], []
while i > 0 or j > 0:
cost = 0 if i > 0 and j > 0 and a[i - 1] == b[j - 1] else 1
valid = []
if i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + cost:
valid.append("diag")
if i > 0 and dp[i][j] == dp[i - 1][j] + 1:
valid.append("up")
if j > 0 and dp[i][j] == dp[i][j - 1] + 1:
valid.append("left")
move = next(m for m in order if m in valid)
if trace is not None:
trace.append(f"({i},{j}) value {dp[i][j]}, valid {valid}, take {move}")
if move == "diag":
top.append(a[i - 1]); bottom.append(b[j - 1]); i -= 1; j -= 1
elif move == "up":
top.append(a[i - 1]); bottom.append("-"); i -= 1
else:
top.append("-"); bottom.append(b[j - 1]); j -= 1
return "".join(reversed(top)), "".join(reversed(bottom))
def show(top, bottom):
marks = "".join(" " if "-" in (x, y) else ("|" if x == y else "*")
for x, y in zip(top, bottom))
return f"{top}\n{marks}\n{bottom}"
def script_from_alignment(top, bottom):
"""Turn aligned rows into edits that use positions in the ORIGINAL first string."""
ops, pos = [], 0
for x, y in zip(top, bottom):
if x == "-":
ops.append(("insert", pos, y))
elif y == "-":
ops.append(("delete", pos, x)); pos += 1
else:
if x != y:
ops.append(("replace", pos, y))
pos += 1
return ops
def apply_script(a, ops):
s = list(a)
for kind, pos, ch in reversed(ops): # right to left keeps positions valid
if kind == "replace":
s[pos] = ch
elif kind == "delete":
del s[pos]
else:
s.insert(pos, ch)
return "".join(s)
def count_optimal(a, b, dp):
"""ways[i][j] = number of different optimal alignments of a[:i] and b[:j]."""
ways = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
ways[0][0] = 1
for i in range(len(a) + 1):
for j in range(len(b) + 1):
if i == j == 0:
continue
total = 0
if i > 0 and j > 0:
cost = 0 if a[i - 1] == b[j - 1] else 1
if dp[i][j] == dp[i - 1][j - 1] + cost:
total += ways[i - 1][j - 1]
if i > 0 and dp[i][j] == dp[i - 1][j] + 1:
total += ways[i - 1][j]
if j > 0 and dp[i][j] == dp[i][j - 1] + 1:
total += ways[i][j - 1]
ways[i][j] = total
return ways[-1][-1]
def all_optimal(a, b):
"""Reference: enumerate every alignment of minimum cost by plain recursion."""
best, found = [10 ** 9], set()
def go(i, j, top, bottom, cost):
if cost > best[0]:
return
if i == len(a) and j == len(b):
if cost < best[0]:
best[0] = cost
found.clear()
found.add((top, bottom))
return
if i < len(a) and j < len(b):
go(i + 1, j + 1, top + a[i], bottom + b[j], cost + (a[i] != b[j]))
if i < len(a):
go(i + 1, j, top + a[i], bottom + "-", cost + 1)
if j < len(b):
go(i, j + 1, top + "-", bottom + b[j], cost + 1)
go(0, 0, "", "", 0)
return best[0], found
cells = 0
def last_row(a, b):
"""Edit distances from a to every prefix of b, keeping one row at a time."""
global cells
prev = list(range(len(b) + 1))
for i in range(1, len(a) + 1):
cur = [i] + [0] * len(b)
for j in range(1, len(b) + 1):
cells += 1
cost = 0 if a[i - 1] == b[j - 1] else 1
cur[j] = min(prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + cost)
prev = cur
return prev
def hirschberg_align(a, b):
"""Optimal alignment using only rows of length len(b)+1 for the split search."""
if not a:
return "-" * len(b), b
if not b:
return a, "-" * len(a)
if len(a) == 1: # tiny table: 2 rows
return align(a, b, edit_table(a, b))
mid = len(a) // 2
front = last_row(a[:mid], b)
back = last_row(a[mid:][::-1], b[::-1])
k = min(range(len(b) + 1), key=lambda k: front[k] + back[len(b) - k])
t1, b1 = hirschberg_align(a[:mid], b[:k])
t2, b2 = hirschberg_align(a[mid:], b[k:])
return t1 + t2, b1 + b2
def cost_of(top, bottom):
return sum(x != y for x, y in zip(top, bottom))
a, b = "sunday", "saturday"
dp = edit_table(a, b)
print(" " + " ".join(["-"] + list(b)))
for i, row in enumerate(dp):
print(f"{'-' if i == 0 else a[i - 1]} " + " ".join(str(v) for v in row))
trace = []
top, bottom = align(a, b, dp, trace=trace)
print("\ndistance:", dp[-1][-1], "\nwalk back (diagonal preferred):")
print("\n".join(" " + line for line in trace))
print(show(top, bottom))
ops = script_from_alignment(top, bottom)
print("edits:", ops, "->", apply_script(a, ops))
print("\nsunday -> saturday has", count_optimal(a, b, dp), "optimal alignment")
x, y = "abc", "acb"
tie_dp = edit_table(x, y)
print(x, "->", y, "has", count_optimal(x, y, tie_dp), "optimal alignments, distance", tie_dp[-1][-1])
for order in [("diag", "up", "left"), ("up", "left", "diag"), ("left", "up", "diag")]:
print(f"order {order}:")
print(show(*align(x, y, tie_dp, order)))
print("all optimal alignments:", sorted(all_optimal(x, y)[1]))
mid = len(a) // 2
front = last_row(a[:mid], b)
back = last_row(a[mid:][::-1], b[::-1])
sums = [front[k] + back[len(b) - k] for k in range(len(b) + 1)]
print(f"\nsplit search: a[:{mid}] = {a[:mid]!r}, a[{mid}:] = {a[mid:]!r}")
print("front[k] (first half vs b[:k]): ", front)
print("back[m-k] (second half vs b[k:], k=0..m):", [back[len(b) - k] for k in range(len(b) + 1)])
print("sum per k: ", sums)
print("best k:", sums.index(min(sums)), "-> b splits into", repr(b[:sums.index(min(sums))]), "and", repr(b[sums.index(min(sums)):]))
ht, hb = hirschberg_align(a, b)
print("row-only alignment:", ht, "/", hb, "| cost", cost_of(ht, hb))
# Check against brute force on seeded random inputs.
rng = random.Random(21)
multi = 0
for _ in range(300):
x = "".join(rng.choice("abc") for _ in range(rng.randint(0, 5)))
y = "".join(rng.choice("abc") for _ in range(rng.randint(0, 5)))
table = edit_table(x, y)
best, found = all_optimal(x, y)
assert best == table[-1][-1] and count_optimal(x, y, table) == len(found)
multi += len(found) > 1
for order in [("diag", "up", "left"), ("left", "up", "diag"), ("up", "diag", "left")]:
t, bt = align(x, y, table, order)
assert (t, bt) in found
assert apply_script(x, script_from_alignment(t, bt)) == y
ht, hb = hirschberg_align(x, y)
assert cost_of(ht, hb) == best and ht.replace("-", "") == x and hb.replace("-", "") == y
print("\n300 random pairs: alignments, edit scripts and row-only alignments are optimal;",
"pairs with more than one optimal alignment:", multi)
# Work done by the row-only method on two random strings of length 300.
rng = random.Random(8)
s = "".join(rng.choice("ACGT") for _ in range(300))
t = "".join(rng.choice("ACGT") for _ in range(300))
cells = 0
ht, hb = hirschberg_align(s, t)
print("n*m =", len(s) * len(t), "| row-only cell updates =", cells,
"| cost matches table:", cost_of(ht, hb) == edit_table(s, t)[-1][-1])
Output
- s a t u r d a y
- 0 1 2 3 4 5 6 7 8
s 1 0 1 2 3 4 5 6 7
u 2 1 1 2 2 3 4 5 6
n 3 2 2 2 3 3 4 5 6
d 4 3 3 3 3 4 3 4 5
a 5 4 3 4 4 4 4 3 4
y 6 5 4 4 5 5 5 4 3
distance: 3
walk back (diagonal preferred):
(6,8) value 3, valid ['diag'], take diag
(5,7) value 3, valid ['diag'], take diag
(4,6) value 3, valid ['diag'], take diag
(3,5) value 3, valid ['diag'], take diag
(2,4) value 2, valid ['diag'], take diag
(1,3) value 2, valid ['left'], take left
(1,2) value 1, valid ['left'], take left
(1,1) value 0, valid ['diag'], take diag
s--unday
| |*|||
saturday
edits: [('insert', 1, 'a'), ('insert', 1, 't'), ('replace', 2, 'r')] -> saturday
sunday -> saturday has 1 optimal alignment
abc -> acb has 3 optimal alignments, distance 2
order ('diag', 'up', 'left'):
abc
|**
acb
order ('up', 'left', 'diag'):
a-bc
| |
acb-
order ('left', 'up', 'diag'):
abc-
| |
a-cb
all optimal alignments: [('a-bc', 'acb-'), ('abc', 'acb'), ('abc-', 'a-cb')]
split search: a[:3] = 'sun', a[3:] = 'day'
front[k] (first half vs b[:k]): [3, 2, 2, 2, 3, 3, 4, 5, 6]
back[m-k] (second half vs b[k:], k=0..m): [5, 4, 3, 2, 1, 0, 1, 2, 3]
sum per k: [8, 6, 5, 4, 4, 3, 5, 7, 9]
best k: 5 -> b splits into 'satur' and 'day'
row-only alignment: s--unday / saturday | cost 3
300 random pairs: alignments, edit scripts and row-only alignments are optimal; pairs with more than one optimal alignment: 138
n*m = 90000 | row-only cell updates = 179559 | cost matches table: True
What this does to the space optimization
Keeping only one or two rows throws away exactly the cells the walk back needs, so the plain rolling-row version can give you the distance but not the edits. There are three ways out:
- Keep the whole table. Time O(nm), space O(nm). For two strings of length 2000 that is about four million cells. Storing one small direction code per cell instead of the number is still O(nm) cells, only smaller ones.
- Divide and conquer (Hirschberg's method).
hirschberg_aligncomputes, with rolling rows only, the cost of aligning the first half ofawith every prefix ofb(front) and the cost of aligning the second half with every suffix (back, computed on the reversed strings). An optimal alignment crosses the middle ofaat some column k ofb, and the best k minimizesfront[k] + back[len(b) - k]. Recurse on the two halves. Time stays O(nm) but is about twice the plain table: on two random strings of length 300 it made 179,559 cell updates againstn*m= 90,000, because the first level costs about nm and the work halves at each level below it (1 + 1/2 + 1/4 + ...). The recursion is about log2(n) deep. The split search itself uses two rows of length m + 1 at a time, but this listing is not memory-tight: every call keeps its rows and its copied slices alive while it recurses, so in the worst case it holds up to about m cells for each of about log2(n) levels. The textbook form passes index ranges instead of slices and discards the rows before recursing, which needs only linear space.
A worked split on sunday to saturday (the split search lines in the output): the middle of a cuts it into sun and day. front[k] is the cost of turning sun into the first k characters of saturday, and the second row is the cost of turning day into the remaining characters from k on. Adding the two for every k gives [8, 6, 5, 4, 4, 3, 5, 7, 9], and the smallest sum, 3, is at k = 5. Reading it as a cell: at k = 5, sun against satur costs 3 (insert a and t, substitute n with r) and day against day costs 0, so 3 + 0 = 3, which equals the distance. So some optimal alignment pairs sun with satur and day with day, and each half is then solved on its own with the same method. Hirschberg's method is deeper material than most coding rounds ask for; a typical interview wants the full-table walk back and the observation that rolling rows lose the path.
3. Recompute only when needed. If you need edits for very few pairs, run the cheap length-only version for all of them and reconstruct for the pairs that matter.
Complexity
- Table and walk back: time O(nm) to fill, O(n + m) to walk (every step lowers i or j); space O(nm).
- Row-only alignment: time O(nm) (about 2nm updates); linear space in the textbook form, a little more in the listing for the reason given above.
Edge cases and common mistakes
- If
ais empty the alignment is all insertions, and ifbis empty it is all deletions; thewhile i > 0 or j > 0loop handles both with no special case, since only the left or only the up move is valid there. - Forgetting to reverse the collected columns, which prints the alignment backwards.
- Applying the edits left to right with original positions, which shifts every later position after an insert or delete. Apply right to left, or track an offset.
- Treating a substitution of equal characters as an edit: only columns where the two characters differ count.
- Assuming the alignment is unique when
count_optimalcan be greater than 1.
Running the code
Save the listing as edit_alignment.py and run python edit_alignment.py (Python 3.12, standard library only).
Design an algorithm that computes a minimal list of edits (insert, delete, replace) turning one ordered JSON document into another, as a diff tool would. State your assumptions about child ordering, and analyze the time and space cost.
Sample Answer
The idea
Edit distance on strings is the fewest single-character edits (delete a character, insert one, or replace one) that turn one string into another: "cat" to "cut" is one replace (a to u), so the distance is 1. It aligns two sequences with those three moves. A JSON document is a tree, so the same idea works one level at a time: the children of an array are the "characters", and the cost of substituting one child for another is itself the edit distance between those two subtrees. Recursion supplies that cost; a table aligns the children at each level.
Assumptions (stated up front)
- Arrays are ordered sequences. Children are aligned by position with the edit-distance table.
- Object members are matched by key, and key order is ignored. A key in both documents is compared recursively; a key only in the old document is deleted; a key only in the new one is inserted. If key order must be preserved, treat the object as a sequence of (key, value) pairs and run the array alignment on it.
- Nodes keep their parent. A subtree that moved to a different parent appears as a delete plus an insert. General ordered tree edit distance lets nodes match across parents, but it is a heavier algorithm; the top-down version here is what common JSON diff tools need and is far simpler.
- Costs count nodes. A node is every scalar, array or object (an array of two numbers has 3 nodes). Replacing one scalar costs 1. Inserting or deleting a subtree costs its node count. If two nodes are different kinds (array against object, container against scalar) the whole subtree is deleted and the other inserted, costing both node counts. A scalar and a different-typed scalar count as different (
1andtrueare different JSON values).
State, recurrence, base cases, fill order
For two arrays a (p children) and b (q children):
- State:
(i, j), the firstichildren ofaand the firstjofb. - What one cell means:
D[i][j]is the minimal cost of turninga[:i]intob[:j]. - Recurrence:
D[i][j] = min( D[i-1][j] + size(a[i-1]), D[i][j-1] + size(b[j-1]), D[i-1][j-1] + diff(a[i-1], b[j-1]) ): delete childi, insert childj, or align them and pay the cost of editing one into the other. - Base cases:
D[i][0]is the total size of the first i children ofa(delete them all);D[0][j]is the total size of the first j children ofb. - Fill order:
iascending, thenjascending. Each cell reads three cells already filled. - Answer:
D[p][q], then walk back from(p, q)to read off the edits. Walking from the end produces edits at higher array positions first, so when the script is applied in order every index is still valid.
Brute force
The same recurrence as plain recursion on (i, j) has no table. The program counts its calls on arrays of k scalars (root call included): 1 for k = 0, 4 for k = 1, 19 for k = 2, 94 for k = 3, 13,483 for k = 6 and 398,593 for k = 8, against a table of 1, 4, 9, 16, 49 and 81 cells. The exponential blow-up comes from reaching the same (i, j) along many paths.
Code
diff(a, b) returns a pair (cost, build). The cost is computed first, bottom-up, for every pair of subtrees. build is a closure (a function that remembers the tables of its call) that is run only afterwards: it replays the walk back through those tables and appends the edits to a list. This keeps the cost computation and the edit-list construction separate, so each table is filled once and the edit list is read off without recomputing anything.
import copy
import json
import random
stats = {"pair_calls": 0, "cells": 0}
def kind(x):
return "obj" if isinstance(x, dict) else "arr" if isinstance(x, list) else "leaf"
size_cache = {}
def size(x):
"""Number of nodes: every scalar, array and object counts 1, plus everything inside. Cached per container."""
if not isinstance(x, (dict, list)):
return 1
key = id(x)
if key not in size_cache:
children = x.values() if isinstance(x, dict) else x
size_cache[key] = 1 + sum(size(v) for v in children)
return size_cache[key]
def same_leaf(a, b):
return type(a) is type(b) and a == b # 1 and True are different JSON values
def diff(a, b, table_sink=None):
"""Returns (cost, build). build(path, out) appends the edits for this pair to out.
Costs count nodes: replace one scalar = 1, insert or delete a subtree = its node count."""
stats["pair_calls"] += 1
ka, kb = kind(a), kind(b)
if ka == "leaf" and kb == "leaf":
if same_leaf(a, b):
return 0, lambda path, out: None
return 1, lambda path, out: out.append(("replace", path, b))
if ka != kb:
cost = size(a) + size(b)
def swap(path, out):
if not path:
out.append(("replace", path, b))
else:
out.append(("delete", path))
out.append(("insert", path, b))
return cost, swap
if ka == "obj":
cost = 0
parts = []
for key in sorted(set(a) | set(b)):
if key in a and key in b:
c, bld = diff(a[key], b[key])
cost += c
parts.append((key, bld, None))
elif key in a:
cost += size(a[key])
parts.append((key, None, "delete"))
else:
cost += size(b[key])
parts.append((key, None, "insert"))
def build_obj(path, out):
for key, bld, op in parts:
if bld:
bld(path + [key], out)
elif op == "delete":
out.append(("delete", path + [key]))
else:
out.append(("insert", path + [key], b[key]))
return cost, build_obj
# two arrays: D[i][j] = cheapest edits turning a[:i] into b[:j]
p, q = len(a), len(b)
D = [[0] * (q + 1) for _ in range(p + 1)]
stats["cells"] += (p + 1) * (q + 1)
for i in range(1, p + 1):
D[i][0] = D[i - 1][0] + size(a[i - 1])
for j in range(1, q + 1):
D[0][j] = D[0][j - 1] + size(b[j - 1])
pair = [[None] * (q + 1) for _ in range(p + 1)]
for i in range(1, p + 1):
for j in range(1, q + 1):
pair[i][j] = diff(a[i - 1], b[j - 1])
D[i][j] = min(D[i - 1][j] + size(a[i - 1]),
D[i][j - 1] + size(b[j - 1]),
D[i - 1][j - 1] + pair[i][j][0])
if table_sink is not None:
table_sink.extend(D)
def build_arr(path, out):
i, j = p, q
while i > 0 or j > 0: # walk back from the end so earlier indexes stay valid
if i > 0 and j > 0 and D[i][j] == D[i - 1][j - 1] + pair[i][j][0]:
pair[i][j][1](path + [i - 1], out)
i, j = i - 1, j - 1
elif i > 0 and D[i][j] == D[i - 1][j] + size(a[i - 1]):
out.append(("delete", path + [i - 1]))
i -= 1
else:
out.append(("insert", path + [i], b[j - 1]))
j -= 1
return D[p][q], build_arr
def edit_script(a, b, table_sink=None):
size_cache.clear()
cost, build = diff(a, b, table_sink)
out = []
build([], out)
return cost, out
def apply_script(doc, script):
doc = copy.deepcopy(doc)
for op in script:
kindname, path = op[0], op[1]
if not path:
doc = copy.deepcopy(op[2])
continue
parent = doc
for step in path[:-1]:
parent = parent[step]
last = path[-1]
if kindname == "replace":
parent[last] = copy.deepcopy(op[2])
elif kindname == "delete":
del parent[last]
elif isinstance(parent, list):
parent.insert(last, copy.deepcopy(op[2]))
else:
parent[last] = copy.deepcopy(op[2])
return doc
def naive_cost_calls(a, b):
"""Reference: the same model by plain recursion, no table. Returns (cost, number of prefix-pair calls)."""
size_cache.clear()
calls = 0
def dist(x, y):
nonlocal calls
kx, ky = kind(x), kind(y)
if kx == "leaf" and ky == "leaf":
return 0 if same_leaf(x, y) else 1
if kx != ky:
return size(x) + size(y)
if kx == "obj":
total = 0
for key in set(x) | set(y):
total += dist(x[key], y[key]) if key in x and key in y else size(x.get(key, y.get(key)))
return total
def seq(i, j):
nonlocal calls
calls += 1
if i == 0:
return sum(size(v) for v in y[:j])
if j == 0:
return sum(size(v) for v in x[:i])
return min(seq(i - 1, j) + size(x[i - 1]), seq(i, j - 1) + size(y[j - 1]),
seq(i - 1, j - 1) + dist(x[i - 1], y[j - 1]))
return seq(len(x), len(y))
return dist(a, b), calls
def levenshtein(s, t):
"""Independent textbook edit distance on flat lists, for comparison."""
prev = list(range(len(t) + 1))
for i, x in enumerate(s, 1):
cur = [i]
for j, y in enumerate(t, 1):
cur.append(min(prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + (0 if x == y else 1)))
prev = cur
return prev[-1]
# 1. Worked example: two small configs
old = {"name": "api", "ports": [80, 443, 8080], "tls": {"min": "1.2"}, "debug": True}
new = {"name": "api", "ports": [80, 8443, 8080, 9090], "tls": {"min": "1.3"}, "owner": "ops"}
cost, script = edit_script(old, new)
print("cost (nodes edited):", cost)
for op in script:
print(" ", op)
print("patched document equals target:", apply_script(old, script) == new, "| script entries:", len(script))
# 2. Filled table for a small array pair
sink = []
c, ops = edit_script([1, 2, 3], [1, 3, 4], sink)
print("array [1,2,3] -> [1,3,4], table rows i=0..3, columns j=0..3:")
for row in sink:
print(" ", row)
print("edits the walk back from the bottom-right cell makes:", ops)
# cell D[2][2] (turn [1,2] into [1,3]) from its three neighbours
D = sink
print("D[2][2] = min(delete:", D[1][2], "+ 1, insert:", D[2][1], "+ 1, align 2 with 3:", D[1][1], "+ 1) =",
min(D[1][2] + 1, D[2][1] + 1, D[1][1] + 1))
print("cat -> cut on plain strings:", levenshtein("cat", "cut"))
# 3. Counted work: naive recursion vs table on flat arrays of k scalars
print("k naive recursive calls table cells equals textbook edit distance")
for k in (0, 1, 2, 3, 6, 8):
a = list(range(k))
b = list(range(100, 100 + k))
stats["cells"] = 0
cost, _ = edit_script(a, b)
nc, calls = naive_cost_calls(a, b)
assert cost == nc == levenshtein(a, b) == k
print(f"{k:<2} {calls:<22} {stats['cells']:<12} yes")
# 4. Pair-comparison bound: at most size(a) * size(b) pair calls
for a, b in (([], []), (1, 2), ([1], [2]), ([[1, 2], {"k": 3}], [[2], {"k": 4, "z": 5}])):
stats["pair_calls"] = 0
size_cache.clear()
diff(a, b)
print(f"sizes {size(a)} x {size(b)} = {size(a) * size(b)} | pair comparisons made: {stats['pair_calls']}")
assert stats["pair_calls"] <= size(a) * size(b)
# 5. Edge cases that are run
print("equal documents:", edit_script({"a": [1, 2]}, {"a": [1, 2]}))
print("1 vs true are different JSON values:", edit_script(1, True))
print("empty array to [1,2]:", edit_script([], [1, 2]))
print("object value changes kind:", edit_script({"a": [1, 2]}, {"a": 7}))
print("root changes kind:", edit_script([1, 2], {"x": 1}))
# 6. Nesting depth: each level of the document costs a few Python frames
def nested(depth):
doc = 0
for _ in range(depth):
doc = [doc]
return doc
for depth in (100, 2000):
try:
print("depth", depth, "-> cost", edit_script(nested(depth), nested(depth - 1))[0])
except RecursionError:
print("depth", depth, "-> RecursionError at the default recursion limit of", __import__("sys").getrecursionlimit())
# 7. Random check
rng = random.Random(86)
def random_doc(depth):
r = rng.random()
if depth == 0 or r < 0.35:
return rng.choice([0, 1, 2, "x", "y", None, True, False])
if r < 0.7:
return [random_doc(depth - 1) for _ in range(rng.randint(0, 3))]
return {k: random_doc(depth - 1) for k in rng.sample("abc", rng.randint(0, 3))}
checked = 0
distinct = set()
nonzero = 0
for _ in range(500):
a, b = random_doc(3), random_doc(3)
distinct.add(json.dumps([a, b], sort_keys=True))
cost, script = edit_script(a, b)
assert apply_script(a, script) == b and json.dumps(apply_script(a, script), sort_keys=True) == json.dumps(b, sort_keys=True), (a, b, script)
assert cost == naive_cost_calls(a, b)[0] == edit_script(b, a)[0], (a, b)
assert edit_script(a, a)[0] == 0
nonzero += cost > 0
checked += 1
print("random document pairs checked:", checked, "| distinct pairs:", len(distinct), "| with at least one edit:", nonzero)
flat = 0
for _ in range(300):
a = [rng.randint(0, 3) for _ in range(rng.randint(0, 7))]
b = [rng.randint(0, 3) for _ in range(rng.randint(0, 7))]
assert edit_script(a, b)[0] == levenshtein(a, b)
flat += 1
print("flat integer arrays vs textbook edit distance:", flat)
# 8. Two of the named mistakes
old_list, new_list = [0, 1, 2], [2]
cost, script = edit_script(old_list, new_list)
print("[0, 1, 2] -> [2]: script", script, "| applied in order:", apply_script(old_list, script),
"| same edits listed lowest index first:", apply_script(old_list, script[::-1]))
by_key = {"a": 1, "b": 2}
reordered = {"b": 2, "a": 1}
by_position = sum(edit_script(x, y)[0] for x, y in zip(by_key.values(), reordered.values()))
print("same members, key order changed: matched by key cost", edit_script(by_key, reordered)[0],
"| matched by position cost", by_position)
Output:
cost (nodes edited): 5
('delete', ['debug'])
('insert', ['owner'], 'ops')
('insert', ['ports', 3], 9090)
('replace', ['ports', 1], 8443)
('replace', ['tls', 'min'], '1.3')
patched document equals target: True | script entries: 5
array [1,2,3] -> [1,3,4], table rows i=0..3, columns j=0..3:
[0, 1, 2, 3]
[1, 0, 1, 2]
[2, 1, 1, 2]
[3, 2, 1, 2]
edits the walk back from the bottom-right cell makes: [('replace', [2], 4), ('replace', [1], 3)]
D[2][2] = min(delete: 1 + 1, insert: 1 + 1, align 2 with 3: 0 + 1) = 1
cat -> cut on plain strings: 1
k naive recursive calls table cells equals textbook edit distance
0 1 1 yes
1 4 4 yes
2 19 9 yes
3 94 16 yes
6 13483 49 yes
8 398593 81 yes
sizes 1 x 1 = 1 | pair comparisons made: 1
sizes 1 x 1 = 1 | pair comparisons made: 1
sizes 2 x 2 = 4 | pair comparisons made: 2
sizes 6 x 6 = 36 | pair comparisons made: 8
equal documents: (0, [])
1 vs true are different JSON values: (1, [('replace', [], True)])
empty array to [1,2]: (2, [('insert', [0], 2), ('insert', [0], 1)])
object value changes kind: (4, [('delete', ['a']), ('insert', ['a'], 7)])
root changes kind: (5, [('replace', [], {'x': 1})])
depth 100 -> cost 3
depth 2000 -> RecursionError at the default recursion limit of 1000
random document pairs checked: 500 | distinct pairs: 438 | with at least one edit: 487
flat integer arrays vs textbook edit distance: 300
[0, 1, 2] -> [2]: script [('delete', [1]), ('delete', [0])] | applied in order: [2] | same edits listed lowest index first: [1]
same members, key order changed: matched by key cost 0 | matched by position cost 2
Reading the run
- Worked diff: the script for the config example costs 5 node edits: delete
debug, insertowner, insert 9090 atports[3], replaceports[1](443 with 8443) and replacetls.min. Applying the script to the old document gives exactly the new one. - Filled table: for
[1,2,3]against[1,3,4]the bottom-right cell is 2. Rows are the prefixes[],[1],[1,2],[1,2,3]of the old array and columns the prefixes[],[1],[1,3],[1,3,4]of the new one. One cell worked:D[2][2]turns[1,2]into[1,3]; deleting the 2 costsD[1][2] + 1 = 2, inserting a 3 costsD[2][1] + 1 = 2, and aligning the 2 with the 3 costsD[1][1] + 1 = 1, so the cell is 1 (the printed line shows the three candidates). The walk back starts at the bottom-right cellD[3][3] = 2: aligning 3 with 4 givesD[2][2] + 1 = 2, which matches, so the walk replaces the 3 with 4 and moves toD[2][2] = 1; aligning 2 with 3 givesD[1][1] + 1 = 1, so it replaces the 2 with 3 and moves toD[1][1] = 0, where the 1 matches the 1 for free. The edits the code makes are therefore "replace the 3 with 4" and "replace the 2 with 3" (printed above, last one in the old array first). Another route also costs 2: delete the 2 and insert 4 at the end, with the 1 and the 3 matched for free. The code reports the first route because it tests the align move before delete and insert. - Edge cases: equal documents cost 0 with an empty script;
1againsttrueis a replace costing 1; the empty array to[1,2]is two inserts, and the second insert is at index 0 because the script walks from the end; a changed kind inside an object is a delete plus an insert (cost 4 for a 3-node array becoming a number); a changed kind at the root is a single replace costing both sizes (5). - Random check: 500 seeded random document pairs (438 distinct, 487 with at least one edit; scalars, empty arrays and objects,
null, booleans, depth up to 3) satisfy: the patched document equals the target, the cost equals the plain recursion,diff(a, b)equalsdiff(b, a), and a document against itself costs 0. On 300 flat integer arrays (lengths 0 to 7) the cost equals a separately written textbook edit distance. - Pair comparisons are bounded by the product of sizes: the run made 1 comparison where at most 1 is allowed (two empty arrays, and again two scalars), 2 where at most 4 (
[1]and[2]), and 8 where at most 36 (the largest example). Each pair of nodes is compared at most once because a node has one parent: the pair (x, y) is only requested from the table cell for the parent of x and the parent of y, and each cell is filled once. - Depth: a document nested 100 levels works, and 2000 levels raises
RecursionErrorat Python's default limit of 1000 frames, because each level uses recursion. Deep documents need an explicit stack or a raised limit.
Complexity
With n1 and n2 the node counts of the two documents:
- Time: O(n1 * n2). Each pair of nodes is compared at most once (counted above), and each array pair fills p * q cells where each cell is one such pair. Sizes are computed once per container. Sorting the keys of objects adds a logarithmic factor on top.
- Space: O(n1 * n2) in this code, because the tables are kept so the edit script can be rebuilt. A version that only needs the cost can drop each table after use. Recursion depth equals the nesting depth of the documents.
Common mistakes
- Comparing with Python
==and treating1andTrueas equal, which hides a real change (the run shows it). - Emitting array edits from the front of the array. Every insert or delete shifts the indexes of the later edits: for
[0, 1, 2]to[2]the script is delete index 1, then delete index 0, which gives[2]; the same two edits listed lowest index first give[1](the last block of the run). - Matching object members by position when order is not meaningful: with the same two members in a different key order the cost is 0 matched by key and 2 matched by position (the last block of the run).
- Promising "minimal" without naming the model. Minimal here means minimal under the assumptions above (no moves across parents).
Running the code
Save the code as json_diff_dp.py
python3 json_diff_dp.py
Python 3.12, standard library only.
You must split an integer budget of B units among M services; spending x units on service i reduces expected loss by a known table f_i(x). Choose the split that minimizes total loss. Formulate the DP, give its complexity, and explain how you recover the allocation.
Sample Answer
The idea
Spending x units on service i removes f_i(x) of expected loss, and each service's table is given as a list of numbers, not a formula. Minimising the total loss is the same as maximising the total reduction, because the loss with nothing spent is fixed: total loss = sum of the starting losses minus the sum of the reductions. Decide the services one at a time. After deciding the first i services, the only thing that matters about the past is how many units have been spent, not how they were spread. That single number makes the problem a DP (dynamic programming: solve small cases once and build the big one from them) over (services handled, units used).
The five things to state
- State.
(i, b): the first i services are decided and exactly b units have been spent on them. - What one cell means.
best[i][b]is the largest total reduction obtainable from services 1..i using exactly b units. - Recurrence.
best[i][b] = max over x from 0 to b of best[i-1][b-x] + f_i(x): the last service gets x units and the earlier ones get the remaining b - x. - Base cases.
best[0][0] = 0(no services, nothing spent) andbest[0][b] = minus infinityfor b > 0 (you cannot spend units on no service). - Fill order. i from 1 to M, and for each i, b from 0 to B in any order because row i reads only row i - 1. The answer is
sum(base losses) - best[M][B].
Recovering the allocation
A table of values alone does not say which x was chosen. Store the winning x in a second table, pick[i][b]. To recover the split, start at (M, B): the last service gets pick[M][B], then move to (M-1, B - pick[M][B]), and repeat down to service 1. The code does exactly this walk and the units it returns add up to B on every random test.
Why not just give units greedily?
The tempting shortcut is to hand out one unit at a time to the service whose next unit helps most. That is guaranteed to give the best split when each table has diminishing returns (each extra unit helps no more than the previous one); without that, it can win on some inputs and lose on others. The tables here are arbitrary (a service may gain little from the first units and a lot from the third), and the last lines of the output show a pair of tables where the greedy split loses to the DP.
The code
import random
from itertools import product
from math import comb
def allocate(base_loss, reduction, budget, show=False):
"""reduction[i][x] = loss removed by giving x units to service i (x = 0..budget).
best[i][b] = most loss removed using services 0..i-1 and EXACTLY b units.
Returns (minimum total loss, units per service, inner steps) or None if impossible."""
m = len(base_loss)
if m == 0:
return (0, [], 0) if budget == 0 else None
NEG = float("-inf")
best = [[NEG] * (budget + 1) for _ in range(m + 1)]
pick = [[0] * (budget + 1) for _ in range(m + 1)]
best[0][0] = 0 # no services, no units spent
steps = 0
for i in range(1, m + 1):
for b in range(budget + 1):
for x in range(b + 1): # x units go to service i - 1
steps += 1
if best[i - 1][b - x] == NEG:
continue
value = best[i - 1][b - x] + reduction[i - 1][x]
if value > best[i][b]:
best[i][b], pick[i][b] = value, x
if show:
for i in range(m + 1):
print(f"best[{i}] =", best[i])
for i in range(1, m + 1):
print(f"pick[{i}] =", pick[i])
units, b = [0] * m, budget
for i in range(m, 0, -1): # walk back through the stored choices
units[i - 1] = pick[i][b]
b -= pick[i][b]
return sum(base_loss) - best[m][budget], units, steps
def brute_force(base_loss, reduction, budget):
m = len(base_loss)
if m == 0:
return 0 if budget == 0 else None
top = None
for split in product(range(budget + 1), repeat=m):
if sum(split) == budget:
gain = sum(reduction[i][x] for i, x in enumerate(split))
top = gain if top is None else max(top, gain)
return sum(base_loss) - top
def greedy(base_loss, reduction, budget):
units = [0] * len(base_loss)
for _ in range(budget):
i = max(range(len(units)), key=lambda k: reduction[k][units[k] + 1] - reduction[k][units[k]])
units[i] += 1
return sum(base_loss) - sum(reduction[i][x] for i, x in enumerate(units)), units
base = [10, 8, 12]
red = [[0, 4, 7, 9, 10, 10],
[0, 1, 2, 6, 7, 8],
[0, 3, 5, 6, 6, 6]]
print("budget 5, base losses", base)
loss, units, steps = allocate(base, red, 5, show=True)
print("minimum total loss:", loss, "| units per service:", units, "| inner steps:", steps)
print("formula M*(B+1)*(B+2)/2 =", 3 * 6 * 7 // 2)
print("M B inner steps all splits C(B+M-1, M-1)")
for m, b in ((1, 5), (2, 5), (3, 5), (10, 20)):
print(f"{m:2d} {b:4d} {m * (b + 1) * (b + 2) // 2:12d} {comb(b + m - 1, m - 1):d}")
print("M=50, B=1000: inner steps", 50 * 1001 * 1002 // 2, "| number of splits has", len(str(comb(1049, 49))), "digits")
random.seed(62)
for _ in range(300):
m, b = random.randint(0, 4), random.randint(0, 6)
bl = [random.randint(5, 20) for _ in range(m)]
rd = [[0] + [random.randint(-2, 9) for _ in range(b)] for _ in range(m)]
got = allocate(bl, rd, b)
expected = brute_force(bl, rd, b)
assert (got[0] if got else None) == expected, (bl, rd, b)
if got and m:
assert sum(got[1]) == b
assert sum(bl) - sum(rd[i][x] for i, x in enumerate(got[1])) == got[0]
print("300 seeded cases (0..4 services, budget 0..6, losses that can also rise): DP equals brute force and the units add up to B")
random.seed(7)
while True:
bl = [10, 10]
rd = [[0] + sorted(random.sample(range(1, 12), 4)) for _ in range(2)]
g = greedy(bl, rd, 4)
d = allocate(bl, rd, 4)
if g[0] > d[0]:
break
print("tables", rd, "budget 4: greedy loss", g[0], "with", g[1], "| DP loss", d[0], "with", d[1])
Output:
budget 5, base losses [10, 8, 12]
best[0] = [0, -inf, -inf, -inf, -inf, -inf]
best[1] = [0, 4, 7, 9, 10, 10]
best[2] = [0, 4, 7, 9, 10, 13]
best[3] = [0, 4, 7, 10, 12, 14]
pick[1] = [0, 1, 2, 3, 4, 5]
pick[2] = [0, 0, 0, 0, 0, 3]
pick[3] = [0, 0, 0, 1, 1, 2]
minimum total loss: 16 | units per service: [3, 0, 2] | inner steps: 63
formula M*(B+1)*(B+2)/2 = 63
M B inner steps all splits C(B+M-1, M-1)
1 5 21 1
2 5 42 6
3 5 63 21
10 20 2310 10015005
M=50, B=1000: inner steps 25075050 | number of splits has 85 digits
300 seeded cases (0..4 services, budget 0..6, losses that can also rise): DP equals brute force and the units add up to B
tables [[0, 2, 4, 6, 10], [0, 1, 2, 9, 11]] budget 4: greedy loss 10 with [4, 0] | DP loss 9 with [1, 3]
Reading the output
- The worked example has three services, base losses 10, 8, 12 (sum 30) and budget 5.
best[1]is just the first service's table.best[2][5] = 13comes frompick[2][5] = 3: three units to service 2 (reduction 6) and the other two to service 1 (reduction 7).best[3][5] = 14withpick[3][5] = 2, so service 3 gets 2 units (reduction 5), and the remaining 3 units go to the first two services. - Walking back: service 3 gets 2 units, then
pick[2][3] = 0, then service 1 getspick[1][3] = 3. The split is[3, 0, 2], with reductions 9 + 0 + 5 = 14 and a minimum total loss of 30 - 14 = 16. - The code counts the inner steps: 63 for M = 3 and B = 5, equal to
M * (B+1) * (B+2) / 2. The other rows of the second table use that formula (it matches the counted value at M = 3, B = 5), and are put next to the number of possible splits,C(B+M-1, M-1), which is 21 for M = 3, B = 5 and has 85 digits for M = 50, B = 1000. - The random test compares the DP with a brute force over every split on 300 seeded cases with 0 to 4 services and budgets from 0 to 6, including budget 0, the empty service list and tables where extra units make the loss go up. M = 0 with a positive budget is reported as impossible. Every case also checks that the returned units sum to B and reproduce the reported loss.
- On the final tables, greedy returns loss 10 with all 4 units on one service, while the DP finds 9 with a 1/3 split.
Complexity
- Time. There are M * (B + 1) states, and each takes the maximum over up to B + 1 choices of x, so the inner step runs
M * (B+1) * (B+2) / 2times: O(M * B^2). For M = 50 and B = 1000 that is 25,075,050 steps (printed), fine in a compiled language and slow-ish in plain Python. - Space.
bestandpickeach have (M + 1)(B + 1) cells, O(M * B). If you only need the minimum loss and not the split, keep two rows ofbest, O(B). - At M = 1 the loop is still correct: one service gets all B units, and the step count is
(B+1)(B+2)/2.
Edge cases and common mistakes
- Budget 0: the only split is all zeros and the answer is the sum of base losses.
- This code spends exactly B units, as the question's 'split' says. To allow leftover units, take the best of
best[M][b]over all b. - Reading the answer from the wrong row: it is
best[M][B], not the maximum over rows.
Running the code
python3.12 budget_split.py
Standard library only. Save the listing as budget_split.py and run the command above; it prints exactly the output shown.
Unlock Full Question Bank
Get access to all Dynamic Programming interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.