Question 1

Climbing Stairs with 1 or 2 steps, n up to 45. Which runs in O(n) time and O(1) space?

Accepted Answer

Two rolling variables a, b = b, a + b Each state needs only the previous two. Plain recursion is O(2^n). Memoization is O(n) time but O(n) space. A dp array is also O(n) space.

Question 2

House Robber (max total from houses in a row, never two adjacent houses) recurrence for dp[i], the best up to house i?

Accepted Answer

dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) Either skip house i or take it with the best up to i - 2. Always taking i forces a choice. max(dp[i - 1], nums[i]) forgets the sum. Alternating fails on [2, 1, 1, 2] where the best is 4 from houses 0 and 3.

Question 3

Coin Change: coins = [1, 3, 4], amount = 6, fewest coins. What does largest coin first greedy return, and what is optimal?

Accepted Answer

Greedy 3 coins (4, 1, 1), optimal 2 (3, 3) Greedy takes 4 then two 1s. DP finds 3 + 3. Greedy is only optimal for canonical coin systems. It does find an answer because 1 exists.

Question 4

Coin Change II counts combinations. Which loop order counts each combination once?dp = [1] + [0] * amount
# loops here
 dp[a] += dp[a - c]

Accepted Answer

for c in coins: for a in range(c, amount + 1) Coins outer means each combination is built in coin order, so it is counted once. Amount outer counts ordered sequences (permutations), which is Combination Sum IV. Iterating amounts downward is 0/1 knapsack, so each coin is used at most once. The orders differ: for amount 3 with coins 1 and 2 they give 2 and 3.

Question 5

0/1 knapsack with a 1D dp over capacity. Why iterate capacity from high to low?

Accepted Answer

So dp[w - weight] still holds the value without the current item, preventing reuse Going downward reads states from the previous item row. Going upward lets an item be added multiple times, which is unbounded knapsack. Cache locality is not the reason. Overflow is unrelated. It matters for correctness.

Question 6

Longest Increasing Subsequence in O(n log n) with a tails array. For each x, what happens?

Accepted Answer

Replace tails[bisect_left(tails, x)] with x, or append if at the end bisect_left keeps strict increase: an equal value replaces rather than extends. bisect_right counts non decreasing sequences. Ignoring smaller x loses better tails. Inserting grows the array beyond the LIS length.

Question 7

Edit Distance dp[i][j] for word1[:i] and word2[:j]. When word1[i - 1] != word2[j - 1], what is dp[i][j]?

Accepted Answer

1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) Delete, insert and replace each cost 1. Only replace ignores insert and delete. Adding 2 models delete plus insert in place of replace, the LCS style distance. max is wrong for a minimum.

Question 8

Word Break (can s be split into dictionary words) with memo on start index, string length n, dictionary of words up to length L stored in a set. For each start you try every end up to n and slice. What is the time?

Accepted Answer

O(n^3): n states, n ends, O(n) slice and hash Memoization caps states at n, but each tries up to n ends and slicing plus hashing costs O(n), giving O(n^3), or O(n^2 L) if ends are capped at L. O(n) counts states only. O(n^2) forgets the slice cost. O(2^n) is without memoization.

Question 9

Longest Common Subsequence of lengths m and n. Minimum space while still returning the length?

Accepted Answer

O(min(m, n)) with two rolling rows Each row depends only on the previous row, so keep two rows of the shorter length. O(m n) is the full table, needed only to reconstruct the sequence directly. O(1) cannot hold the dependencies. O(m + n) is more than needed.

Question 10

Unique Paths II counts right and down paths from top left to bottom right on a grid with obstacles. In the first row, what is dp[0][j] after an obstacle at (0, 2)?

Accepted Answer

0 for every j >= 2 A path along the first row cannot pass the obstacle, so everything to its right is 0. Initializing the whole row to 1 is the classic bug. Only zeroing j = 2 still lets j = 3 inherit 1. The first row is filled as a base case.

Question 11

Partition Equal Subset Sum (can nums split into two subsets with equal sums), n up to 200, values up to 100. Which state works?

Accepted Answer

Boolean dp over sums up to total / 2, 0/1 knapsack style Target is total / 2 at most 10^4, so a sum indexed boolean dp is O(n target). Indices alone do not capture reachable sums. The greedy fails on [3, 3, 2, 2, 2]. Brute force is 2^200.

Question 12

Best Time to Buy and Sell Stock with Cooldown: max profit over many trades, with one day of rest after each sale. What is the minimal state set per day?

Accepted Answer

held, sold today, rested (not holding, free to buy) Cooldown means the day after selling you cannot buy, so not holding must split into just sold and rested. Two states let you buy right after selling. Profit alone loses holding status. Transactions are unlimited here, so counting them is unneeded.

Question 13

Decode Ways (count ways to decode a digit string where 1 to 26 map to A to Z) for s = "10" and s = "06". What should a correct dp return?

Accepted Answer

1 and 0 "10" is only J, and "06" has no valid decoding because a leading 0 is invalid. 2 for "10" counts "1","0", but 0 alone is not a letter. 1 for "06" accepts 6 after an invalid 0.

Question 14

Burst Balloons (bursting balloon i earns nums[left] * nums[i] * nums[right] with its current neighbours; maximize total coins): why define dp[i][j] by the last balloon burst in (i, j) rather than the first?

Accepted Answer

If k is the last burst in (i, j), its neighbours at that moment are the fixed boundaries i and j, so the subproblems (i, k) and (k, j) are independent: dp[i][j] = max over k of dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j]. Choosing the first burst makes neighbours depend on later choices. Total time is O(n^3).

Dynamic programming interview questions

More coding topics

Practise these on your commute