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.

MediumTechnical
83 practiced

You have n items with weights and values (n up to 2000) and a knapsack of capacity W up to 100000. Return the maximum value you can carry and the indices of the items you chose. State the time and space complexity, and what happens to memory at those sizes.

MediumTechnical
93 practiced

Given two strings of length up to 2000, compute the length of their longest common subsequence. Define the table and recurrence, then explain how to cut memory from O(nm) to O(min(n,m)) and what that costs you.

MediumTechnical
81 practiced

Return an actual longest common subsequence of two strings, not just its length. Fill the table, walk back through it to build the string, and say what you do when several answers tie.

HardTechnical
77 practiced

In a tree whose node weights can be negative, find the maximum sum of weights along any path between two nodes (the path may be a single node). Describe what each node returns to its parent versus what it records as the global best, and give the complexity.

EasyTechnical
89 practiced

A cashier always hands over the largest coin that fits. Give denominations and an amount where this gives a non-optimal answer, explain why, and describe the DP that fixes it.

Unlock Full Question Bank

Get access to all 43 Dynamic Programming interview questions and detailed answers.

Sign in to Continue

Join thousands of developers preparing for their dream job.