Dynamic Programming Questions

Algorithmic technique for solving problems with overlapping subproblems and optimal substructure. Candidates should demonstrate identifying states and transitions, choosing memoization or bottom up tabulation, analyzing time and space complexity, reconstructing solutions from computed tables, and optimizing space or state when possible. Practice includes classic problems such as longest common subsequence, knapsack, coin change, matrix path problems, and partition problems. Interview assessment focuses on problem formulation, correctness proofs, trade offs between recursion and iterative approaches, and clear coding of the solution with edge case handling and complexity justification.

HardTechnical

91 practiced

You must design a DP over intervals with very large endpoints (up to 1e18) but n <= 2e5. Explain how to use coordinate compression and hashing to compress the domain, how to build DP transitions over compressed coordinates, and discuss pitfalls (off-by-one shifts, memory limits, and mapping back to original coordinates). Show how this reduces memory/time and give an example.

Sample Answer

Approach (high level)When endpoints are up to 1e18 but n ≤ 2e5, you cannot allocate arrays sized by coordinate. Use coordinate compression: collect all distinct endpoints (and any +1/-1 boundaries you need for half-open intervals), sort them, map each original coordinate to its index. Use hashing (unordered_map) only if random access to original values is needed without storing huge arrays.

Steps1. Collect coordinates: for every interval [L,R] add L and R and, if transitions depend on gaps (e.g. DP on points vs segments), also add R+1 or L-1 as needed.2. Sort unique list coords[]. Build map coord -> idx (0..m-1). Use vector for coords and an unordered_map<long long,int> for lookups (or binary search if you avoid hashing).3. Build DP over indices 0..m-1. When your DP needs segment lengths or costs, compute original length as coords[i+1]-coords[i] (for segment i) or coords[idx] when mapping back.4. Transitions: translate any condition using original values into equivalent on indices. E.g., if you need to add weight proportional to interval length, weight = coords[r_idx+1]-coords[l_idx].

Pitfalls- Off-by-one: decide whether coords represent points or segments. If intervals are inclusive [L,R], mapping to segments often requires adding R+1 to represent the half-open endpoint. Forgetting this causes off-by-one bugs.- Memory: m ≤ 2n (or 3n if you add +1), so DP arrays O(n) not O(1e18). But watch constant factors: avoid O(m^2) structures. Use sparse structures or segment trees over compressed indices if necessary.- Hash collisions: unordered_map<long long,int> is safe; avoid custom poor hashes. Prefer vector+binary_search when possible for determinism.- Mapping back: any answer computed on compressed indices must be converted using coords[] to original units (lengths, positions). Keep coords as 64-bit.

Complexity & benefit- Time: sorting coords O(n log n). Each DP transition works on m indices, so time scales in O(m log m) or O(m) depending on data structure. Memory: O(m) instead of O(max_coordinate).Examplen=3 intervals: [1,1e18], [5,10], [1e9,1e9+5]. coords = {1,5,10,1e9,1e9+5,1e18,(1e18+1 if using half-open)} => m≈6. DP over m indices computes costs using original gaps like coords[i+1]-coords[i], enabling correct weights without huge arrays.

This pattern reduces memory/time from impossible (1e18) to manageable O(n log n) and is standard for interval DP at scale.

MediumTechnical

89 practiced

Implement the Viterbi algorithm for a Hidden Markov Model in Python: given transition matrix A, emission matrix B, initial probabilities pi, and an observation sequence O, return the most likely hidden state sequence and its log-probability. Include backpointers for reconstruction and discuss numerical stability (use of log-space). State complexity in terms of T (time steps) and S (states).

Sample Answer

To implement Viterbi robustly, run the DP in log-space to avoid underflow: compute log(pi) + sum of log transitions and log emissions. Keep two arrays per time step: delta[t][s] = max log-prob of path ending in state s at time t, and psi[t][s] = argmax previous state. Reconstruct by backtracking psi from argmax at final time.

python

import math
from typing import List, Tuple

def log(x):
    return math.log(x) if x > 0 else float("-inf")

