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.

EasyTechnical

65 practiced

Write a DP solution in your preferred language to compute the length of the longest increasing subsequence (LIS) in an array of integers with the straightforward O(n^2) DP. Explain the DP state and recurrence. Also describe why the naive O(n^2) approach can be improved and hint at the n log n approach without implementing it.

Sample Answer

Approach: Use the classic O(n^2) dynamic programming where dp[i] = length of the longest increasing subsequence ending at index i. For each i, scan all j < i and extend any subsequence where arr[j] < arr[i].

python

def length_of_lis(nums):
    """
    O(n^2) DP: dp[i] = length of LIS ending at i
    """
    if not nums:
        return 0
    n = len(nums)
    dp = [1] * n  # each element itself is an LIS of length 1
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

DP state and recurrence:- State: dp[i] = longest increasing subsequence length that ends at i.- Recurrence: dp[i] = 1 + max(dp[j]) over all j < i with nums[j] < nums[i]; if none, dp[i] = 1.

Time/Space:- Time: O(n^2) due to nested loops.- Space: O(n) for dp.

Edge cases:- Empty array -> 0- All equal or decreasing -> 1

Why improve: The inner scan finds the best predecessor; we can speed this by maintaining a structure of minimal tail values for increasing lengths and binary-searching the place for nums[i], reducing time to O(n log n). That approach stores tails[len] = smallest tail value of an increasing subsequence of length len and updates via binary search.

HardTechnical

51 practiced

You need to combine DP with graph shortest path reasoning: find shortest path from source to target where path cost is cost_sum + penalty(max_edge_on_path). Design an algorithm that uses DP over subsets or dynamic states combined with Dijkstra-like relaxation and discuss correctness and complexity trade-offs.

Sample Answer

Approach (high level)- Observation: the penalty depends only on the maximum edge weight along the path. Any optimal path has some max-edge value M that equals one of the edge weights in the graph. So we can convert the problem into: for every candidate M (unique edge weights sorted), compute the cheapest path from s to t that uses only edges of weight ≤ M, then add penalty(M). The global optimum is the minimum over M of (shortest-path-sum-with-edges-≤M + penalty(M)).

Algorithm (enumeration + Dijkstra)1. Collect unique edge weights W = sorted distinct weights.2. For each M in W: - Build or conceptually restrict the graph to edges with weight ≤ M. - Run Dijkstra (edge costs = original cost_sum contribution) from source s to get dist_M[t]. - If t reachable, candidate_cost = dist_M[t] + penalty(M); track min over M.3. Return min candidate cost (or INF if unreachable).

Correctness- Any path P has max edge weight M* equal to some edge weight in W. When we consider M = M*, the restricted graph includes all edges of P, so Dijkstra returns some dist ≤ cost_sum(P). Thus the enumeration will consider the true cost of P. Minimizing over all M therefore finds the optimal path.

Complexity- Let V,E,K (K ≤ E distinct weights). Each Dijkstra is O(E log V) (or O(E+V log V) with Fibonacci heap). Total: O(K * E log V). Space O(V+E).- Trade-offs: - Works well when K is small (few distinct weights). If K ~ E this is E times Dijkstra and can be expensive. - Alternative: augment states to (node, current_max_index) and run one multi-dimensional Dijkstra: states up to V*K, transitions relax to (v, max(i, idx(edge))). Complexity O(V*K log(V*K) + E*K) — often worse but gives single-run solution and can be pruned by ignoring dominated states. - If penalty(M) is monotonic convex/concave, you can prune or apply parametric/binary search on M (if best M is monotone by feasibility) to reduce runs.Edge cases & practical notes- If penalty is arbitrary, enumeration is safe.- Pre-sort weights and reuse adjacency filtering (incrementally add edges as M increases) so you can incrementally update shortest paths or use dynamic shortest-path data structures to amortize work.- If multiple edge metrics (cost and weight) are continuous, consider state-augmentation with pruning by dominance.

HardTechnical

65 practiced

You have an O(n*k) DP that fills dp[i][j] and you must reduce memory to O(k) but still output the full solution path at the end. Describe techniques like checkpointing with recomputation (divide and conquer reconstruction), and implement a plan showing how to reconstruct solution by rerunning DP on segments. Analyze time increase and memory savings.

