Dynamic Programming Questions

Solving problems with overlapping subproblems and optimal substructure via memoization and tabulation. Covers recognizing DP-amenable problems, defining state and transitions, 1D/2D formulations, and space optimization. Widely regarded as the highest-difficulty and highest-discriminating coding-interview topic.

HardTechnical

92 practiced

Many backend DP cost models reduce to dp[i] = min_j (dp[j] + m_j * x_i + b_j). Explain and implement the Convex Hull Trick (CHT) to optimize queries over lines for monotonic x_i. Provide both an amortized O(1) stack/deque-based CHT for monotonic slopes and a Li Chao tree for arbitrary queries; discuss numeric stability, integer vs floating-point trade-offs, and how to integrate CHT into production code.

Sample Answer

Approach (brief) We need to maintain a set of lines y = m*x + b to answer min y at given x_i (monotonic nondecreasing). For monotonic x and monotonic slopes we can use a deque (amortized O(1) per op). For arbitrary insert/query use Li Chao tree (O(log C) per op) over x domain. Deque (monotonic slopes, monotonic x) — C++ cpp// Insert slopes m increasing, query x nondecreasing struct Line { long long m,b; long double eval(long long x) const { return (long double)m*x + b; } }; bool bad(const Line &a,const Line &b,const Line &c){ // intersection(a,b) >= intersection(b,c) ? then b is useless // compare (b.b - a.b)/(a.m - b.m) >= (c.b - b.b)/(b.m - c.m) return (long double)(b.b - a.b)*(b.m - c.m) >= (long double)(c.b - b.b)*(a.m - b.m); } deque<Line> dq; void add(Line L){ while(dq.size()>=2 && bad(dq[dq.size()-2],dq[dq.size()-1],L)) dq.pop_back(); dq.push_back(L); } long double query(long long x){ while(dq.size()>=2 && dq[0].eval(x) >= dq[1].eval(x)) dq.pop_front(); return dq.front().eval(x); } Complexity: O(1) amortized add/query. Li Chao Tree (arbitrary) — C++ cppstruct LiChao { struct Node{ Line line; Node *l,*r; Node(Line ln):line(ln),l(nullptr),r(nullptr){} }; Node* root=nullptr; long long L,R; LiChao(long long L_, long long R_):L(L_),R(R_){} void add_line(Line nw){ insert(root,L,R,nw); } void insert(Node*&node,long long l,long long r, Line nw){ if(!node){ node=new Node(nw); return; } long long m=(l+r)>>1; bool lef = nw.eval(l) < node->line.eval(l); bool mid = nw.eval(m) < node->line.eval(m); if(mid) swap(nw, node->line); if(r-l==0) return; if(lef != mid) insert(node->l, l, m, nw); else insert(node->r, m+1, r, nw); } long double query(long long x){ return query(root,L,R,x); } long double query(Node*node,long long l,long long r,long long x){ if(!node) return 1e30; long double cur=node->line.eval(x); if(l==r) return cur; long long m=(l+r)>>1; if(x<=m) return min(cur, query(node->l,l,m,x)); else return min(cur, query(node->r,m+1,r,x)); } }; Complexity: O(log range) per op. Numeric stability & integer vs float Use 128-bit or integer cross-multiplication when comparing intersections to avoid floating errors. In deque bad() we used long double for simplicity; prefer __int128 comparisons for strict correctness. For Li Chao with integer domain use integer arithmetic to compare values (avoid long double). Be careful with overflow: use 64-bit for m,b,x leading to 128-bit intermediates. Production integration Encapsulate as a tested library with clear API. Validate domain bounds for Li Chao. Add unit tests (randomized), fuzzing for corner cases (equal slopes, identical lines), and benchmarks. Expose both integer and floating variants; choose integer version when inputs are integral. Add logging and metrics (qps, latency). Consider memory bounds for Li Chao; use iterative pool allocator for high-throughput backends. This covers both practical implementations, complexity, numeric trade-offs, and production guidance.

MediumTechnical

93 practiced

As a backend developer deciding which endpoints to pre-warm under a fixed budget K, endpoints i have warm cost c_i and expected saved latency v_i. Implement a Java function that selects endpoints to maximize total saved latency subject to total cost \leq K (0/1 knapsack). Return the selected indices. Discuss time/space trade-offs and approximation/scale strategies for very large K or many endpoints.

Sample Answer

