Dynamic Programming interview questions

Dynamic programming interview questions on state definition, recurrence transitions, memoisation, tabulation and recognising overlapping subproblems.

6 questions in Data Structures & Algorithms.

Data Structures & AlgorithmsA 26-minute read on how the topic fits together, before the questions.Data structures and algorithms fundamentals54 short answers on one page, for revising rather than studying.

medium3

mediumCodingConcept

Edit distance where insert costs 1, delete costs 2 and replace costs 3. Define the DP state and the recurrence, and tell me what changes from the classic version.

The state is unchanged - the minimum cost to transform the first i characters of one string into the first j of the other - because the subproblem structure does not depend on what operations cost. Only the recurrence changes, adding a per-operation weight instead of a uniform 1, and the base cases become multiples of the insert and delete costs rather than i and j.

4 minmid, senior

mediumCoding

Given a set of coin denominations and a target amount, return the fewest coins that make it exactly. Why would you not just take the largest coin first each time?

Largest-coin-first fails on denominations like 1, 3 and 4, so you fill a table where entry i is the fewest coins making amount i and each entry takes the best over all denominations. The unreachable case needs a sentinel that survives being incremented, which rules out the maximum integer.

4 minentry, mid, senior

mediumCodingConcept

How do you know a problem is dynamic programming?

Dynamic programming interview questions usually need overlapping subproblems, optimal substructure and a precise state definition. Define the minimum state, write the transition, then choose memoisation or tabulation based on dependency order.

5 minmid, senior

hard3

hardCodingConcept

Assign n tasks to n workers at minimum cost, with n up to 20. Why a bitmask, and what does it cost?

Bitmask DP keeps the cheapest cost for every subset of workers already used. The number of set bits says which task comes next, so there are 2^n states with n moves each, O(2^n * n) time and 2^n memory. At n = 20 that is about a million states, where trying all 20! orders is hopeless.

4 minmid, senior

hardCoding

Envelopes nest only when both width and height are strictly larger. How many can you nest, and why must equal widths be sorted by height descending?

Russian doll envelopes reduce to a longest increasing subsequence. Sort by width ascending, break width ties by height descending, then run the O(n log n) tails search on heights. The descending tie-break stops equal widths from chaining, since a strictly increasing run then takes at most one per width.

4 minmid, senior, staff

hardCoding

Find the length of the longest strictly increasing subsequence, then get it under quadratic time.

The quadratic dynamic programme asks for the best chain ending at each index. The faster version keeps one array where slot j holds the smallest possible tail of an increasing subsequence of length j plus one; that array stays sorted, so each element is placed by binary search for O of n log n.

6 minmid, senior, staff