Dynamic Programming Questions

High-level summary: reconstruction trades time for space. Let N = number of DP states, T = average work to recompute transitions per state (i.e., time per subproblem), P = bytes to store one parent pointer, and k = checkpoint interval (number of states between checkpoints).

A) Store parent pointers for every DP state

• Space: O(N·P) (must keep all pointers in memory or on fast storage).
• Time (reconstruct): O(L) where L is path length — just follow pointers; negligible extra compute.
• Sweet spot: when N·P fits comfortably in RAM (or high-throughput local SSD) and low-latency reconstruction is required (real-time serving, many queries).
• Practical notes: simplest, lowest-latency. Use compression/sparse encoding if many identical parents. For GPU-memory constrained workloads, avoid full pointer storage on device.

B) Recompute subproblems on demand (no pointers)

• Space: O(1) extra (only store scores or minimal metadata).
• Time: Worst-case O(R·T) where R is number of recomputed states; often R ≈ O(N) in naive backtracking, but can be smaller if structure exploited.
• Sweet spot: when memory is extremely constrained and recomputation cost is small relative to storage cost (cheap CPU/GPU cycles, offline batch jobs).
• Practical notes: good for deterministic DP with cheap local transitions (e.g., recompute one predecessor quickly). For ML with expensive scoring (large models), recompute can be very costly; consider caching hot subproblems.

C) Checkpointing parent pointers at intervals + recompute between checkpoints

• Space: O((N/k)·P) storing checkpoints every k states.
• Time: Reconstruction cost O((k)·T·(L/k)) ≈ O(L·T) but with smaller constants: per segment you recompute up to k states. More precisely, total recompute work ≈ (L/k)·(work to recompute segment) ~ O((L·k_avg)·T) where k_avg ≤ k.
• Trade-off curve: choose k to balance memory M and acceptable extra compute: M ≈ (N/k)·P ⇒ k ≈ (N·P)/M. Reconstruction time grows linearly with k.
• Sweet spot: production scenarios with limited RAM but cheap CPU/SSD I/O — e.g., large tables that won’t fit in RAM but where recomputing a small window is feasible. Checkpointing also parallelizes well: segments can be recomputed independently.

Advice for ML workloads with very large tables (don’t fit in memory)

• Prefer checkpointing (C) as default: store checkpoints on fast SSD (mmap files) and recompute small segments in-memory. Tune k using a target latency budget: pick largest k such that recompute time per segment ≤ latency budget.
• Use hybrid optimizations:
  • Compress pointers (quantize indices, delta-encode) to reduce P.
  • Store checkpoints for only the top-K likely paths (beam/importance) rather than full table.
  • Asynchronously prefetch or warm recompute segments when a path is likely (speculative recompute).
  • Use external-memory friendly formats (memory-mapped arrays, columnar layout) to get sequential I/O for checkpoints.
  • For GPU-heavy scoring, keep model on device but checkpoint pointers on host; recompute segments on GPU only when needed (amortize kernel launch costs).
  • If recomputation dominates, consider storing succinct summaries (hashes, sketches) to prune recompute.
• Measurement-driven tuning: profile T, P, and reconstruction frequency; pick strategy that minimizes cost under your SLOs (latency, throughput, storage cost).
• Fail-safes: ensure deterministic recompute, include checksums to validate recomputed parents, and expose telemetry for checkpoint hit/miss and recompute time to guide future tuning.

To solve this, precompute a boolean table isPal[i][j] indicating s[i..j] is palindrome (O(n^2)). Then compute minCuts[i] = minimum cuts for s[0..i] using DP: if s[0..i] is palindrome, cuts=0 else cuts = min(minCuts[j-1]+1) for every j in [1..i] where s[j..i] is palindrome. To reconstruct partitions, store best cut index for each i.

def min_cut_palindrome(s):
    n = len(s)
    if n <= 1:
        return 0, [s] if n==1 else []

    # Precompute palindromes: isPal[i][j] True if s[i..j] is palindrome
    isPal = [[False]*n for _ in range(n)]
    for center in range(n):
        # odd length
        l = r = center
        while l>=0 and r<n and s[l]==s[r]:
            isPal[l][r] = True
            l -= 1; r += 1
        # even length
        l, r = center, center+1
        while l>=0 and r<n and s[l]==s[r]:
            isPal[l][r] = True
            l -= 1; r += 1

    # DP for min cuts and reconstruction pointer
    INF = 10**9
    minCuts = [INF]*n
    prev = [-1]*n  # prev[i] = index before the palindrome that ends at i
    for i in range(n):
        if isPal[0][i]:
            minCuts[i] = 0
            prev[i] = -1
            continue
        for j in range(1, i+1):
            if isPal[j][i] and minCuts[j-1] + 1 < minCuts[i]:
                minCuts[i] = minCuts[j-1] + 1
                prev[i] = j-1

    # reconstruct partitions
    parts = []
    idx = n-1
    while idx >= 0:
        start = prev[idx] + 1
        parts.append(s[start:idx+1])
        idx = prev[idx]
    parts.reverse()
    return minCuts[n-1], parts

# Example:
# min_cut_palindrome("aab") -> (1, ["aa","b"])

Key points:

• Time: O(n^2) for palindrome table + O(n^2) for DP => O(n^2).
• Space: O(n^2) for isPal, O(n) for minCuts and prev.
• Trade-offs: You can reduce space to O(n) by computing palindromes on the fly using center expansion during DP (increasing constant factors) or by storing only needed diagonals; reconstruction becomes trickier without prev pointers. For very long strings consider streaming/linear-memory heuristics or Manacher-based palindrome info to speed palindrome checks. Edge cases: empty string, all-equal characters, large n (~10^4) may hit memory limits for O(n^2).