Sample Answer

Approach summary- Goal: reduce memory from O(n*k) (store full dp table) to O(k) while still outputting the full solution path.- Two practical techniques: checkpointing with recomputation (block checkpoints) and divide-and-conquer reconstruction (Hirschberg-style). Trade-offs: checkpointing gives tunable time/memory trade-off; divide-and-conquer often reduces memory to O(k log n) or O(k) (for some DP shapes) at the cost of extra recomputation (often a logarithmic factor).

1) Checkpointing with recomputation (block checkpoints)Idea:- Partition rows 0..n into blocks of size B.- During forward DP pass, only store full dp rows at block boundaries (checkpoints): rows 0, B, 2B, ...- Memory: O(k * (n/B)) (choose B so this fits).Reconstruction:- To reconstruct path, process blocks from left to right. For block [s..t] of size ≤ B: - Recompute DP starting from checkpoint at s to t, keeping only O(k) memory during recomputation; produce the decisions inside the block and output path piece.- Time overhead: each block recomputed once during reconstruction; total forward work already done once; so total time ≈ O(nk) (initial pass) + O(nk) (recomputations) = O(nk * (1 + 1)) if you plan well. More precisely total time = O(nk * (1 + (n/B)/(n/B))) ≈ O(nk * (1 + 1)) but worst-case each cell may be recomputed a constant number of times. Setting B = sqrt(n) yields memory O(k*sqrt(n)) and time O(2nk). If you want memory O(k), set B = n so you store only endpoints and must recompute large segments many times — time becomes O(n^2 k) (not recommended).

Pseudocode (sketch):- Forward DP: for i in 0..n: compute dp_row (O(k)); if i % B == 0: save copy(dp_row)- Reconstruct: for each block [s..t]: load checkpoint at s recompute rows s+1..t storing decisions append decisions to path

When to use:- When you can afford a moderate number of checkpoints (e.g., memory O(k*sqrt(n))) and want near-linear time.

2) Divide-and-conquer reconstruction (Hirschberg-style)Idea:- Works when the DP recurrence only depends on previous rows (or can be split) and the path can be determined by a “split index” at middle row mid.- Recursively find the split: compute forward DP from start to mid keeping only O(k) memory; compute backward DP from end to mid (on reversed transitions) keeping O(k) memory. For each state j combine forward[j] + backward[j] to pick the best split state j* at mid. Recurse on [start..mid] and [mid..end].Memory and time:- Memory: O(k) per DP vector + recursion stack. Stack depth log n (if balanced), so O(k log n) worst-case; often implement tail recursion to keep O(k).- Time: Each recursion level computes DP over the whole segment length; summing over levels gives additional factor O(log n) in general: total time O(nk log n). For special structures (e.g., LCS) you can achieve O(nk) total time because each element is processed constant times.When to use:- When you need strict small memory (O(k) or O(k log n)) and can tolerate a logarithmic time blow-up, or when DP structure matches Hirschberg so time stays linear.

Example sketch (divide-and-conquer):- function reconstruct(l, r): if r - l == 1: recover base choice directly mid = (l + r) // 2 forward = dp_forward(l..mid) # O((mid-l)*k) time, O(k) memory backward = dp_backward(mid..r) # O((r-mid)*k) time, O(k) memory choose split j* = argmax_j forward[j] + backward[j] reconstruct(l, mid) with target state j* reconstruct(mid, r) with start state j*

Trade-offs and guidance- If you can afford O(k * sqrt(n)) memory, use checkpointing with B = sqrt(n) for simple implementation and near-linear time.- If you must target O(k) memory, use divide-and-conquer; expect extra runtime (commonly O(nk log n)), but it guarantees low memory.- Hybrid: use sparse checkpoints to limit recursion depth or reduce recomputation factor.

Practical notes- Make sure to store enough information in checkpoints to restart recomputation (full dp row + any tie-breaking metadata).- If transitions are local or monotone (divide-and-conquer-friendly), preferring Hirschberg-style yields better memory with bounded time overhead.- Always test on worst-case n to pick B and confirm runtime fits constraints.

