Recursion and Dynamic Programming Questions

Covers recursive problem solving and dynamic programming as core algorithmic techniques. For recursion, understand how functions call themselves, base and recursive cases, the call stack, common patterns such as tree and graph traversals, backtracking, permutations, and detecting and avoiding infinite recursion. For dynamic programming, understand when to apply optimization via memoization and bottom up approaches, recognize optimal substructure and overlapping subproblems, convert naive recursive solutions into memoized or tabulated solutions, and analyze time and space complexity tradeoffs. Familiarity with classic examples such as Fibonacci, longest common subsequence, knapsack, coin change, and path counting is expected. At more senior levels, be able to discuss performance considerations, space optimization, and how DP principles can map onto real systems such as caching strategies, state management, and optimization of workflows or database query plans.

EasyTechnical

68 practiced

When using recursion to traverse a graph (DFS), it's important to avoid infinite recursion due to cycles. Implement a recursive DFS in Python that detects and avoids cycles; given a directed graph represented as adjacency list, return True if there's a path between two nodes. Describe how a visited set or recursion stack differs and when to use each.

Sample Answer

To find whether there's a path from source to target in a directed graph using recursive DFS while avoiding infinite recursion from cycles, we track nodes we've already visited. For reachability a single visited set suffices; for detecting cycles (e.g., in directed graph cycle detection) we also use a recursion stack.

python

def has_path_dfs(graph, src, dst):
    """
    graph: dict[node] -> list[neighbor]
    returns True if there's a path from src to dst
    """
    visited = set()

    def dfs(u):
        if u == dst:
            return True
        if u in visited:
            return False
        visited.add(u)
        for v in graph.get(u, []):
            if dfs(v):
                return True
        return False

    return dfs(src)

# Example:
# g = {'A': ['B','C'], 'B': ['C'], 'C': ['A'], 'D': []}
# has_path_dfs(g, 'A', 'D') -> False
# has_path_dfs(g, 'A', 'C') -> True

Key points:- visited prevents revisiting nodes already explored in any previous branch, avoiding infinite recursion from cycles and improving efficiency.- A recursion stack (set of nodes currently on the call path) is different: use it when you need to detect back-edges / report existence of cycles in directed graphs. If dfs finds a neighbor in the recursion stack, that's a back-edge -> cycle.- Use visited for reachability; use recursion stack in addition when you must detect cycles or produce topological order (to detect invalid DAGs).

Complexity:- Time: O(V + E) — each node and edge processed once.- Space: O(V) for visited plus recursion depth (O(V) worst-case).

Edge cases:- src or dst not in graph (treat missing nodes as having no outgoing edges)- large depth may hit Python recursion limit — consider iterative DFS for very deep graphs.

HardTechnical

73 practiced

Given a grid where each cell has a non-negative cost that may change over time, design an algorithm to compute the minimum-cost path from top-left to bottom-right if costs are updated in small batches between queries. Discuss DP approaches plus efficient incremental update techniques (e.g., dynamic shortest path, Dijkstra variants) and when to recompute from scratch versus incremental updates.

Sample Answer

Clarify assumptions- Grid of size M×N, non-negative cell costs. Allowed moves: 4-neighbor (or specify 8). Goal: shortest path cost from (0,0) to (M−1,N−1).- Costs change in small batches between queries; want to answer many shortest-path queries efficiently.

Baseline / DP for static grid- If moves allowed only right/down, classic DP works: dp[i][j] = cost[i][j] + min(dp[i−1][j], dp[i][j−1]) in O(MN).- For general four-way moves, model grid as weighted directed graph and run Dijkstra from source: O(MN log(MN)) with binary heap (or O(MN) with radix heap if integer costs).

Incremental / dynamic update approaches1) Maintain full shortest-path structure - Keep distance array dist[u], and predecessor parent[u] for nodes on current shortest-path DAG. - Also maintain a PQ for incremental repairs.

2) Handling a batch of updates (cells whose cost changed): Preprocess: treat a cell cost change as edge-weight changes on incident edges. a) Decrease in cost (one or more cells): - Decreasing weights can only improve distances. For each updated node u, compute new tentative distance via neighbors: new_d = min(dist[v] + w(v→u)) over v. - If new_d < dist[u], set dist[u]=new_d and push u into PQ. - Run Dijkstra-like relaxation from these seeds to propagate improvements. Complexity proportional to number of relaxed nodes E' log V. b) Increase in cost: - Increases are harder: some nodes whose shortest path used the increased edge become invalid (their dist must increase). - Mark nodes whose parent chain includes changed edges (walk forward from changed nodes along the shortest-path DAG) — these distances are potentially invalid. For each invalidated node, set dist[node]=+∞ (or recompute) and push its neighbors that could re-reach it into a PQ seeded either from source or from boundary nodes whose distances are unchanged. - A practical technique: run multi-source Dijkstra from all nodes with unchanged distances adjacent to invalidated region to recompute distances inside the affected subgraph. - Alternatively, invert graph and run a BFS from target over predecessors to identify affected region quickly.