To count distinct subsequences of s that equal t, use dynamic programming. Let dp[i][j] be the number of ways the prefix s[i:] can form the prefix t[j:]. Recurrence:

• If s[i] == t[j]: dp[i][j] = dp[i+1][j+1] + dp[i+1][j] (use the character or skip it)
• Else: dp[i][j] = dp[i+1][j] (skip s[i])
  Base cases:
• dp[len(s)][len(t)] = 1 (empty t matched)
• dp[i][len(t)] = 1 for all i (one way to match empty t)
• dp[len(s)][j] = 0 for j < len(t) (no chars left in s to match non-empty t)

We can implement space-optimized 1D DP iterating s from right to left. Use modulo = 10**9+7 to avoid overflow.

def num_distinct(s: str, t: str) -> int:
    MOD = 10**9 + 7
    n, m = len(s), len(t)
    # Edge cases
    if m == 0:
        return 1
    if n == 0:
        return 0

    # dp[j] = number of ways s[i+1:] matches t[j:]
    dp = [0] * (m + 1)
    dp[m] = 1  # empty t

    # iterate s from right to left
    for i in range(n - 1, -1, -1):
        # iterate t from left->right but updating using previous row requires right->left
        for j in range(m - 1, -1, -1):
            if s[i] == t[j]:
                dp[j] = (dp[j] + dp[j + 1]) % MOD
            # else dp[j] remains dp[j] (skip s[i])
    return dp[0]

Key points:

• Time: O(n*m), Space: O(m) with 1D optimization.
• Why right->left for j: we must use dp[j+1] from the previous "row" (i+1) before dp[j] gets overwritten.
  Edge cases:
• Empty t returns 1.
• t longer than s returns 0.
• Large counts handled by modulo.
• Works with repeating characters and duplicates (counts combinations, not permutations).

Common pitfalls and best practices for top-down memoization in production ML Python:

Pitfalls

• Unbounded memory growth: naive dict caches can exhaust RAM for long runs or many unique inputs.
• Recursion depth: deep recursive calls (e.g., large graphs) hit RecursionError.
• Non-deterministic keys: using unhashable/mutable or non-canonical inputs leads to cache misses or collisions.
• Thread/process-safety: plain dicts aren’t safe across threads/processes used by data loaders or batch workers.
• Serialization fragility: pickling complex objects or functions can break across versions or environments.
• Silent correctness bugs: caching stale or version-mismatched outputs causes subtle downstream errors.

Best practices

• Use bounded caches: functools.lru_cache(maxsize=N) or custom LRU/TTL caches to limit growth; choose size/TTL based on memory budget and input distribution.
• Prefer iterative over deep recursion: rewrite to iterative DP or increase sys.setrecursionlimit only cautiously and with tests.
• Deterministic, compact keys: canonicalize inputs (tuple-ize, sort dict items), avoid floating-point raw values (quantize or round), and use stable hashing (hashlib.sha256 on canonical bytes).
• Thread/process safety: for multi-threaded use, protect cache with threading.Lock; for multi-process or distributed jobs use external stores (Redis, Memcached) or multiprocessing.Manager-backed caches.
• Eviction & persistence: combine LRU with TTL; for large/expensive values consider caching metadata and storing payloads on disk (LMDB, RocksDB) or cloud object store with keys referencing content.
• Serialization/versioning: serialize values with robust formats (msgpack, protobuf) and include schema/model version in cache keys to avoid incompatibility.
• Monitoring & testing: track cache hit/miss rates, memory usage, and add unit/integration tests that exercise cache behavior (cold start, eviction, version bump).
• Simplicity first: memoize only pure, idempotent functions; avoid caching functions with side effects or external state.

Example lightweight pattern: canonicalize inputs -> compute keyed hash -> use LRU or external cache -> include model/schema/version in key.

We can solve this with bottom-up dynamic programming: build an (m+1)x(n+1) table dp where dp[i][j] is LCS length of a[:i] and b[:j]. After filling dp, backtrack from dp[m][n] to construct one LCS by walking i->0, j->0: if a[i-1]==b[j-1], prepend that char and move diagonally; otherwise move to the neighbor with larger dp value.

def lcs_string(a: str, b: str) -> str:
    m, n = len(a), len(b)
    # dp[i][j] = LCS length for a[:i], b[:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Build table bottom-up
    for i in range(1, m + 1):
        ai = a[i - 1]
        for j in range(1, n + 1):
            if ai == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = dp[i - 1][j] if dp[i - 1][j] >= dp[i][j - 1] else dp[i][j - 1]

    # Backtrack to build one LCS (reverse order)
    i, j = m, n
    res_chars = []
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            res_chars.append(a[i - 1])
            i -= 1
            j -= 1
        else:
            # Move in direction of larger dp value
            if dp[i - 1][j] >= dp[i][j - 1]:
                i -= 1
            else:
                j -= 1

    return ''.join(reversed(res_chars))

Key points:

• Time: O(mn), Space: O(mn) for full table (can be reduced if only length needed).
• Backtracking reconstructs a valid LCS; ties are broken arbitrarily by >=.
• Edge cases: empty strings -> returns "". Handles duplicates and multiple valid LCS by returning any one.