Algorithm Design and Dynamic Programming Questions

Comprehensive topic covering algorithm design with a strong emphasis on dynamic programming across beginner to advanced levels. Candidates should be able to recognize overlapping subproblems and optimal substructure, define states and derive recurrence relations, and implement correct top down memoization or bottom up tabulation. Core problem types include Fibonacci and climbing stairs for basics, coin change and basic knapsack, intermediate patterns such as longest increasing subsequence, longest common subsequence, edit distance, and matrix chain multiplication, and advanced domains including bitmask dynamic programming, dynamic programming on trees, digit dynamic programming, game theoretic dynamic programming, and multi dimensional state spaces. Evaluation includes space and time optimization techniques such as rolling arrays, state compression, reducing dimensionality, and other algorithmic optimizations including divide and conquer optimization, monotone queue optimization, and convex hull trick when applicable. Candidates are expected to refactor brute force solutions into efficient dynamic programming implementations, reason about correctness and complexity, discuss trade offs between clarity and performance, and leverage related algorithmic building blocks such as binary search, common sorting algorithms, greedy strategies, and appropriate data structures to improve solutions.

MediumTechnical

72 practiced

Implement Longest Increasing Subsequence (LIS) length in Python with O(n log n) time using patience sorting / tails array and explain how it works. Also describe how to reconstruct one LIS sequence in O(n log n) or O(n) extra memory. Discuss behavior with duplicates and strict vs non-strict LIS.

Sample Answer

Approach: use patience-sorting tails array where tails[len] = smallest tail value of an increasing subsequence of length len+1. For each x, binary-search in tails to find position to replace/append. Length = size of tails. To reconstruct one LIS, keep predecessor indices and index-of-tail for each length; when you place x at position pos, record prev[i] = index_of_tail[pos-1]. At the end backtrack from index_of_tail[last_len-1].

python

from bisect import bisect_left

def lis_with_reconstruction(arr, strict=True):
    """
    Returns (length, one_LIS_list)
    strict=True => strictly increasing (use bisect_left)
    strict=False => non-decreasing (use bisect_right)
    O(n log n) time, O(n) extra memory for reconstruction.
    """
    if not arr:
        return 0, []
    n = len(arr)
    tails = []                 # values for binary search
    tail_idx = []              # indices in arr corresponding to tails
    prev = [-1]*n              # predecessor indices for reconstruction

    bisect_fn = bisect_left if strict else __import__('bisect').bisect_right

    for i, x in enumerate(arr):
        pos = bisect_fn(tails, x)
        if pos == len(tails):
            tails.append(x)
            tail_idx.append(i)
        else:
            tails[pos] = x
            tail_idx[pos] = i
        if pos > 0:
            prev[i] = tail_idx[pos-1]

    # reconstruct
    lis_len = len(tails)
    res = []
    k = tail_idx[-1] if lis_len>0 else -1
    # find actual last index: tail_idx[lis_len-1]
    k = tail_idx[lis_len-1]
    while k != -1:
        res.append(arr[k])
        k = prev[k]
    res.reverse()
    return lis_len, res

Key points:- Time: O(n log n) due to binary searches. Space: O(n).- Reconstruction uses predecessor links and indices of tails to rebuild in O(n).- Duplicates: choice of bisect_left (strict) avoids equal values extending sequence; bisect_right allows equals (non-strict). Pick per problem requirement.

HardTechnical

56 practiced

Some DP transitions are convolution-like: dp[i] = sum_j dp[j] * w[i-j] or dp[i] = min_j dp[j] + w[i-j]. Explain when you can accelerate using FFT/NTT for sum-convolutions (polynomial multiplication) and discuss why min-plus convolution is harder. Provide algorithms and complexity trade-offs for both cases and an example application (bounded knapsack via generating functions).

Sample Answer

Short answer: Sum-convolutions dp[i] = sum_j dp[j] * w[i-j] are exactly polynomial (or discrete) convolutions and can be accelerated by FFT/NTT (or any fast multiplicative convolution). Min-plus convolution dp[i] = min_j (dp[j] + w[i-j]) is in the tropical semiring and cannot be reduced to FFT/NTT directly; it’s fundamentally harder and needs different techniques (divide-and-conquer optimizations, monotone queues, or structure-specific transforms).

When FFT/NTT applies (sum-convolution)- Requirement: operation is sum over products (standard ring). You can view arrays A[j]=dp[j], B[k]=w[k] and compute C = A * B by polynomial multiplication: C[i] = sum_j A[j] * B[i-j].- Algorithms: Cooley–Tukey FFT over reals/complex (O(n log n)), or NTT on a suitable modulus (exact integer arithmetic, avoids precision issues).- Complexity: For length n, convolution via FFT/NTT is O(n log n) time and O(n) memory. Naive is O(n^2).- Practical notes: use NTT for integer counts modulo a prime (e.g., 998244353). For arbitrary integers, use multiple NTTs + CRT or careful double-precision FFT with rounding.

