Top 8 Dynamic programming Interview Questions
Browse 8 real-world technical and behavioral interview questions about Dynamic programming. Review scenarios, edge cases, and architectural best practices.
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.
Find the cheapest flight from one city to another using at most K stops. Why does plain Dijkstra give the wrong answer?
Plain Dijkstra minimises cost alone, so it can return a cheap route with too many stops, and settling each city once discards a dearer route that still has stops to spare. Make the state city plus edges used, or run Bellman-Ford for exactly K + 1 rounds, each reading only the previous round's distances.
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.
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.
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.
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.
Find the largest sum obtainable from a contiguous run of elements in an array.
Walk the array once, keeping the best sum ending at the current element - that element alone, or that element added to the best run ending before it. The maximum of those is the answer, and the familiar version that resets the running sum to zero is wrong when every element is negative.
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.