Dynamic Programming Questions

Approach (brief)
Use dynamic programming: DP[i][j] = min edits to convert A[0..i) -> B[0..j). To also reconstruct operations, keep a backpointer matrix. For distance-only, use two rolling rows of length min(n,m)+1.

Java implementation (distance + operations)

import java.util.*;
public class Levenshtein {
  public static class Result { public int dist; public List<String> ops; }
  public static Result compute(String A, String B) {
    int n = A.length(), m = B.length();
    int[][] dp = new int[n+1][m+1];
    int[][] prev = new int[n+1][m+1]; // 0=diag,1=del,2=ins
    for(int i=0;i<=n;i++) dp[i][0]=i;
    for(int j=0;j<=m;j++) dp[0][j]=j;
    for(int i=1;i<=n;i++){
      for(int j=1;j<=m;j++){
        if(A.charAt(i-1)==B.charAt(j-1)){
          dp[i][j]=dp[i-1][j-1]; prev[i][j]=0;
        } else {
          int sub = dp[i-1][j-1]+1;
          int del = dp[i-1][j]+1;
          int ins = dp[i][j-1]+1;
          if(sub<=del && sub<=ins){ dp[i][j]=sub; prev[i][j]=0; }
          else if(del<=ins){ dp[i][j]=del; prev[i][j]=1; }
          else { dp[i][j]=ins; prev[i][j]=2; }
        }
      }
    }
    // reconstruct
    List<String> ops = new ArrayList<>();
    int i=n, j=m;
    while(i>0 || j>0){
      if(i>0 && j>0 && prev[i][j]==0){
        if(A.charAt(i-1)==B.charAt(j-1)) ops.add("MATCH "+A.charAt(i-1));
        else ops.add("SUB '"+A.charAt(i-1)+"'->'"+B.charAt(j-1)+"'");
        i--; j--;
      } else if(i>0 && (j==0 || prev[i][j]==1)){ ops.add("DEL '"+A.charAt(i-1)+"'"); i--; }
      else { ops.add("INS '"+B.charAt(j-1)+"'"); j--; }
    }
    Collections.reverse(ops);
    Result r = new Result(); r.dist = dp[n][m]; r.ops = ops;
    return r;
  }
}

Distance in O(min(n,m)) space
Compute only numeric distance with two rows (previous and current) of length min(n,m)+1. If you swap strings so inner loop uses shorter string, space is O(min(n,m)). Time remains O(n*m).

When this prevents reconstructing operations
Rolling rows discard full DP table/backpointers, so you cannot backtrack to get the edit sequence. To reconstruct with reduced space you'd need to:

• store checkpoints (Hirschberg's algorithm) and recursively compute splits to rebuild path in O(n*m) time but O(min(n,m)) auxiliary space, or
• recompute DP segments on demand (trading time for space).

Complexity & notes

• Time: O(n*m)
• Space: O(n*m) with backpointers (for operations), or O(min(n,m)) for distance-only.
• Edge cases: empty strings, very long strings (consider memory/time limits), unicode code points vs. Java chars.

Brief approach (why rolling-array works)
Replace the 2D DP table dp[i][w] (best using first i items) with a single 1D array dp[w] representing the current best value for capacity w. Update dp in-place for each item but in reverse capacity order so each item is used at most once.

Code (Python)

# items: list of (weight, value), W: capacity
def knapsack_01(items, W):
    dp = [0] * (W + 1)          # dp[w] = max value for capacity w
    for wt, val in items:
        # iterate w from W down to wt to avoid reusing same item
        for w in range(W, wt - 1, -1):
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[W]

Why reverse iteration matters
Iterating w descending ensures dp[w - wt] on RHS is the state from previous item-iteration (or prior capacities of same item before update). If we iterated ascending, dp[w - wt] might already include the current item, allowing multiple uses and turning 0-1 into unbounded knapsack.

Complexity & correctness

• Time: O(N * W)
• Space: O(W) (vs O(N * W))
  Correctness follows because for each item we consider taking it exactly once by basing updates on older states via descending w.

Edge cases / backend notes

• Validate weights ≤ W, handle zero-weight items carefully (separate logic).
• For large W, consider alternative approaches (meet-in-the-middle, value-based DP) to avoid memory/time issues.

Brief approach

Use divide-and-conquer DP (aka Aliens trick / Knuth-like optimization) to compute dp[i] = min_{0<=j<i} (dp[j] + cost(j+1,i)) in O(N log N) calls to cost when the argmins (opt[i]) are monotone and cost satisfies quadrangle inequality.

Why monotone opt matters

Monotonicity means opt[l] <= opt[r] for l < r. That bounds the search interval for opt(mid) to [optl, optr] so each subproblem limits work and correctness follows from quadrangle inequality (it implies that optimal split indices don't move left as i increases).

Recursive template (Python)

# dp_prev is dp for previous layer (or dp array being filled), 0-indexed
def compute(l, r, optl, optr, dp_prev, dp):
    if l > r:
        return
    mid = (l + r) // 2
    best_cost = float('inf')
    best_k = -1
    # search only between optl..min(optr, mid-1)
    hi = min(optr, mid - 1)
    for k in range(optl, hi + 1):
        c = dp_prev[k] + cost(k + 1, mid)  # cost expects 1-based endpoints
        if c < best_cost:
            best_cost = c
            best_k = k
    dp[mid] = best_cost
    compute(l, mid - 1, optl, best_k, dp_prev, dp)
    compute(mid + 1, r, best_k, optr, dp_prev, dp)

Complexity

Each level does O(N) cost evaluations across log N levels => O(N log N) cost calls. If cost is heavy but supports faster evaluation (e.g., using cumulative sums), overall runtime can be O(N log C) in parameterized problems.

Validation on sample data

• Small N brute-force vs optimized: compute dp by naive O(N^2) and compare results for many random inputs and cost functions that satisfy quadrangle inequality (e.g., cost(a,b)= (prefix[b]-prefix[a-1])^2).
• Track that best_k(mid) ∈ [optl, optr] during runs; assert monotonicity by checking opt[i] >= opt[i-1] for computed opts.
• If violations occur, cost doesn't satisfy required properties or there is an implementation bug.

Practical notes for backend role

• Precompute prefix arrays to make cost O(1) when possible.
• Profile cost calls; memoize if cost is heavy.
• Use iterative stack to avoid recursion depth limits for large N.

Approach (brief)
Use the classic O(n log n) patience/DP with binary search on tail values, while keeping a predecessor index array to reconstruct one LIS.

Code (Java)

import java.util.*;
public class LIS {
  // returns pair: length and one subsequence
  public static Pair<Integer, List<Integer>> lis(int[] a) {
    int n = a.length;
    int[] tails = new int[n];       // store indices of smallest tail for each length
    int[] prev = new int[n];        // predecessor index for reconstruction
    Arrays.fill(prev, -1);
    int size = 0;

    for (int i = 0; i < n; i++) {
      int x = a[i];
      // binary search on tails by value a[tails[mid]]
      int l = 0, r = size;
      while (l < r) {
        int m = (l + r) / 2;
        if (a[tails[m]] < x) l = m + 1; else r = m;
      }
      int pos = l;
      if (pos > 0) prev[i] = tails[pos-1];
      tails[pos] = i;
      if (pos == size) size++;
    }

    // reconstruct sequence
    List<Integer> seq = new ArrayList<>();
    int k = tails[size-1];
    while (k != -1) { seq.add(a[k]); k = prev[k]; }
    Collections.reverse(seq);
    return new Pair<>(size, seq);
  }
  // Simple Pair for brevity (or use AbstractMap.SimpleEntry)
  public static class Pair<K,V>{ public final K k; public final V v; public Pair(K k,V v){this.k=k;this.v=v;} }
}

Key ideas / predecessor pointers

• tails[len] stores index of minimal tail value for an increasing subsequence of length len+1.
• prev[currentIndex] points to the index of the element that precedes currentIndex in the subsequence (tails[pos-1]) so we can walk back from tails[size-1].

Complexity

• Time: O(n log n) (binary search per element). Space: O(n) for tails and prev.

Trade-offs (clarity vs performance)

• O(n^2) DP is simpler to implement and reason about (clear loops and direct predecessors) and acceptable for small inputs. In backend services handling large lists or high throughput, O(n log n) is preferable. The O(n log n) variant is slightly more complex (index bookkeeping), so in production prefer the faster approach with thorough tests and comments; choose O(n^2) only when inputs are small, latency/non-determinism less critical, or maintainability trumps performance.

Approach (brief)

• Compute Grundy (mex of reachable states) for pile sizes 0..N using given move set S plus any size-dependent moves.
• A position is winning iff Grundy(n) != 0.
• Detect eventual periodicity in the Grundy sequence to answer queries for N up to 1e6 efficiently.

Python implementation (dynamic + periodicity detection)

# compute Grundy up to limit or until periodicity found
def compute_grundy(S, special_fn, limit=10**6, detect_window=5000):
    grundy = [0]
    seen_patterns = {}
    for n in range(1, limit+1):
        moves = [n - a for a in S if n - a >= 0] + special_fn(n)
        reachable = {grundy[m] for m in moves}
        g = 0
        while g in reachable:
            g += 1
        grundy.append(g)
        # periodicity detection: capture tail pattern of last detect_window values
        if n > detect_window*2:
            tail = tuple(grundy[n-detect_window+1:n+1])
            if tail in seen_patterns:
                prev_n = seen_patterns[tail]
                period = n - prev_n
                offset = prev_n - detect_window + 1
                return grundy, (offset, period)
            seen_patterns[tail] = n
    return grundy, None

# example special_fn for moves that depend on n (returns list of resulting indices)
def special_fn_example(n):
    # e.g., if n is even you can remove n//2
    if n % 2 == 0 and n//2 >= 0:
        return [n//2]
    return []

# usage
S = {1,3,4}
grundy, pat = compute_grundy(S, special_fn_example, limit=200000)
def first_wins(n):
    if pat and n > pat[0]:
        offset, period = pat
        idx = offset + ((n - offset) % period)
        return grundy[idx] != 0
    return grundy[n] != 0

Key concepts & optimizations

• Use mex via small boolean array for speed when max Grundy small.
• Periodicity: detect repeating tail windows; store hashes to reduce memory.
• Memory: store only window when seeking periodicity; after period known, answer O(1) for any large N.
• Complexity: O(limit * |S|) time typically; space O(limit) (can be reduced after detecting period).
• Edge cases: special moves producing self-loop avoid infinite move lists; ensure moves >=0.