def viterbi(A: List[List[float]], B: List[List[float]], pi: List[float], O: List[int]) -> Tuple[List[int], float]:
    """
    A: SxS transition matrix (A[i][j] = P(s_j | s_i))
    B: SxM emission matrix (B[s][o] = P(o | s))
    pi: length-S initial state probs
    O: length-T observation indices (0..M-1)
    Returns: (most likely state sequence as list of state indices, log-probability)
    """
    S = len(pi)
    T = len(O)
    if S == 0 or T == 0: 
        return ([], float("-inf") if T>0 else 0.0)

    # precompute logs
    logA = [[log(a) for a in row] for row in A]
    logB = [[log(b) for b in row] for row in B]
    logpi = [log(p) for p in pi]

    # dp arrays: delta_prev, delta_curr: length S
    delta = [logpi[s] + logB[s][O[0]] for s in range(S)]
    psi = [[0]*S for _ in range(T)]  # backpointers

    for t in range(1, T):
        new_delta = [float("-inf")] * S
        for j in range(S):
            best_val = float("-inf")
            best_state = 0
            emit = logB[j][O[t]]
            for i in range(S):
                val = delta[i] + logA[i][j] + emit
                if val > best_val:
                    best_val = val
                    best_state = i
            new_delta[j] = best_val
            psi[t][j] = best_state
        delta = new_delta

    # termination
    best_final = max(range(S), key=lambda s: delta[s])
    best_logp = delta[best_final]

    # backtrack
    path = [0]*T
    path[-1] = best_final
    for t in range(T-1, 0, -1):
        path[t-1] = psi[t][path[t]]

    return path, best_logp

Key points:- Use log-space to prevent underflow; treat zeros as -inf.- Time complexity: O(T * S^2) (for dense A). Space: O(T * S) for psi plus O(S) for current DP row. You can reduce space to O(S) for psi if you store backpointers compactly or only keep last K steps.- Edge cases: zero probabilities, empty observations, non-normalized matrices (works in log-space but semantically expect probabilities).

MediumTechnical

69 practiced

Given a directed acyclic graph (DAG) with weighted edges, design an algorithm to compute the longest path lengths from a source to all other nodes using DP/topological ordering. Provide pseudocode, prove correctness briefly and analyze complexity. How does this DP relate to dynamic programming used in sequence models?

Sample Answer

Approach: Perform a topological sort of the DAG, then relax edges in topological order to compute longest path distances from source. Because topological order respects dependencies, each node's best incoming path is final when processed — classic DP over DAG.

Pseudocode:

python

def longest_paths_dag(graph, source):
    # graph: adjacency list {u: [(v, weight), ...]}
    topo = topological_sort(graph)            # list of nodes in topo order
    dist = {node: -inf for node in graph}
    dist[source] = 0
    for u in topo:
        if dist[u] == -inf: continue
        for v, w in graph[u]:
            # relax for longest path
            if dist[u] + w > dist[v]:
                dist[v] = dist[u] + w
    return dist

Correctness (brief): Topological order ensures all predecessors of u appear before u. When processing u, dist[u] already equals the maximum achievable from source through any predecessor because all those predecessors were processed and their outgoing relaxations considered. By induction over topo order, dist values become optimal.

Complexity: Topological sort O(V+E). Single pass relaxations visit each edge once → O(V+E) total time. Space O(V) for dist (plus graph storage).

Relation to sequence-model DP: This is an instance of DP over a partial order: states are nodes, transitions are weighted edges. Like Viterbi/forward algorithms, you compute optimal scores by combining previous state scores with transition scores in an order that respects dependencies. In sequence models the order is linear (time steps); in DAG DP the order is given by a topological sort. Both use memoization, local transition combination, and dynamic programming to avoid recomputation.

MediumTechnical

99 practiced

You are given a working recursive memoized DP whose states are tuples (i,j). Explain step-by-step how to convert it into an iterative bottom-up tabulation. Explain how to determine a safe iteration order, and illustrate using the example dp[i][j] depends on dp[i-1][j] and dp[i][j-1]. Discuss pros and cons of conversion.

Sample Answer

Approach (step-by-step):1. Identify state space and base cases your memoized recursion uses (all (i,j) values and which return immediately).2. Extract recurrence: dp(i,j) = f(dp(a,b) for (a,b) in predecessors). List predecessors for each state.3. Choose iteration order so every state's predecessors are already computed when you compute it. That requires a topological ordering of the implicit DAG of states.4. Translate recursive calls into nested loops that follow that order, initialize dp with base values, and fill table iteratively.