3) Practical algorithm (batch procedure) - Input batch B of changed cells. - Classify updates into decreases and increases. - For decreases: seed PQ with changed nodes where new dist < old dist; run relaxations (Dijkstra) until PQ empty. - For increases: find affected set A by traversing the shortest-path DAG forward from any changed edge/node. For nodes in A set dist=∞. Then seed PQ with neighbors of A that have finite dist and run Dijkstra to recompute distances into A. If A is large (> α·MN, α e.g. 0.2), full recompute from scratch with Dijkstra is simpler and often faster.

When to recompute from scratch- If batch size is large or significantly reshapes the shortest-path DAG (many increases), incremental repair overhead can approach a full Dijkstra. Use a heuristic: if |affected_nodes| > threshold (e.g., 10–30% of grid) or number of edges touched > threshold, run full Dijkstra. Also if many alternating increase/decrease patterns cause repeated churn, periodic full recompute is simpler.

Optimizations and variants- Use A* instead of Dijkstra when admissible heuristic (Manhattan) exists to speed single-query runs.- Use hierarchical grids / multi-resolution graphs for very large maps.- For integer non-negative costs, use radix heap for near-linear performance.- Parallelism: process independent regions in parallel; GPU-friendly approaches exist for grid DP-style or bucket-based relaxations.- Maintain compact representation of shortest-path DAG to rapidly identify affected nodes on increases.

Complexity notes- Full Dijkstra: O(MN log(MN)) time, O(MN) memory.- Incremental decreases: proportional to number of nodes whose dist decreases plus relaxations, typically much less than full recompute for small batches.- Incremental increases: cost is size of affected region traversal + recompute inside it — worst case O(MN log(MN)), average much better.

Recommendation for ML-engineer context- If updates are sparse and mostly decreases (model confidence improvements / cost reductions), incremental Dijkstra repairs give big savings.- If updates include many increases or are unpredictable, set a threshold to fall back to full recompute for simplicity and stability.- Instrument metrics: track affected-region size and time per update; auto-tune recompute threshold.- If shortest-path results feed downstream models or routing services, ensure versioning and consistent atomic swaps of distance arrays to avoid serving transient inconsistent states.

MediumTechnical

86 practiced

You are given a top-down recursive DP pseudocode (e.g., for LCS or knapsack). Explain how to convert it into a bottom-up tabulation approach. Walk through the conversion using the LCS recursive formulation as the example and discuss ordering of loops and initialization of base cases.

Sample Answer

Start by identifying the recursive structure: state parameters, recurrence, and base cases. For LCS the top-down recursion is:

- State: f(i,j) = LCS length of A[i:] and B[j:]- Recurrence: - if i==len(A) or j==len(B): return 0 (base) - if A[i]==B[j]: return 1 + f(i+1,j+1) - else: return max(f(i+1,j), f(i,j+1))

To convert to bottom-up (tabulation):1. Choose table indices that represent the state (i, j). Here make dp sized (n+1)x(m+1) where dp[i][j] = LCS length of A[i:] and B[j:] or alternatively of prefixes A[:i],B[:j] — pick one consistently.2. Initialize base cases explicitly: for suffix-based dp, set last row and last column to 0 (i==n or j==m).3. Determine fill order so dependencies are computed before use. For suffix formulation dp[i][j] depends on dp[i+1][j+1], dp[i+1][j], dp[i][j+1] — so iterate i from n-1 down to 0 and j from m-1 down to 0.4. Translate recurrence into loop body.

Example (suffix-based) in Python:

python

def lcs_length(A, B):
    n, m = len(A), len(B)
    dp = [[0]*(m+1) for _ in range(n+1)]  # base: dp[n][*]=dp[*][m]=0
    for i in range(n-1, -1, -1):
        for j in range(m-1, -1, -1):
            if A[i] == B[j]:
                dp[i][j] = 1 + dp[i+1][j+1]
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j+1])
    return dp[0][0]

Key reasoning:- Table shape and initialization come directly from base cases of recursion.- Loop order follows dependency graph: compute states that recursion would reach deeper first.Complexity: O(n*m) time and O(n*m) space. You can reduce space to O(min(n,m)) by rolling arrays if only lengths are needed. Edge cases: empty strings, very imbalanced lengths (choose smaller dimension for rolling).

