Dynamic Programming Questions

We want to compute DP[j] = min_{i in feasible(j)} { DP[i] + cost(i,j) } where cost(i,j) has monotone quadrangle/convexity or can be rearranged so the candidate indices form a monotone queue; and sliding-window minima are required for telemetry aggregates (e.g., min-latency over last W seconds, or DP with windowed i ∈ [j−W, j−1]).

Approach:

1. Reduce cost(i,j) to form: cost(i,j) = f(j) + g(i) + h(i)*p(j) where comparisons between candidates depend only on i (linear in p(j)) — this yields monotone envelope allowing deque-of-candidates.
2. Maintain deque of candidate indices in increasing i; for each j, pop_front if index < j−W; while new candidate k makes back-of-deque dominated, pop_back; answer DP[j] = DP[deque.front] + cost(deque.front, j).

Pseudocode (python-like):

# cost(i,j) returns DP[i] + cost(i,j)
from collections import deque

def monotone_dp(n, W, cost, DP0):
    DP = [float('inf')]* (n+1)
    DP[0]=DP0
    dq = deque()
    dq.append(0)
    for j in range(1, n+1):
        # remove out-of-window
        while dq and dq[0] < j - W:
            dq.popleft()
        # compute DP[j] using best candidate
        i = dq[0]
        DP[j] = cost(i, j)
        # prepare new candidate j for future indices
        # define domination: i dominates k iff for all future j' cost(i,j') <= cost(k,j')
        while dq:
            k = dq[-1]
            # if j dominates k, pop k
            if dominates(j, k):  # problem-specific comparator using algebraic cross-over
                dq.pop()
            else:
                break
        dq.append(j)
    return DP

Invariant checks:

• deque indices increasing; front is current argmin for current j.
• For any two indices a<b in deque, there exists future j where a better than b before b may become relevant (no redundant indices).
• Window correctness: no index < j−W in deque.

Amortized runtime reasoning:

• Each index enters once and is removed at most once (pop_back or pop_front) => O(n) operations; each cost/dominance check is O(1). Total O(n) time, O(W) space (deque bounded by window or structure-specific bound).

Numerical stability & SRE telemetry considerations:

• Telemetry timestamps and values are noisy; use stable comparison thresholds: when comparing cost(i,j) with cost(k,j) use epsilon to avoid thrashing from floating precision.
• Aggregate over integers/64-bit counters when possible; if using rates (floats), normalize and clamp.
• For large sums, use compensated summation (Kahan) if cost uses cumulative sums.
• Bound W to memory/latency constraints; stream DP updates in batches to avoid GC/latency spikes.
• Handle missing telemetry: treat absent points as +inf or interpolate; ensure deque dominance logic accounts for NaN.

Edge cases:

• Empty deque (no feasible i) -> DP[j]=inf or fallback.
• Window W >= j: initial indices valid.
• cost non-monotone: fallback to naive O(W) per j or ensure preconditions (convexity) hold with tests.
• Very large W: may need hierarchical aggregation (segment trees) to keep memory/time bounded.

Proof sketch:

• Dominance comparator is derived from pairwise cross-over points: solve cost(i,x) <= cost(k,x) for x; maintain increasing cross-over positions => monotone queue correctness. Each popped index is provably never optimal for any later j.

Approach: Use classic bottom-up DP to compute an m+1 by n+1 table of LCS lengths, then reconstruct one LCS by walking back from dp[m][n]. Time O(mn), space O(mn). If only the length is needed, reduce space to O(min(m,n)) with two rolling rows; for full string with low memory, use Hirschberg’s algorithm (divide-and-conquer) to get O(mn) time and O(min(m,n)) space.

def longest_common_subsequence(a: str, b: str) -> str:
    m, n = len(a), len(b)
    # dp[i][j] = length of LCS of a[:i], b[:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        ai = a[i - 1]
        row = dp[i]
        prev = dp[i - 1]
        for j in range(1, n + 1):
            if ai == b[j - 1]:
                row[j] = prev[j - 1] + 1
            else:
                row[j] = row[j - 1] if row[j - 1] >= prev[j] else prev[j]

    # Reconstruct one LCS by walking back
    i, j = m, n
    lcs_chars = []
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            lcs_chars.append(a[i - 1])
            i -= 1; j -= 1
        else:
            if dp[i - 1][j] >= dp[i][j - 1]:
                i -= 1
            else:
                j -= 1
    return ''.join(reversed(lcs_chars))

Key points:

• Time: O(mn). Space: O(mn) for reconstruction; for length-only use two rows (O(min(m,n))).
• To reconstruct with low memory, use Hirschberg’s algorithm (splits one string, uses forward/backward length DP to find split).

SRE use-cases:

• Compare config file histories to find common baseline between versions.
• Detect drift between deployed config and repo.
• Compute common subsequence of log sequences to identify recurring error patterns across services.

To solve TSP for N ≤ 16 we use bitmask DP: dp[mask][v] = minimum cost to reach subset mask ending at v. Start from node 0 (fixing start reduces cycles by N). Transition: dp[mask | (1<<u)][u] = min(dp[mask][v] + cost[v][u]). Finally add cost back to start.

