Dynamic Programming Interview Questions for Data Structures and Algorithms
25 Dynamic Programming questions with answers for data structures and algorithms roles — 6 easy, 12 medium, 7 hard.
About Dynamic Programming
Learn to recognise overlapping subproblems and optimal substructure, define states and transitions, and convert recursion into memoised or tabulated solutions. Practise one-dimensional, grid, knapsack, subsequence, edit distance, interval, tree and bitmask DP, along with space optimisation techniques that interviewers frequently ask for.
Sheet progressStart practicing
3 QUESTIONS FREESign up to unlock the full question bank and track your progress.Unlock every question and answer, then continue practising company-wise and package-wise.
✓ 3 questions free • Unlock the rest in seconds
01
What is dynamic programming, and what are overlapping subproblems and optimal substructure?
Dynamic programming solves a problem by combining solutions of smaller subproblems and storing them so each is computed only once. It applies when a problem has overlapping subproblems, meaning the same smaller problems repeat, as in Fibonacci, and optimal substructure, meaning the best answer can be built from best answers to subproblems, as in shortest paths. DP often turns exponential brute force into polynomial time.
02
What is the difference between memoisation and tabulation?
Memoisation is top-down: write the natural recursion and cache results in a map or array, so only needed states are computed, but recursion depth can be a problem. Tabulation is bottom-up: fill a table iteratively from base cases in an order where dependencies are ready, avoiding recursion overhead and making space optimisation easier. Both usually have the same time complexity; choose whichever is clearer for the problem.
03
A warehouse robot moves only right or down on a grid with some blocked cells. How do you count the number of paths?
Use DP where dp[r][c] is the number of ways to reach cell r, c. A blocked cell has 0 ways; the start has 1; every other cell is dp[r-1][c] plus dp[r][c-1]. Fill row by row in O(rows times columns), and keep a single row array to use O(columns) space. Counts can become huge, so problems often ask for the result modulo 10 to the power 9 plus 7.
04
Solve climbing stairs: how many ways are there to climb n steps taking 1 or 2 steps at a time?
def rob(nums):
take, skip = 0, 0 # best if the previous house is taken or skipped
for x in nums:
take, skip = skip + x, max(take, skip)
return max(take, skip)
# rob([2, 7, 9, 3, 1]) -> 12 (2 + 9 + 1)
# dp[i] = max(dp[i-1], dp[i-2] + nums[i]); O(n) time, O(1) space
06
Tell me about a time you kept working on a hard problem when others had given up.
Situation: a scheduling feature produced suboptimal plans and the team was ready to accept it. Task: I believed an exact solution was possible for our sizes. Action: I spent evenings modelling it, found the number of shifts was small enough for bitmask DP, built a prototype, and validated it against the old greedy output on 200 real cases. Result: plans improved by about 12 percent in cost, and the feature shipped with the new algorithm.
07
How do you recognise a DP problem and define its state?
Signals include asking for a minimum, maximum, count of ways or whether something is possible, with choices at each step that affect later options. Start from brute-force recursion and ask what parameters fully describe a subproblem, such as index, remaining capacity or last chosen item; those become the state. Then write the transition between states, the base cases and the order of computation, and check the state count times transition cost fits limits.
08
Explain the recurrence for the 0/1 knapsack problem.
Let dp[i][w] be the maximum value using the first i items with capacity w. For item i with weight wt and value val, either skip it, giving dp[i-1][w], or take it if wt is at most w, giving dp[i-1][w - wt] plus val; take the larger. Base cases are zero items or zero capacity. Time and space are O(n times W), and space can drop to O(W) by iterating w downwards in a single array.
09
How is the longest common subsequence computed with DP?
Let dp[i][j] be the LCS length of the first i characters of A and the first j characters of B. If A[i-1] equals B[j-1], dp[i][j] is dp[i-1][j-1] plus 1; otherwise it is the maximum of dp[i-1][j] and dp[i][j-1]. Fill the table row by row in O(m times n) time. Backtracking from dp[m][n] recovers the actual subsequence. LCS underlies diff tools and DNA sequence comparison.
10
How can you reduce the space used by a DP solution?
If each row of the table depends only on the previous row, keep two rows or even a single array, reducing O(n times m) space to O(m). Fibonacci-like problems need only the last two values, so O(1). For 0/1 knapsack in one array, iterate capacity from high to low so each item is used once; for unbounded knapsack iterate low to high. The trade-off is that reconstructing the actual solution becomes harder.
Edit distance, or Levenshtein distance, is the minimum number of insertions, deletions and substitutions to turn one string into another. dp[i][j] is the distance between the first i characters of A and the first j of B; if characters match, take dp[i-1][j-1], otherwise 1 plus the minimum of the three neighbouring cells. It runs in O(m times n) and is used in spell checkers, fuzzy search, DNA alignment and plagiarism detection.
12
Your recursive solution passes with memoisation, but the interviewer asks for a bottom-up version. How do you convert it?
I identify the recursion parameters, which become the table dimensions, and the base cases, which become the initial cells. Then I look at which states each call depends on, for example index plus 1, and fill the table in the opposite order, so dependencies are computed first. The recursive transition becomes the loop body. Finally I check whether only the last row is used, so I can reduce space, and walk through a small example.
13
A search box must suggest the closest dictionary words when a user makes a typo. How would you approach it?
Compute edit distance between the typed word and candidate words, suggesting those within distance 1 or 2. Running O(m times n) DP against a whole dictionary is slow, so narrow candidates first using a BK-tree indexed by edit distance, a trie with bounded edit distance search, or n-gram indexes. Then rank candidates by distance and word popularity. Keyboard-aware substitution costs can improve suggestions further.
14
You need to build a tool that shows the differences between two versions of a file line by line. What algorithm would you use?
The core is the longest common subsequence over lines: lines in the LCS are unchanged, and the rest are additions or deletions. Hash each line first so comparisons are fast. Classic LCS DP is O(m times n), which is too slow for large files, so real diff tools use Myers' algorithm, which runs in O((m plus n) times d), where d is the number of differences, fast when versions are similar.
15
Find the minimum number of coins needed to make an amount.
def coin_change(coins, amount):
INF = amount + 1
dp = [0] + [INF] * amount # dp[x] = min coins for amount x
for x in range(1, amount + 1):
for c in coins:
if c <= x and dp[x - c] + 1 < dp[x]:
dp[x] = dp[x - c] + 1
return dp[amount] if dp[amount] != INF else -1
# coin_change([1, 3, 4], 6) -> 2 (3 + 3)
# O(amount * len(coins)) time, O(amount) space
16
Compute the length of the longest common subsequence of two strings.
def knapsack(weights, values, capacity):
dp = [0] * (capacity + 1) # dp[w] = best value with capacity w
for wt, val in zip(weights, values):
for w in range(capacity, wt - 1, -1): # go downwards: each item once
dp[w] = max(dp[w], dp[w - wt] + val)
return dp[capacity]
# knapsack([1, 3, 4], [15, 20, 30], 4) -> 35
# O(n * W) time, O(W) space
18
How do you handle pressure during a timed online coding test?
Situation: in a 90-minute test I faced three problems, one of them a tough DP. Task: maximise my score. Action: I read all problems first, solved the easiest one quickly to secure marks, wrote a brute-force version of the DP problem for partial credit, then improved it to memoised DP once I spotted the state. I kept an eye on time at fixed checkpoints. Result: I cleared all test cases on two problems and most of the third.
Bitmask DP represents a subset of up to about 20 items as the bits of an integer, so the state can be the set of items already used plus perhaps the last item. The travelling salesman problem uses dp[mask][last], the minimum cost to visit the cities in mask ending at last, giving O(2 to the power n times n squared) instead of n factorial. It is used for assignment, scheduling and covering problems with small n.
DP on trees computes values for each node from the values of its children, usually in a postorder DFS. For the maximum independent set, where no two chosen nodes are adjacent, each node keeps two values: the best if it is taken, which is its value plus the not-taken values of children, and the best if it is not taken, the sum of each child's better option. This runs in O(n) and also solves house robber on a tree.
21
What is interval DP? Explain with matrix chain multiplication.
Interval DP defines states over a range i to j and combines smaller ranges. In matrix chain multiplication, dp[i][j] is the minimum scalar multiplications to multiply matrices i through j. Try every split point k between i and j: dp[i][k] plus dp[k+1][j] plus the cost of multiplying the two results. Fill by increasing interval length, O(n cubed). Similar patterns solve burst balloons and palindrome partitioning.
22
How do you find the longest increasing subsequence in O(n log n)?
The simple DP is O(n squared): dp[i] is the LIS ending at i. The faster method keeps an array tails, where tails[k] is the smallest possible last value of an increasing subsequence of length k plus 1. For each number, binary search tails for the first value not less than it and replace it, or append if none. The length of tails is the LIS length. This patience sorting idea also helps in envelope nesting problems.
23
A company has a fixed budget and several projects with costs and expected returns. How would you choose projects to maximise return?
If each project is all or nothing, this is the 0/1 knapsack problem: budget is capacity, cost is weight and return is value, solved with DP in O(projects times budget), and tracking choices lets me list selected projects. If the budget is very large, I would scale costs to units such as lakhs to keep the table small, or use DP over value instead. Extra constraints like dependencies change the state design.
24
Your knapsack DP has n equal to 100 items but capacity up to 10 to the power 9, so the table does not fit in memory. What do you do?
A table indexed by capacity is impossible, so I change the state. If item values are small, use dp[v] as the minimum weight needed to achieve value v, then pick the largest v whose weight fits the capacity; that is O(n times total value). If n is about 40, meet in the middle: enumerate subsets of each half, sort one side and binary search. Otherwise approximation or branch and bound are options.
def edit_distance(a, b):
m, n = len(a), len(b)
prev = list(range(n + 1)) # distances from empty prefix of a
for i in range(1, m + 1):
cur = [i] + [0] * n
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
cur[j] = prev[j - 1]
else:
cur[j] = 1 + min(prev[j], # delete
cur[j - 1], # insert
prev[j - 1]) # replace
prev = cur
return prev[n]
# edit_distance('horse', 'ros') -> 3; O(m * n) time, O(n) space
Frequently asked questions
How important is Dynamic Programming in Data Structures and Algorithms interviews?
Learn to recognise overlapping subproblems and optimal substructure, define states and transitions, and convert recursion into memoised or tabulated solutions. Practise one-dimensional, grid, knapsack, subsequence, edit distance, interval, tree and bitmask DP, along with space optimisation techniques that interviewers frequently ask for.
How should I use the Dynamic Programming sheet?
Go top to bottom — easy to hard. Answer before opening each answer, tick what you solved and save misses to Last-Minute Revision.