← DSA interview questions

Dynamic Programming Interview Questions

Dynamic programming trips people up because the syntax is easy and the thinking is not. The interview version is almost always: can you define a small state vector that captures everything the future depends on, write a recurrence that respects problem constraints, and argue correctness without waving at "overlapping subproblems" like a magic spell. At mid-level and above, interviewers want to hear why your state is minimal—if you carry the entire history when only the last two rows matter, they will notice.

Memoization first, tabulation when stable

Top-down DP is often faster to derive in the room: you write the recursive structure that mirrors the problem statement, add a cache keyed by arguments, and stop when the parameter space explodes. Bottom-up shines when you need constant space—rolling arrays for knapsack variants—or when iteration order matters for optimization. Be honest about trade-offs: memoization can stack-overflow on deep recursion; tabulation can waste cells if your state is sparse.

Red flags interviewers listen for

Make it human with one production analogy

Scheduling shifts, segmenting user sessions, or optimizing ad spend under caps—all are DP-shaped stories if you squint. Pick one real constraint you have optimized and keep it in your back pocket; it turns a dry grid problem into proof you optimize under business rules, not only puzzle rules. Continue with Blind 75–style drills so pattern recognition becomes automatic before the clock starts.

DP outside the whiteboard: budgets and batches

Minimize cost to process jobs on Azure Batch (scored like knapsack / scheduling DP)

# jobs[i] = (duration_min, cost_if_spot, cost_if_reserved)
# cap: finish within T minutes — pick subset / order (toy idea)
def min_cost(jobs, T):
    # state: dp[t] = min cost to fill exactly t minutes (simplified)
    INF = 10**18
    dp = [INF] * (T + 1)
    dp[0] = 0
    for dur, spot, res in jobs:
        for t in range(T, dur - 1, -1):
            dp[t] = min(dp[t], dp[t - dur] + min(spot, res))
    return min(dp)

Finance and platform teams argue about spot vs reserved VMs on Azure. You are not solving full MIP in an interview—you are showing you can define state ("minutes used"), transitions ("add this job"), and why greedy fails when jobs have weird cost curves. That maps cleanly to "explain knapsack to a PM."

Questions with sample answers

These are interview-ready outlines—sound human by swapping in your own metrics, team names, and war stories. The examples are generic on purpose so you can map them to what you actually shipped.

  1. Primary prompt

    House robber variant: maximize sum with no two adjacent elements chosen—define state and transition in one sentence.

    State: dp[i] = max money up to house i. Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i])—either skip current or rob current + best up to i-2.

    Example: [2,7,9,3,1] → 2+9+1=12. O(n) time, O(1) space with two rolling variables.

  2. Primary prompt

    Longest increasing subsequence: O(n log n) patience sorting approach vs classic DP—when would you pick each?

    O(n²) DP: dp[i] = length ending at i; fine for n ≤ few thousand. O(n log n): maintain smallest tail array; binary search placement—when you only need length, not the actual subsequence, or n is large.

  3. Primary prompt

    0/1 knapsack with small capacity but many items—how does state dimensionality change your implementation?

    State is dp[c] = max value for capacity c; iterate items outer loop, capacity inner loop descending to avoid reusing same item. Complexity O(n × W); if W is small (≤10⁴) it's feasible even if n is huge.

  4. Primary prompt

    Edit distance between two strings—how do you optimize space once the full table is understood?

    Only previous row of DP table needed for Levenshtein: keep two arrays of length m+1, swap each row. Time O(nm), space O(min(n,m)) with shorter string as columns.

Follow-ups interviewers often ask

Expect nested "why?" questions—brief answers here; expand with your production defaults.

  1. Follow-up

    Prove overlapping subproblems exist for your recurrence.

    Same substring pair (i,j) is reached from multiple parent paths—memo/table fills each cell once; without DP, exponential recomputation of identical subproblems.

  2. Follow-up

    What is the base case and does your loop order respect dependencies?

    For grid DP, typically initialize first row/column; nested loops increase i,j so dependencies (top, left) already computed. State explicitly to avoid out-of-order access bugs.

  3. Follow-up

    When does top-down beat bottom-up in an interview setting?

    When state space is sparse—many subproblems never reached—memoized DFS explores only needed states. Bottom-up is better when you fill most of the table anyway or need iterative space optimization.

  4. Follow-up

    How would you reconstruct the optimal solution, not only the score?

    Keep parent pointers or choice table alongside DP; backtrack from optimal cell. Example: knapsack—store whether item i was taken at capacity c.

  5. Follow-up

    What if weights or costs overflow 32-bit integers—where does your code break?

    Use 64-bit or BigInt; compare with INF sentinel that does not overflow when adding edge weights; Python ints are arbitrary precision—still mention production awareness.