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

85 practiced

Implement wildcard pattern matching is_match(s: str, p: str) -> bool in Python supporting '?' (single char) and '*' (matches any sequence, including empty) using DP with O(n*m) time and O(n*m) space. Then discuss and implement (or describe) the greedy two-pointer approach that runs in average linear time and prove when the greedy method is correct versus when DP is necessary.

Sample Answer

To solve wildcard matching, use DP first (O(n*m) time & space), then a greedy two-pointer approach that's linear on average.

DP approach (clear, correct):

python

def is_match_dp(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [[False]*(n+1) for _ in range(m+1)]
    dp[0][0] = True
    # empty s matched by leading '*' in p
    for j in range(1, n+1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-1]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if p[j-1] == '?':
                dp[i][j] = dp[i-1][j-1]
            elif p[j-1] == '*':
                # '*' matches empty (dp[i][j-1]) or consumes one char (dp[i-1][j])
                dp[i][j] = dp[i][j-1] or dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j-1] and s[i-1] == p[j-1]
    return dp[m][n]

Key points:- Handles '?' as single-char, '*' as any-length (including 0).- Time: O(m*n), Space: O(m*n). Can reduce space to O(n) by rolling array.

Greedy two-pointer approach (O(m+n) average, O(m*n) worst-case):Idea: scan s and p with pointers i,j. When encountering '*' in p, record star position (star_j) and the position in s when star started (star_i). Advance p past '*' and try to match remainder. If mismatch later, backtrack: set j = star_j+1 and star_i += 1, set i = star_i (i.e., let '*' absorb one more char), continue. If no star to backtrack, fail.

Implementation sketch:

python

def is_match_greedy(s: str, p: str) -> bool:
    i = j = 0
    m, n = len(s), len(p)
    star_i = -1
    star_j = -1
    while i < m:
        if j < n and (p[j] == '?' or p[j] == s[i]):
            i += 1; j += 1
        elif j < n and p[j] == '*':
            star_j = j
            star_i = i
            j += 1
        elif star_j != -1:
            # backtrack: let '*' consume one more char
            star_i += 1
            i = star_i
            j = star_j + 1
        else:
            return False
    # consume trailing '*' in pattern
    while j < n and p[j] == '*':
        j += 1
    return j == n

When greedy is correct vs DP necessary:- Greedy is correct for this wildcard grammar ('?' and '*' only) because '*' is the only operator with unbounded repetition and greedy with backtracking over the last '*' suffices to explore necessary expansions. The algorithm effectively simulates nondeterministic choices lazily: it always prefers to match pattern characters directly, but remembers the last '*' to try alternative allocations when a mismatch occurs.- DP is necessary when patterns include additional constructs that create non-regular dependencies (e.g., bounded repeats, character classes with intersections, or when you need guaranteed worst-case bounds). Also, worst-case input patterns like many '*' interleaved with specific chars can degrade greedy to O(m*n) due to repeated backtracking; DP gives predictable O(m*n) time and is simpler to reason about formally.

Edge cases:- Empty pattern vs non-empty string and vice versa- Multiple consecutive '*' (greedy handles them; DP initialization handles them)- Long runs causing worst-case backtracking — prefer DP if worst-case guarantees required.

MediumTechnical

87 practiced

Implement Damerau–Levenshtein distance in Python to handle insertions, deletions, substitutions, and adjacent transpositions. Provide the DP formulation and handle edge cases (empty strings, repeated characters). Discuss runtime and where in ML this is useful (e.g., spell correction).

Sample Answer