HardSystem Design

60 practiced

Design the architecture for an online coding judge service that must evaluate many DP-heavy algorithm submissions concurrently. Address worker isolation, resource limits (CPU, memory), caching of common DP results, timeouts for exponential algorithms, and strategies to detect and mitigate repeated expensive submissions (e.g., same input).

Sample Answer

Requirements:- Functional: accept source + testcases, run and return verdicts (AC/WA/TLE/MLE/RE), support many concurrent DP-heavy submissions.- Non-functional: strong isolation, strict CPU/memory limits, cache reuse of DP sub-results, detect/timeout exponential algorithms, mitigate repeated expensive identical runs, scalable.

High-level architecture:- API Gateway → Submission Service → Scheduler/Queue → Worker Pool (isolated sandboxes) ↔ Shared Cache (Redis + sharded persistent store) → Results DB + Monitoring/Alerting

Key components and choices:1. Worker isolation & resource limits- Run each submission in containers orchestrated by Kubernetes with seccomp/AppArmor, disabled network, ephemeral FS.- Enforce CPU/memory with cgroups/Kubernetes resourceRequests & limits. Use pod-level OOMScoreAdj and CPU quotas.- For strong isolation on untrusted code, offer Firecracker microVMs as optional higher-security workers.- Runtime watchdog process (outside guest) kills workers exceeding wall-time or syscall patterns.

2. Caching common DP results- Two-level cache: - Short-term in-memory Redis cluster keyed by deterministic fingerprint = hash(problemID + normalized code + input + canonical DP state representation). - Long-term deduplicated store (RocksDB/Cloud Storage) for expensive precomputed inputs.- Encourage canonicalization: transform DP state into compact tuple string (e.g., sorted or normalized indices) so equivalent subproblems map to same key.- Workers consult cache before computing; for partial reuse support, expose memoization API where worker can store subproblem results during run (with TTL and size limits).

3. Timeouts & detecting exponential algorithms- Static heuristics pre-check: analyze source for obvious exponential patterns (deep recursion, no memoization, nested loops over n with exponential bounds). Use fast AST-based rules + language-specific heuristics.- Dynamic monitoring: instrument runtime to track number of recursive calls, unique DP state explorations, and growth rate. If growth exceeds threshold (configurable per problem), trigger graceful abort → return TLE or "Probable exponential" verdict.- Progressive timeouts: scale per-submission based on problem difficulty, historical runtimes, and worker load.

4. Mitigating repeated expensive submissions- Deduplication layer in Scheduler: compute submission fingerprint (code + input). If identical submission is currently running or recently completed, return existing result or attach requestor to ongoing run.- Rate-limiting & backoff: per-user and per-IP rate limits; for users repeatedly submitting expensive jobs, enforce longer cooldowns or queue lower priority.- Cost accounting / quotas: per-user daily compute quota; expose premium fast-path.- Result caching with validated TTL: if same input+code seen, return cached verdict; for nondeterministic builds include random seeds in fingerprint.

5. Scalability & operations- Autoscale worker pool based on queue length and historical processing times; separate pools by resource class (small/large memory).- Metrics: per-job CPU/mem, DP state exploration counts, cache hit-rate, dedupe rate. Alert on cache churn or abnormal exponential detections.- Security & correctness: sandbox syscall filtering, filesystem snapshots, reproducible builds, deterministic hashing.

Trade-offs:- Aggressive static rejection risks false positives; mitigate by conservative thresholds and informative messages to users.- Memoization sharing improves throughput but may expose intermediate results; restrict cache keys per problem/visibility and scrub sensitive outputs.

This design balances isolation, strict resource control, DP-specific caching, heuristic + runtime exponential detection, and deduplication to efficiently handle many concurrent DP-heavy submissions.

EasyTechnical

91 practiced

Given a recurrence or DP algorithm, describe a systematic process to derive its time and space complexity. Apply that checklist to a two-dimensional DP that fills dp[i][j] where i ranges to N and j ranges to M and each transition considers up to K candidate j' values. What is the cost and how could it be improved?

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.