MediumTechnical

96 practiced

Tree DP: Implement the 'House Robber III' problem where thieves cannot rob two directly-linked houses (a binary tree). Return the maximum amount that can be robbed. Use recursion with memoization and explain your state definition and transitions in terms of including/excluding root.

Sample Answer

Approach: Define DP state as two values per node: (rob, not_rob). rob = max money when we rob this node (so children cannot be robbed). not_rob = max money when we don't rob this node (children may be robbed or not). Use recursion with memoization (cache results per node) and compute transitions bottom-up.

python

# python
from functools import lru_cache

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rob(root: TreeNode) -> int:
    @lru_cache(maxsize=None)
    def dfs(node):
        if node is None:
            return (0, 0)  # (rob, not_rob)
        left_rob, left_not = dfs(node.left)
        right_rob, right_not = dfs(node.right)

        # If we rob this node, cannot rob children
        rob_here = node.val + left_not + right_not
        # If we don't rob this node, children choose max of rob/not
        not_rob_here = max(left_rob, left_not) + max(right_rob, right_not)
        return (rob_here, not_rob_here)

    return max(dfs(root))

Key points:- State: (rob, not_rob) per node captures include/exclude.- Transition: rob = node.val + left.not_rob + right.not_rob; not_rob = sum(max(child.rob, child.not_rob)).Time: O(n) — each node visited once (memoized). Space: O(n) recursion + cache. Edge cases: empty tree (0), single node (node.val), skewed tree (depth n) — watch recursion depth. Alternative: iterative post-order traversal or explicit stack to avoid recursion limits.

HardTechnical

95 practiced

Solve the Traveling Salesman Problem for n ≤ 20 using bitmask dynamic programming: implement a solution in Python that returns the minimum tour length given a full distance matrix. Explain the O(n^2 * 2^n) complexity and memory usage, and discuss pruning or heuristics you might use to handle n slightly larger than 20 in practice.

Sample Answer

Approach: use Held–Karp bitmask DP. DP[mask][i] = minimum cost to start at node 0, visit nodes in mask (mask includes node 0 and i), and finish at i. Build states by increasing masks and finally add cost to return to 0.

python

import math
def tsp_held_karp(dist):
    """
    dist: n x n full distance matrix (dist[i][j] >= 0)
    returns minimum tour length (cycle starting and ending at 0 visiting all nodes)
    """
    n = len(dist)
    if n == 0:
        return 0
    N = 1 << n
    INF = float('inf')
    # DP: array of size N x n, initialized to INF
    dp = [[INF] * n for _ in range(N)]
    dp[1][0] = 0  # mask with only node 0 visited, at node 0 cost 0

    for mask in range(1, N):
        if not (mask & 1):  # require start node 0 to be in mask
            continue
        for u in range(n):
            if not (mask & (1 << u)):
                continue
            cur = dp[mask][u]
            if cur == INF:
                continue
            # try to go to v not in mask
            rem = (~mask) & (N - 1)
            v = rem
            while v:
                lsb = v & -v
                vv = (lsb.bit_length() - 1)
                new_mask = mask | (1 << vv)
                # relax
                nv = cur + dist[u][vv]
                if nv < dp[new_mask][vv]:
                    dp[new_mask][vv] = nv
                v -= lsb

    full = N - 1
    ans = INF
    for u in range(n):
        if dp[full][u] < INF:
            ans = min(ans, dp[full][u] + dist[u][0])  # return to start
    return ans

Key concepts:- We encode visited set as bitmask (0..2^n-1).- Transition: extend path by one unvisited node.- Final answer: best path visiting all nodes and returning to 0.

Complexity:- Time: For each of 2^n masks, for each of up to n end-nodes u, we attempt up to n transitions → O(n^2 * 2^n).- Memory: store dp table size O(n * 2^n).

Practical extensions for n > 20:- Branch-and-bound with a cheap lower bound (e.g., sum of two smallest outgoing edges per unvisited node or a 1-tree/Held–Karp bound) to prune branches.- A* / iterative deepening A* using admissible lower bounds.- Heuristics/metaheuristics: Lin–Kernighan, 2-opt/3-opt local search, simulated annealing, genetic algorithms — fast and often near-optimal on larger instances.- Meet-in-the-middle or bidirectional DP variants and sparse DP optimizations if graph structure allows.- Use approximation or MST-based bounds when exact is infeasible; combine local search seeded by heuristics (nearest neighbor, greedy) then refine with LK.

Unlock Full Question Bank

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

Join thousands of developers preparing for their dream job.