Safe iteration order (how to determine):- Build dependency directions. If dp[i][j] depends only on dp[i-1][j] and dp[i][j-1], both predecessors have smaller i or smaller j. A safe order is increasing i and, for each i, increasing j (row-major), or increasing j then i (column-major) — both work because predecessors lie "earlier".- General rule: sort states so predecessor → successor. For grid-like indices, monotonic increasing loops matching dependency axes are safe.

Concrete example (dp[i][j] depends on dp[i-1][j] and dp[i][j-1]):- Base: dp[0][*], dp[*][0] known.- Loop row-major:

python

def tabulate(m, n):
    dp = [[0]*(n+1) for _ in range(m+1)]
    # initialize base cases
    for i in range(m+1):
        dp[i][0] = base_i0(i)
    for j in range(n+1):
        dp[0][j] = base_0j(j)
    for i in range(1, m+1):
        for j in range(1, n+1):
            dp[i][j] = combine(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

Pros of conversion:- Eliminates recursion overhead and stack depth; often faster and more memory-efficient (no memo recursion stack).- Easier to analyze and to apply memory optimizations (rolling arrays).- Predictable iteration for parallelization or vectorization.

Cons / caveats:- Finding correct order can be nontrivial for complex, non-acyclic, or cyclic-like dependencies (need topological sort).- Tabulation may require allocating the full DP table even when memoization touches a small subset; higher memory for sparse reachable states.- More boilerplate to initialize many base cases; less intuitive if recurrence branches deeply.

When to prefer each:- Use tabulation for performance, stack safety, and when many states are reachable. Keep memoization when reachable states are sparse, or order is hard to derive.

EasyTechnical

94 practiced

Write a Python function to compute the length of the Longest Common Subsequence (LCS) between two strings s and t using bottom-up DP. Discuss time and space complexity. Input sizes: |s|,|t| up to 2000 — what memory issues might arise and how would you mitigate them?

Sample Answer

Approach — bottom-up DP with space optimization:- Standard DP uses a (n+1)x(m+1) table where dp[i][j] = LCS length of s[:i], t[:j]. Recurrence: if s[i-1]==t[j-1]: dp[i][j]=dp[i-1][j-1]+1 else dp[i][j]=max(dp[i-1][j],dp[i][j-1]).- For memory reasons (|s|,|t| up to 2000), we use two rolling rows (previous and current) so space is O(min(n,m)).

Code (bottom-up, rolling rows):

python

def lcs_length(s: str, t: str) -> int:
    """
    Returns length of Longest Common Subsequence between s and t.
    Time: O(n*m). Space: O(min(n,m)).
    """
    # ensure t is the shorter string to minimize row width
    if len(t) > len(s):
        s, t = t, s

    n, m = len(s), len(t)
    prev = [0] * (m + 1)  # previous row
    curr = [0] * (m + 1)  # current row

    for i in range(1, n + 1):
        # reset curr[0] = 0 implicitly
        si = s[i - 1]
        for j in range(1, m + 1):
            if si == t[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                # max of skip s[i-1] (prev[j]) or skip t[j-1] (curr[j-1])
                curr[j] = prev[j] if prev[j] >= curr[j - 1] else curr[j - 1]
        prev, curr = curr, prev  # swap references; reuse arrays to avoid realloc
    return prev[m]

Key points and reasoning:- Time complexity: O(n * m) where n = len(s), m = len(t).- Space complexity: O(min(n, m)) because we only keep two rows of length m+1; swapping ensures we reuse buffers without reallocation.- Memory issues at size 2000: full (2001 x 2001) Python int table is very heavy (Python ints and nested lists add large overhead) and can consume hundreds of MB. Using rolling arrays reduces memory drastically (≈ O(2000) integers).- Further mitigations: if you need even lower overhead, use array('H') or array('I') from the array module or numpy.int16/32 to store small integers compactly (safe since LCS ≤ min(n,m)). Example: from array import array; prev = array('H', [0])*(m+1).- Edge cases: one or both strings empty (returns 0), identical strings (returns len(s)), non-ASCII characters (works fine since comparisons are on characters).

Unlock Full Question Bank

Get access to hundreds of Dynamic Programming interview questions and detailed answers.

Join thousands of developers preparing for their dream job.