Approach (brief) Use classic 0/1 knapsack dynamic programming to maximize saved latency subject to warm-cost ≤ K. Build DP table dp[w] = max value for cost w and keep parent pointers (or reconstruct by iterating backwards) to return selected indices. For large K or many endpoints discuss space/time trade-offs and approximation methods. Java implementation javaimport java.util.*; public class PrewarmSelector { // returns list of selected indices (0-based) public static List<Integer> select(int[] c, int[] v, int K) { int n = c.length; // dp[w] = max value achievable with cost w int[] dp = new int[K+1]; // parent[i][w] isn't stored fully to save memory; store choice index for reconstruction int[][] take = new int[n+1][K+1]; // take[i][w]=1 if we took item i-1 to reach dp state at i for (int i = 1; i <= n; i++) { int cost = c[i-1], val = v[i-1]; for (int w = K; w >= 0; w--) { int without = dp[w]; int with = (w >= cost) ? dp[w-cost] + val : Integer.MIN_VALUE; if (with > without) { dp[w] = with; take[i][w] = 1; } else { take[i][w] = 0; } } } // reconstruct List<Integer> res = new ArrayList<>(); int w = K; for (int i = n; i >= 1; i--) { if (take[i][w] == 1) { res.add(i-1); w -= c[i-1]; } } Collections.reverse(res); return res; } } Complexity Time: O(n * K) Space: O(n * K) for full reconstruction; can reduce to O(K) for values only. Edge cases K = 0, empty arrays, costs > K, negative/zero values (validate input). Scaling / approximation strategies If K large: use DP on total value (value-scaling) or compress costs (divide by gcd). For huge n: use FPTAS — scale values by factor and run DP on scaled values to get (1+ε) approximation. Greedy (value/cost ratio) is fast but only optimal for fractional knapsack; can be used as heuristic. Meet-in-the-middle for n ≤ 40. Streaming/online: sketching, reservoir sampling, or periodically recompute top candidates using estimators. Practical backend tip: prefilter endpoints by minimal ratio or threshold, batch warm operations, and monitor warm benefits to refine models.

MediumTechnical

67 practiced

Given a chain of matrices with dimensions p0, p1, ..., pn, implement a Python function that computes the minimum number of scalar multiplications needed to multiply the chain (matrix chain multiplication) and output the optimal parenthesization. Your solution should use DP and handle n up to ~200. Discuss the time/space complexity and mention any optimizations or heuristics you'd consider for larger n in a production system.

Sample Answer

Approach (brief) Use classical dynamic programming: dp[i][j] = min cost to multiply Ai..Aj and split[i][j] stores k giving the optimal split. Build increasing chain lengths (bottom-up) and reconstruct parenthesization. Python implementation pythondef matrix_chain_order(p): # p: list of dimensions length n+1 for matrices A1..An where Ai is p[i-1] x p[i] n = len(p) - 1 # dp[i][j]: min cost for Ai..Aj (1-based indices). use 0..n-1 for arrays dp = [[0]*n for _ in range(n)] split = [[-1]*n for _ in range(n)] for L in range(2, n+1): # chain length for i in range(0, n-L+1): j = i + L - 1 dp[i][j] = float('inf') for k in range(i, j): cost = dp[i][k] + dp[k+1][j] + p[i]*p[k+1]*p[j+1] if cost < dp[i][j]: dp[i][j] = cost split[i][j] = k def build(i, j): if i == j: return f"A{i+1}" k = split[i][j] return f"({build(i,k)} x {build(k+1,j)})" if n == 0: return 0, "" return dp[0][n-1], build(0, n-1) Complexity Time: O(n^3) (triple loop). For n ≈ 200 this is ~8e6 inner iterations—practical in optimized Python but might be slow depending on constant factors. Space: O(n^2) for dp and split. Optimizations & production considerations Use PyPy or C/Cython to speed heavy loops; vectorize inner loops in C. Memoized recursive DP avoids some work for sparse queries but same worst-case. Heuristics: greedy or hill-climbing for very large n when exact O(n^3) is too costly. Advanced techniques: exploit associativity with problem-specific structure, parallelize evaluation of independent subproblems, or apply approximations (e.g., randomized sampling). Cache-friendly ordering and small-block tiling improve real runtime.

HardTechnical

72 practiced

Given a tree representing microservices, placing a monitor on a service covers itself and direct neighbors. Implement an efficient tree DP in Java to compute the minimum number of monitors needed to cover every node. Use states like: placed, covered-without-placed, and uncovered; traverse with DFS and compute states bottom-up. Explain correctness and how to output the chosen monitor nodes.

Sample Answer

Approach (brief) Use tree DP with three states per node: 0 = placed (has monitor), 1 = covered (no monitor, but covered by child), 2 = uncovered (not covered). Do a DFS from root computing dp[node][state] = min monitors in subtree. Use parent to avoid revisiting. Track choices for reconstruction to output monitor nodes. Key idea / correctness Every node must be covered by itself or neighbor. States exhaustively encode possibilities; transitions enforce coverage constraints and combine optimal child states. This is standard tree-vertex-cover-like DP and is correct by induction: optimal choices for children yield optimal for parent. Java implementation (DP + reconstruction) javaimport java.util.*; public class Monitors { List<Integer>[] g; int n; int[][] dp; int[][] choice; // child decisions encoded during compute List<Integer> monitors = new ArrayList<>(); public Monitors(int n){ this.n=n; g=new ArrayList[n]; for(int i=0;i<n;i++) g[i]=new ArrayList<>(); dp=new int[n][3]; choice=new int[n][3]; for(int i=0;i<n;i++) Arrays.fill(dp[i], Integer.MAX_VALUE/4); } public void addEdge(int u,int v){ g[u].add(v); g[v].add(u); } public int solve(){ dfs(0,-1); int best = Math.min(dp[0][0], Math.min(dp[0][1], dp[0][2])); reconstruct(0,-1, dp[0][0]<=dp[0][1] && dp[0][0]<=dp[0][2] ? 0 : dp[0][1]<=dp[0][2] ? 1 : 2); return best; } void dfs(int u,int p){ dp[u][0]=1; // place here dp[u][2]=0; // uncovered if children ensure no coverage dp[u][1]=0; // covered by some child for(int v: g[u]) if(v!=p){ dfs(v,u); // if u placed, child can be any state -> take min dp[u][0]+= Math.min(dp[v][0], Math.min(dp[v][1], dp[v][2])); // if u uncovered, children must be covered-with-placed to cover themselves? actually uncovered means u is not covered; children cannot place coverage for u -> children must be covered (state 1) dp[u][2]+= dp[v][1]; } // compute dp[u][1]: at least one child placed int sumAsIfNoPlaced=0; for(int v: g[u]) if(v!=p) sumAsIfNoPlaced += Math.min(dp[v][0], Math.min(dp[v][1], dp[v][2])); // we need to force at least one child to be state 0 (placed) int best = Integer.MAX_VALUE/4; for(int v: g[u]) if(v!=p){ int cost = sumAsIfNoPlaced - Math.min(dp[v][0], Math.min(dp[v][1], dp[v][2])) + dp[v][0]; best = Math.min(best, cost); } if(best==Integer.MAX_VALUE/4) dp[u][1]=Integer.MAX_VALUE/4; else dp[u][1]=best; } void reconstruct(int u,int p,int state){ if(state==0) monitors.add(u); for(int v: g[u]) if(v!=p){ int pick; if(state==0){ // child can take any minimal state int a=dp[v][0], b=dp[v][1], c=dp[v][2]; pick = a<=b && a<=c ? 0 : (b<=c?1:2); } else if(state==2){ pick = 1; // children must be covered-without-placed } else { // state==1 parent covered by some child -> pick child states minimizing overall but ensure at least one child is 0 // greedily pick minimal; if no child 0 chosen globally, force one with minimal extra cost to 0 pick = dp[v][0]<=dp[v][1] && dp[v][0]<=dp[v][2] ? 0 : (dp[v][1]<=dp[v][2]?1:2); } reconstruct(v,u,pick); } } } Edge cases & complexity Handles single node, chains, stars. Time O(n). Space O(n). Use root choice compare of dp[0] states. For production, add null checks and deterministic tie-breaking.

MediumTechnical

87 practiced

Write a Python function that counts the number of ways to make amount M using given coin denominations where the order of coins does not matter. Return the result modulo 1,000,000,007. Constraints: number of denominations n <= 100, M <= 10,000. Explain the bottom-up DP approach using a 1D array and how you avoid counting the same combination multiple times.

Sample Answer

Approach (brief) Use bottom-up dynamic programming with a 1D array dp[x] = number of ways to form amount x. Iterate coins in the outer loop and amounts increasing in the inner loop so each coin is considered once per amount — this guarantees combinations (not permutations) are counted. Python implementation python MOD = 10**9 + 7 def count_combinations(coins, M): # dp[x] = ways to make x dp = [0] * (M + 1) dp[0] = 1 # one way to make 0: choose nothing for coin in coins: # each coin considered once (combination-oriented) for amt in range(coin, M+1): # increasing order to reuse current coin unlimited times dp[amt] = (dp[amt] + dp[amt - coin]) % MOD return dp[M] Why this avoids duplicates Outer loop over coins fixes an ordering; we only add ways that include current coin after considering previous coins. This prevents counting the same multiset in different orders. Complexity Time: O(n * M) where n = len(coins) Space: O(M) Edge cases M = 0 -> return 1 coins containing values > M are skipped by loop Use modulo to avoid overflow and match problem requirement This is efficient and suitable for backend tasks where constraints are n \leq 100 and M \leq 10,000.

Unlock Full Question Bank

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

Join thousands of developers preparing for their dream job.