We can implement the "true" Damerau–Levenshtein distance (allows insertions, deletions, substitutions, and adjacent transpositions) using a dynamic programming matrix with an auxiliary last-seen dictionary to correctly handle multiple repeated characters. DP formulation: let s, t be strings (1-indexed). Use a matrix D of size (len(s)+2)x(len(t)+2) initialized with large value INF and D[0][0]=INF, D[1][1]=0, and row/column offsets for costs. For i,j, compute cost = 0 if s[i-1]==t[j-1] else 1. Then:D[i+1][j+1] = min( D[i][j] + cost, # substitution/match D[i+1][j] + 1, # insertion D[i][j+1] + 1, # deletion D[k-1][l-1] + (i-k-1) + 1 + (j-l-1) # transposition via last indices k,l)where k = last index of t[j-1] in s seen before i (from DA), l = last index of s[i-1] in t seen before j.

Implementation (based on Lowrance & Wagner / Wikipedia):

python

def damerau_levenshtein(s: str, t: str) -> int:
    # Handles empty strings
    if s == t:
        return 0
    n, m = len(s), len(t)
    INF = n + m
    # DP matrix of size (n+2) x (m+2)
    D = [[0] * (m + 2) for _ in range(n + 2)]
    D[0][0] = INF
    for i in range(0, n + 1):
        D[i + 1][0] = INF
        D[i + 1][1] = i
    for j in range(0, m + 1):
        D[0][j + 1] = INF
        D[1][j + 1] = j

    # last seen positions in s/t for each character
    da = {}
    for i in range(1, n + 1):
        db = 0
        for j in range(1, m + 1):
            i1 = da.get(t[j - 1], 0)
            j1 = db
            cost = 0 if s[i - 1] == t[j - 1] else 1
            if cost == 0:
                db = j
            # substitution / match / insertion / deletion
            D[i + 1][j + 1] = min(
                D[i][j] + cost,
                D[i + 1][j] + 1,
                D[i][j + 1] + 1,
                D[i1][j1] + (i - i1 - 1) + 1 + (j - j1 - 1)  # transposition
            )
        da[s[i - 1]] = i
    return D[n + 1][m + 1]

Key points:- The auxiliary da/db track last positions so transpositions across distance (not only adjacent) are handled correctly even with repeats.- Edge cases: empty strings return len(other); identical strings return 0; repeated chars handled by last-seen map.- Time complexity: O(n*m) time, O(n*m) space. You can reduce space in simpler Levenshtein but true Damerau–Levenshtein requires this matrix and last-seen map to correctly account for transpositions.- ML relevance: useful in preprocessing/feature engineering for NLP tasks—spell correction, fuzzy matching, data deduplication, approximate string lookup for entity resolution, and generating candidate lists for noisy-channel spelling models. In production, compute-heavy use can be optimized with indexing (BK-trees, n-gram filters) or approximated with embedding distances for large corpora.

MediumTechnical

98 practiced

Explain the bitmask DP approach used for TSP (Held-Karp): define DP[mask][i] meaning, show the transition to extend subsets, and state time and space complexity. For n up to 20 explain practical implementation details: bit operations to iterate masks, ways to precompute distances, and common optimizations such as pruning and symmetry reductions.

Sample Answer

DP definition and core transition- DP[mask][i] = minimum cost to start at fixed root (say node 0), visit exactly the set of nodes given by bitmask mask (mask includes i), and finish at node i.- Base: DP[1<<0][0] = 0 (only root visited); others INF.- Transition (extend subsets): for every mask and every end i with mask&(1<<i): DP[mask][i] = min over j != i and mask&(1<<j) of DP[mask ^ (1<<i)][j] + dist[j][i] After filling all masks, answer = min_i DP[(1<<n)-1][i] + dist[i][0] (return to root).

Complexities- Time: O(n^2 * 2^n) because for each of 2^n masks and each end i you scan up to n predecessors j.- Space: O(n * 2^n) to store DP table.

Practical implementation details for n ≤ 20- Precompute a full distance matrix dist[i][j] (Euclidean, graph shortest paths, or model-specific costs) so inner loops are O(1).- Represent DP as a flat array of size (1<<n) * n (e.g., vector<double>) to improve cache locality. Index = mask*n + i.- Iterate masks in increasing population order (for k=1..n) or simply for mask in 0..(1<<n)-1; ensure you only process i when mask has bit i set: if (mask & (1<<i)) { ... }.- Bit operations: - test bit: mask & (1<<i) - remove bit i: prev = mask ^ (1<<i) - iterate all set bits i: for (int sub = mask; sub; sub &= sub-1) { int i = __builtin_ctz(sub); ... } - iterate predecessors j inside mask: for (int j = mask; j; j &= j-1) { int idx = __builtin_ctz(j); if (idx==i) continue; ... }- Use fast intrinsics: __builtin_popcount, __builtin_ctz for ordering and extracting lowest set bit.

Common optimizations- Fix start to break symmetry (root = 0) — reduces states by factor n for cyclic symmetry.- Prune with heuristics: maintain a current best tour from greedy or 2-approx; skip DP branches whose partial cost + admissible lower bound (e.g., MST on remaining nodes or nearest-neighbor min edges) exceed current best — helpful when turning DP to branch-and-bound.- Memory/time trade-offs: if memory tight, compute DP by increasing mask size and discard layers not needed, or store only reachable states.- Use integer costs when possible for speed; use sentinel INF that's safe from overflow.- Parallelize across masks of same popcount and use vectorized operations where possible.

Why this is useful (ML engineer perspective)- Held–Karp is an exact algorithm for small n (≤20) and can be used as a benchmark or oracle for approximations, hyperparameter search ordering, or combinatorial layers in models. Implementing it efficiently (bit tricks, precompute costs, pruning) makes it practical in real pipelines where exact small-scale solutions are needed.

MediumTechnical

73 practiced

Implement the forward algorithm for a given Hidden Markov Model to compute the probability of an observation sequence O = o1..oT. Provide Python pseudocode that computes forward probabilities α_t(s). Explain how you would modify it for numerical stability (scaling factors or log-space) and show how to obtain log-likelihood. Use a small example HMM and sequence of length 10 in your explanation.

Sample Answer

Approach: use the forward algorithm to compute α_t(s) = P(o1..ot, state_t = s). I'll give straightforward Python pseudocode, then a numerically stable version using scaling factors and show how to get log-likelihood. Finally a small 2-state discrete HMM example with a sequence of length 10.

Basic forward (may underflow for long T)

python

import numpy as np

def forward(A, B, pi, O):
    # A: (N,N) transition, B: (N,M) emission probs, pi: (N,) initial, O: list of obs indices length T
    N = A.shape[0]; T = len(O)
    alpha = np.zeros((T, N))
    # t=0
    alpha[0] = pi * B[:, O[0]]
    for t in range(1, T):
        for j in range(N):
            alpha[t,j] = B[j, O[t]] * np.sum(alpha[t-1] * A[:, j])
    prob = np.sum(alpha[T-1])
    return alpha, prob

Numerical stability — scaling factors- At each t compute c[t] = 1 / sum(alpha[t]) and multiply alpha[t] *= c[t]. Store log-likelihood = -sum(log(c[t])).

Stable forward with scaling:

python

def forward_scaled(A, B, pi, O):
    N = A.shape[0]; T = len(O)
    alpha = np.zeros((T, N))
    c = np.zeros(T)
    alpha[0] = pi * B[:, O[0]]
    c[0] = 1.0 / np.sum(alpha[0])
    alpha[0] *= c[0]
    for t in range(1, T):
        for j in range(N):
            alpha[t,j] = B[j, O[t]] * np.sum(alpha[t-1] * A[:, j])
        c[t] = 1.0 / np.sum(alpha[t])
        alpha[t] *= c[t]
    log_likelihood = -np.sum(np.log(c))  # log P(O)
    return alpha, log_likelihood

Log-space alternative- Work with logA, logB, logpi and use log-sum-exp for numeric safety. That yields log α directly; final log-likelihood = logsumexp(log_alpha[T-1]).

Complexity: O(N^2 T) time, O(N T) space (can reduce to O(N)). Space/time same for scaled/log versions.

Example HMM (N=2, emissions {0,1}), sequence length 10:- A = [[0.7,0.3],[0.4,0.6]]- B = [[0.9,0.1],[0.2,0.8]]- pi=[0.6,0.4]- Example sequence O = [0,0,1,0,1,1,0,0,1,0] (length 10)

Using forward_scaled returns alpha matrix and log_likelihood (e.g. ≈ -5.3 depending on the sequence). Scaling prevents underflow for T=10+ and gives stable log-likelihood for model comparison and learning (e.g., in Baum-Welch).

EasyTechnical

92 practiced

You are given a computed DP table dp[i][j] storing the maximum path sum from the top-left corner to cell (i,j) in an m x n grid where moves allowed are right and down. Describe a step-by-step algorithm to reconstruct one path that achieves dp[m-1][n-1]. Explain how you handle boundaries, ties (multiple optimal paths), and adapt the approach if diagonal moves are also allowed or if obstacles (blocked cells) exist.

Sample Answer

Approach: backtrack from (m-1,n-1) to (0,0) following parent choices implied by dp. At each cell (i,j) choose a predecessor (i-1,j) or (i,j-1) whose dp value plus current cell value equals dp[i][j]. Record moves and reverse at the end.

Pseudo-code (python-like):

python

def reconstruct(dp, grid):
    m, n = len(dp), len(dp[0])
    i, j = m-1, n-1
    path = []
    while True:
        path.append((i,j))
        if i==0 and j==0:
            break
        candidates = []
        if i>0:
            candidates.append(((i-1,j), dp[i-1][j]))
        if j>0:
            candidates.append(((i,j-1), dp[i][j-1]))
        # choose any predecessor that satisfies dp condition
        found = False
        for (pi,pj), val in candidates:
            if val + grid[i][j] == dp[i][j]:
                i, j = pi, pj
                found = True
                break
        if not found:
            raise ValueError("No valid predecessor — input inconsistent")
    return list(reversed(path))

Boundaries: only consider predecessors inside grid (check i>0, j>0). Ties: if multiple predecessors satisfy the equality, choose deterministic rule (prefer up, then left) or collect all to enumerate multiple optimal paths (e.g., DFS branching).

Diagonal moves: allow predecessor (i-1,j-1) and check dp[i-1][j-1] + grid[i][j] == dp[i][j]. Add to candidates.

Obstacles: mark blocked cells (e.g., grid value = -inf or a separate boolean). During reconstruction skip predecessors that are blocked or have dp = -inf. Ensure dp computation used same obstacle rules.

Complexity: O(m+n) for single path; enumerating all optimal paths may be exponential in worst case.

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.