# Python implementation (N <= 16)
import math, functools
def tsp_bitmask(cost):
    n = len(cost)
    START = 0
    ALL = (1<<n) - 1
    INF = 10**18
    # dp[mask][v] stored in dict of arrays for memory/speed tradeoff
    dp = [ [INF]*n for _ in range(1<<n) ]
    dp[1<<START][START] = 0

    for mask in range(1<<n):
        for v in range(n):
            if dp[mask][v] == INF: continue
            for u in range(n):
                if mask & (1<<u): continue
                nd = dp[mask][v] + cost[v][u]
                if nd < dp[mask | (1<<u)][u]:
                    dp[mask | (1<<u)][u] = nd

    res = INF
    for v in range(n):
        if v==START: continue
        res = min(res, dp[ALL][v] + cost[v][START])
    return res

Key concepts:

• Time O(n^2 * 2^n), Space O(n * 2^n). For n=16 this is fine (~16*65536 states).
  Memory/time trade-offs:
• Store dp as array of size (1<<n)*n for fastest access. Reduce memory by storing only masks of a given popcount (rolling DP) or using dicts to keep reachable states (sparse).
• Precompute neighbors or reorder nodes to improve cache locality.

Pruning & branch-and-bound:

• Use DFS + lower-bound (e.g., MST or minimal outgoing edge per unvisited node) to cut branches early; good when many edges are large.
• Keep current best (upper bound) from heuristic (greedy nearest neighbor) to prune aggressively.

Meet-in-the-middle:

• Split nodes into two halves; compute DP from START to middle-set fronts and from START reversed for other half, then combine — reduces constant factors and effectively halves exponent work (useful for N ~ 30 with heavy optimization).

SRE relevance:

• For service probing or rollout path planning, this models minimizing probe/rollback cost visiting multiple targets with limited time windows. Bitmask DP offers an exact small-scale planner; pruning and heuristics let you compute fast safe rollouts and capacity-aware probing schedules in maintenance windows.

We can solve this with dynamic programming: dp[r][c] = ways to reach cell (r,c). Recurrence dp[r][c] = 0 if blocked else (dp[r-1][c] + dp[r][c-1]) % MOD. To save memory for R,C up to 2000 use a single rolling row of length C (O(C) memory). For very sparse obstacles (few blocked cells) we can store blocked positions per row and skip work for unblocked contiguous stretches, or iterate only through columns that matter using a dict/sparse map — useful when topology maps have large empty regions.

MOD = 10**9 + 7

def count_paths(grid):
    """
    grid: list of strings or lists, with '.' for free and '#' for blocked.
    Returns number of paths from (0,0) to (R-1,C-1) moving right/down.
    """
    R = len(grid)
    if R == 0: return 0
    C = len(grid[0])
    # If start or end blocked
    if grid[0][0] == '#' or grid[R-1][C-1] == '#': return 0

    dp = [0] * C
    dp[0] = 1  # start
    for r in range(R):
        for c in range(C):
            if grid[r][c] == '#':
                dp[c] = 0
            else:
                if c > 0:
                    dp[c] = (dp[c] + dp[c-1]) % MOD
                # else dp[c] stays as dp[c] (from top) for c==0
    return dp[C-1]

Key points:

• Rolling array: dp[c] holds ways to current row at column c; dp[c] before update is top, dp[c-1] is left.
• Time: O(R*C). Space: O(C).
• Sparse-obstacle optimizations:
  • Keep a sorted list/set of blocked columns per row and process segments between blocks with simple prefix-sum propagation.
  • Use a hash map for dp when C is huge but few active columns (sparse), iterating only non-zero entries.
• Edge cases: empty grid, start/end blocked, single-row/column.
• For SRE use: prefer streaming row-by-row processing (low memory), log progress for large maps, and benchmark on representative sparse/dense topology datasets.

Approach: LPS(s) = LCS(s, rev(s)). Use DP to compute LCS on strings of length n (n ≤ 2000). To save memory, compute full DP table when you need reconstruction (O(n^2) time & space). For just length, use two rolling rows (O(n) space). Below is an implementation that fills the DP table and reconstructs one LPS.

def longest_palindromic_subsequence(s):
    n = len(s)
    if n == 0:
        return 0, ""
    t = s[::-1]
    # dp[i][j] = LCS length of s[:i] and t[:j]; use (n+1)x(n+1)
    dp = [[0]*(n+1) for _ in range(n+1)]
    for i in range(1, n+1):
        si = s[i-1]
        for j in range(1, n+1):
            if si == t[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    # reconstruct one LCS => LPS
    i, j = n, n
    res = []
    while i>0 and j>0:
        if s[i-1] == t[j-1]:
            res.append(s[i-1])
            i -= 1; j -= 1
        elif dp[i-1][j] >= dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    lps = "".join(reversed(res))
    return dp[n][n], lps

Key concepts:

• LPS equals LCS(s, reverse(s)) because a palindromic subsequence reads same forward/backward.
  Complexity:
• Time O(n^2), Space O(n^2) for reconstruction; length-only can be O(n) space with two rows.
  Trade-offs & optimizations for SRE string-analysis:
• Use rolling arrays (two rows) when processing logs at scale and only length is needed to reduce memory.
• Use sparse or banded DP if expecting limited edit distance between s and reverse (common for near-palindromic short tokens).
• For long streaming logs, process fixed-size windows, sample, or approximate via greedy/heuristic methods to keep latency low.
• Parallelize independent segments, and memoize results for repeated identical tokens (cache hot keys).
  Edge cases:
• Empty string, all-equal chars, and tie-handling in reconstruction (returns one valid subsequence).