Why min-plus is harder- FFT relies on distributivity of multiplication over addition in a ring. Min-plus replaces + with min and * with +; this “semiring” lacks inverses and the transform that diagonalizes convolution (DFT) isn’t applicable.- There’s no direct analogue of FFT for (min,+). Known reductions: min-plus convolution general-case is equivalent in difficulty to all-pairs shortest paths (APSP) in some settings; best general algorithms are near O(n^2) with polylog improvements.

Algorithms / trade-offs for min-plus- If w has structure (convex, monotone): use divide-and-conquer DP optimization (Aliens/Knuth/Divide & Conquer) or monotone queue yielding O(n log n) or O(n). - Example: if argmins obey monotonicity (quadrangle inequality), divide-and-conquer gives O(n log n).- For small integer weights W: encode integers in unary and use FFT on bitsets (convolution of characteristic polynomials) — complexity becomes O(nW log(nW)), useful when W small.- Practical general-purpose algorithms: All-pairs shortest path reductions / bitset tricks; typical complexity remains ~O(n^2) for unconstrained inputs.

Example application — bounded knapsack via generating functions (sum-convolution)- Problem: count ways to reach capacity S using items with bounded multiplicities.- Model: for each item with weight w and count c, polynomial P_item(x) = 1 + x^w + x^{2w} + ... + x^{c w} = (1 - x^{(c+1)w})/(1-x^w). The total generating function is product of P_item(x); coefficient of x^S is the answer.- Algorithm: multiply polynomials using divide-and-conquer convolution with FFT/NTT. Use polynomial truncation to degree S at each step to keep sizes small.- Complexity: naive multiplication would be heavy; using FFT/NTT and truncation yields roughly O(S log S log m) where m is number of items (multiplying m polynomials by pairwise merging). Using NTT modulo prime gives exact counts modulo that prime; use CRT if multiple moduli needed.

Takeaway- Use FFT/NTT whenever your DP is a standard sum-of-products convolution or when you can encode combinatorial counts as polynomial multiplication (generating functions). For min-plus, look for problem-specific structure (convexity, monotonicity, small weights) to apply faster methods; otherwise expect near-quadratic cost.

HardTechnical

70 practiced

Design an algorithm for the 2D knapsack (items have weight, volume and value) with capacities W and V, using DP over two dimensions. Describe O(n * W * V) solution, memory implications, and optimization techniques: compress one dimension, sparse/dictionary DP for sparse reachable states, and Lagrangian relaxation to convert to single-dimension DP. Discuss approximation strategies when exact DP is infeasible.

Sample Answer

Approach (O(n * W * V) DP)- Use dp[w][v] = max value reachable with weight ≤ w and volume ≤ v. Initialize dp[0..W][0..V] = -inf, dp[0][0]=0. For each item i (weight wi, volume vi, value ci) iterate w from W..wi and v from V..vi: dp[w][v] = max(dp[w][v], dp[w-wi][v-vi] + ci). Final answer = max_{w≤W,v≤V} dp[w][v].Memory & time- Time O(n*W*V). Memory O(W*V) for full table; can be large if W,V ~ 10^4 (10^8 states).

Optimizations1) Compress one dimension- Use 2D→1D: treat volume as inner dimension or weight as inner. Keep dp[w][v] but iterate w descending and update v descending; still requires W*V memory but reduces temporary storage. If one capacity is small (e.g., V small), loop order reduces constant factors.

2) Sparse / dictionary DP- Represent reachable states as hashmap: map[(w,v)] -> value. For each item, for each existing (w,v) produce (w+wi,v+vi) capped by capacities and keep best value. Prune dominated states: if state A has ≤ weight, ≤ volume and ≥ value than B, drop B. This works well when reachable state count << W*V.

3) Lagrangian relaxation → single-dim DP- Move one constraint into objective: maximize value - λ * volume, then run 1D knapsack on weight: dp[w] = best modified value. For a fixed λ, compute best solution; adjust λ via binary search (or parametric search) to meet volume constraint, recovering near-feasible solutions. This converts to O(n*W) per λ and is effective when one capacity is large.

Approximation strategies- FPTAS on value: scale/round values to bound DP size: treat value as dimension and run DP over total scaled value to meet capacities; yields (1+ε)-approximation in poly(n,1/ε).- Greedy heuristics: multi-criteria ranking (value per weighted sum α*w+β*v) with local search or knapsack relaxations.- Randomized rounding: solve LP relaxation of integer program, then round with volume/weight repair heuristics.When exact DP infeasible, prefer sparse DP or Lagrangian + rounding; use pruning (dominance, bounding) and profile empirical reachable states.

MediumTechnical

50 practiced

Implement global sequence alignment (Needleman-Wunsch) in Python: given two sequences and a scoring scheme (match +1, mismatch -1, gap -1), compute the optimal alignment score and produce one optimal alignment. Explain the DP table, initialization, and backtracking procedure. Discuss affine gap penalties briefly and how they change the DP.

Sample Answer

To implement Needleman–Wunsch (global alignment) we use dynamic programming: fill an (m+1)x(n+1) score matrix where dp[i][j] = best score aligning seqA[:i] and seqB[:j]. Initialize first row/column with cumulative gap penalties. Fill by taking max of match/mismatch (diag), gap in A (up), gap in B (left). Backtrack from dp[m][n] to build one optimal alignment.

python

def needleman_wunsch(a, b, match=1, mismatch=-1, gap=-1):
    m, n = len(a), len(b)
    dp = [[0]*(n+1) for _ in range(m+1)]
    # Initialization: cumulative gaps
    for i in range(1, m+1): dp[i][0] = dp[i-1][0] + gap
    for j in range(1, n+1): dp[0][j] = dp[0][j-1] + gap
    # Fill
    for i in range(1, m+1):
        for j in range(1, n+1):
            score_diag = dp[i-1][j-1] + (match if a[i-1]==b[j-1] else mismatch)
            score_up   = dp[i-1][j] + gap
            score_left = dp[i][j-1] + gap
            dp[i][j] = max(score_diag, score_up, score_left)
    # Backtrack to produce one optimal alignment
    i, j = m, n
    A_align, B_align = [], []
    while i>0 or j>0:
        if i>0 and j>0 and dp[i][j] == dp[i-1][j-1] + (match if a[i-1]==b[j-1] else mismatch):
            A_align.append(a[i-1]); B_align.append(b[j-1]); i -= 1; j -= 1
        elif i>0 and dp[i][j] == dp[i-1][j] + gap:
            A_align.append(a[i-1]); B_align.append('-'); i -= 1
        else:
            A_align.append('-'); B_align.append(b[j-1]); j -= 1
    return dp[m][n], ''.join(reversed(A_align)), ''.join(reversed(B_align))

Key points:- DP table: rows = prefixes of a, cols = prefixes of b; dp[i][j] stores optimal score.- Initialization: dp[i][0]=i*gap, dp[0][j]=j*gap ensures global alignment uses end-to-end gaps.- Backtracking: prefer diagonal when consistent; ties produce any optimal alignment.

Complexity: O(m*n) time and O(m*n) space. Can reduce space for score only, but need full table to backtrack (or record pointers).

Affine gap penalties: replace single gap cost with gap open + gap extend (e.g., open=-2, extend=-1). This requires three matrices (M for matches/mismatches, Ix for gaps in x, Iy for gaps in y) and transitions accounting for opening vs extending gaps; complexity remains O(m*n) but constants increase and backtracking uses the three-matrix states.

HardTechnical

67 practiced

Explain Sprague-Grundy theorem and design a DP to compute Grundy numbers (mex values) for impartial combinatorial games represented as a DAG of states (given adjacency lists). Provide an algorithm to compute Grundy[state] using topological order, describe complexity, and show an example.

Sample Answer

Sprague–Grundy theorem (brief): any impartial finite game under normal play is equivalent to a Nim heap of size g, where g is the position’s Grundy number (or nimber). The Grundy number of a position = mex({Grundy(child) for each legal move to child}). The XOR of Grundy numbers of independent subgames determines winning/losing (0 = losing).

Algorithm (DAG adjacency lists): compute Grundy for every node by processing nodes in reverse topological order (children before parents).

1. Topologically sort the DAG.2. Initialize Grundy[v] = -1 for all v.3. Process nodes in reverse topo order: - S = {Grundy[u] for u in adj[v]} (children) - Grundy[v] = mex(S) (smallest nonnegative integer not in S)

Python sketch:

python

def mex(s):
    i=0
    while i in s: i+=1
    return i

def compute_grundy(adj):
    topo = topological_sort(adj)
    grundy = {}
    for v in reversed(topo):
        child_vals = {grundy[u] for u in adj[v]}
        grundy[v] = mex(child_vals)
    return grundy

Complexity:- Let n = |V|, m = total edges. Topological sort O(n+m).- For each node v, computing mex naively costs O(deg(v)+M) where M is resulting mex value. Total time O(n + m + sum M). Using boolean array sized up to max possible grundy (<= deg(v) often small) gives overall O(n + m + sum_deg_bound) ≈ O(n + m + Gmax), practical O(n + m + n) = O(n + m).- Space O(n + m + Gmax).

Example:DAG: 0→1, 0→2, 1→3, 2→3, 3→ (terminal)Process 3: adj[3]=[] → Grundy[3]=mex({})=01: adj[1]={3} → mex({0})=12: adj[2]={3} → mex({0})=10: adj[0]={1,2} → mex({1,1})=0So Grundy = {3:0,1:1,2:1,0:0}. Root 0 is losing (0), while positions 1 and 2 are winning.

Notes/optimizations:- Use boolean marker array and timestamping to compute mex in O(deg(v)) per node.- If graph decomposes into independent components, XOR their Grundy numbers for game outcome.

Unlock Full Question Bank

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

Join thousands of developers preparing for their dream job.