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

56 practiced

Given an array nums with length <= 200 and values positive integers with total sum <= 10000, implement Python function can_partition(nums: List[int]) -> bool that returns True iff nums can be partitioned into two subsets with equal sum. Provide both bitset and boolean-DP solutions, explain complexity, and discuss applicability to resource partitioning in SRE contexts.

Sample Answer

To solve partition-to-equal-sum, target = sum(nums)/2 must be integer. Two common DP approaches:

1) Bitset (fast, memory-efficient): use an integer as a bitset where bit i means sum i reachable. Shift-and-OR updates reachable sums in O(n * (sum/word_size)) but in Python shifts are efficient.

python

from typing import List

def can_partition_bitset(nums: List[int]) -> bool:
    total = sum(nums)
    if total % 2: 
        return False
    target = total // 2
    bits = 1  # bit 0 set
    for x in nums:
        bits |= bits << x
        # optional: mask to keep bits small
        if bits >> target & 1:
            return True
    return (bits >> target) & 1 == 1

2) Boolean DP (classic knapsack): dp[i] = reachable sum i.

python

def can_partition_dp(nums: List[int]) -> bool:
    total = sum(nums)
    if total % 2: 
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for x in nums:
        for s in range(target, x - 1, -1):
            if dp[s - x]:
                dp[s] = True
        if dp[target]:
            return True
    return dp[target]

Complexity:- Time: O(n * target) for boolean DP. Bitset effectively O(n * (target / word_size)) but in Python treat shifts as roughly O(#bits) so still ~O(n * target) in worst case.- Space: O(target) for DP; O(1) extra for bitset (bits size ~target bits => memory O(target/8)).

Edge cases:- Empty list (False unless sum 0)- Single element- Large values > target handled naturally- Sum == 0: partitionable (two zero-sum subsets)

SRE applicability:Use this for resource partitioning problems (splitting load, disk or capacity balancing across nodes, packing tasks into two fault domains). Bitset is great when total capacity (sum) is bounded and you need fast checks; boolean DP is explicit and easier to reason about for debugging/alerts. For large-scale real systems, consider greedy heuristics, multi-bin partitioning, or ILP for more constraints, and integrate checks into capacity planning pipelines with monitoring/SLIs.

HardTechnical

57 practiced

Model a cluster as a Markov chain where each server can transition between up and down states with known probabilities. Using DP over time (or matrix exponentiation), compute expected downtime over T steps and steady-state probabilities. Discuss state explosion for n servers, product-form approximations for independence, and practical methods SREs use to estimate reliability metrics.

Sample Answer

Approach (model):- Model each server as a 2-state CTMC/DTMC with states {Up,Down}. For a single server with up→down prob p and down→up prob q per step (DTMC) the one-step transition matrix is: P = [[1-p, p], [q, 1-q]]- For n servers the full chain has 2^n states (vector of up/down). Let X_t be number of down servers; expected downtime at step t is E[ downtime_t ] = E[ X_t ].

DP over time (finite T):- Represent distribution over 2^n states as vector π_t. π_{t+1} = π_t · P_full where P_full = ⊗_{i=1..n} P_i if servers are independent (Kronecker product). Compute expected downtime: sum_s π_t(s) * (#down in s). For T steps iterate or use fast exponentiation: π_T = π_0 · P_full^T (matrix exponentiation).

Steady state:- Solve π = π · P_full (left eigenvector) or for marginal per-server steady-state up probability: π_up = q / (p+q). If independent, expected steady downtime = n * (1 - π_up).

State explosion and approximations:- Exact state space is 2^n — infeasible for n>20. If servers are independent (no correlated failures), product-form holds: full distribution = ⊗ marginals, so only O(n) work. When dependencies exist (shared power/network), use: - Mean-field / fluid approximations: track fraction of failed servers f_t with O(1) dynamics. - Aggregate birth–death on count of failures (n+1 states) if failures/repairs are symmetric. - Low-rank / tensor-train approximations for structured correlations.

Practical SRE methods:- Monte Carlo simulation to estimate downtime, tail percentiles, and rare events (importance sampling for very small p).- Empirical estimation from telemetry: infer p, q from time-series of incidents; use bootstrap for CI.- Fault-injection & chaos testing to validate model assumptions (independence, repair distributions).- Use reliability primitives: availability = MTBF/(MTBF+MTTR) for each component; combine via reliability block diagrams or minimal-cut sets for system-level SLOs.- Instrumentation: fine-grained health metrics, alerting on correlated failures, and periodically re-fit models with production data.

Trade-offs:- Independence/product-form gives scalability and closed form but risks underestimating correlated outage risk.- Aggregated/mean-field models are tractable but lose per-node detail.- Simulations + empirical telemetry often give the most actionable SRE estimates and can be used to validate analytic approximations.

MediumTechnical

53 practiced

Given an R x C grid (R,C <= 2000) where some cells are blocked, implement Python function count_paths(grid) that returns number of ways to go from top-left to bottom-right moving only right or down, modulo 1e9+7. Discuss DP with rolling arrays for memory efficiency and optimizations for sparse obstacles that SREs might encounter in large-scale topology maps.

Sample Answer

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.

python

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.

MediumTechnical

70 practiced

Describe the job sequencing / scheduling with deadlines and profits problem: you have tasks each with deadline and profit and can do at most one task per time slot. Explain the greedy approach (sort by profit and place using DSU) and compare with DP over time for large horizons. Provide an algorithmic approach useful for scheduling batch SRE jobs with deadlines.

Sample Answer

Problem: Given jobs with (deadline, profit), one job per integer time slot, schedule subset to maximize total profit with each job finished by its deadline.

Greedy idea (standard): sort jobs by profit descending; for each job, schedule it at the latest available slot ≤ its deadline. Use a Disjoint Set Union (DSU) / union-find to find that latest free slot quickly: each slot points to the previous free slot once occupied.

Algorithm (steps):- Sort jobs by profit desc.- Let maxD = max(deadlines). Initialize parent[i]=i for i=0..maxD.- For a job with deadline d: - find = find_parent(d) — returns largest free slot ≤ d. - if find == 0: no slot available, skip. - else: assign job to slot find and union(find, find-1) to mark find occupied.- Sum profits of assigned jobs.

Python implementation:

python

# jobs = [(profit, deadline), ...]
def schedule_jobs(jobs):
    jobs.sort(reverse=True)  # by profit
    maxD = max(d for _, d in jobs)
    parent = list(range(maxD+1))
    def find(x):
        if parent[x]!=x:
            parent[x]=find(parent[x])
        return parent[x]
    total=0
    assigned=[]
    for p,d in jobs:
        slot = find(d)
        if slot>0:
            parent[slot]=find(slot-1)
            total+=p
            assigned.append((p,d,slot))
    return total, assigned

Why DSU: each find/unite is nearly O(1) amortized (α(n)). Overall O(n log n) for sort + O(n α(maxD)). Very efficient when deadlines are large but number of jobs n is moderate.

DP over time: you can do knap/DP where dp[t] = max profit up to time t, iterating jobs and times (or using bitset/interval DP). DP is O(n * maxD) time and O(maxD) space — impractical when maxD (time horizon) is huge (e.g., daily windows over months, many seconds) even if n small.

SRE application (batch job scheduling):- Use greedy+DSU when jobs are discrete slots (cron windows) and you must maximize revenue/importance under SLAs.- Pre-normalize time to coarse slots (e.g., minutes/hours) to keep maxD small.- Add priorities/costs by mapping to profit; enforce reservations by pre-occupying slots.- For streaming or continuous arrivals, maintain DSU for sliding window and periodically recompute; for fairness, combine with weight decay or quotas.- If dependencies or varying durations exist, extend scheduling to EDF/weighted interval scheduling (DP on intervals) or use heuristics + capacity-aware bin-packing.

Edge cases:- deadlines ≤ 0, duplicate deadlines, long durations (not unit), and dependencies — treat separately.

Trade-off summary:- Greedy+DSU: fast, simple, best for unit-length tasks and large horizons.- DP: exact for small maxD or when durations vary, but costly for large horizons.

HardTechnical

71 practiced

Design and implement an advanced digit DP: count integers in [0, N] (N up to 10^18) that have no two adjacent equal digits and are divisible by k (k <= 100). Define states (pos, tight, prev_digit, rem) and provide memoization strategy. Discuss handling of leading zeros, memory complexity and optimizations to make it feasible in production SRE tooling.

Sample Answer

Approach (short): Use digit-DP over decimal digits of N with state (pos, tight, prev_digit, rem). pos = index from 0 (most-significant) to L, tight indicates prefix equals N's prefix, prev_digit in {-1,0..9} (-1 means no previous non-discarded digit / leading zeros), rem is current remainder modulo k. Count numbers in [0..N] where no two adjacent equal digits (adjacency ignores leading zeros as "no previous digit").

Recursive implementation with memoization (iterative possible; recursion shown for clarity):

python

from functools import lru_cache

def count_no_adj_eq_divisible(N: int, k: int) -> int:
    s = list(map(int, str(N)))
    L = len(s)

    @lru_cache(maxsize=None)
    def dp(pos: int, tight: int, prev: int, rem: int) -> int:
        # pos = index in s (0..L). At pos==L we processed all digits.
        if pos == L:
            return 1 if rem == 0 else 0
        limit = s[pos] if tight else 9
        total = 0
        for d in range(0, limit + 1):
            ntight = tight and (d == limit)
            # leading zeros: if prev == -1 and d == 0, we keep prev = -1 (no adjacency constraint)
            if prev == -1 and d == 0:
                nprev = -1
                nrem = (rem * 10 + d) % k  # including zeros still affects remainder for counting 0..N
                total += dp(pos + 1, ntight, nprev, nrem)
            else:
                # normal digit (either prev != -1 or d != 0)
                if prev != -1 and d == prev:
                    continue  # adjacent equal -> invalid
                nprev = d
                nrem = (rem * 10 + d) % k
                total += dp(pos + 1, ntight, nprev, nrem)
        return total

    # Start with pos=0, tight=1, prev=-1, rem=0
    return dp(0, 1, -1, 0)

Key concepts and reasoning:- prev = -1 marks "no meaningful previous digit" so leading zeros don't trigger adjacency checks.- We still incorporate leading zeros into remainder so numbers like 0 are handled; if you want to exclude 0 explicitly, subtract if needed.- tight ensures we don't exceed N.- Memoization key is (pos, tight, prev, rem). Because tight is boolean, prev ∈ { -1,0..9 } (11 values), pos ≤ 19 for 10^18, rem < k (≤100). So worst-case states ≈ 20*2*11*k ≈ 44k for k=100 — tiny and safe for production.

Memory complexity and optimizations:- Space: ~O(L * 2 * 11 * k) states; each cached value is an integer — with k≤100 this is small (~44k entries). For safety in SRE tooling, use iterative DP (bottom-up) to avoid recursion stack and to tightly control memory layout.- Use compact arrays: pack prev+1 (0..10) and tight (0/1) into indices and store dp[pos][packed] as arrays of length k with int64 values. This yields contiguous memory, faster lookups.- If doing many queries with varying N but same k, precompute transitions for digits and reuse DP skeleton; only fill per N.- To reduce GC pressure in Python, use lru_cache with maxsize or switch to array-backed implementation in C-extension or use PyPy/CPython with minimal object churn.- For extreme performance (SRE alerting/monitoring), implement in Go/Java with iterative DP and preallocated int64[][][] arrays; avoid recursion, avoid hash-based memoization.

Edge cases:- N=0: function returns 1 if 0 % k == 0 and no adjacency violation (handled).- Leading zeros: treated so numbers shorter than L are considered.- k=1 trivial: all numbers satisfying adjacency constraint count; can short-circuit.

Time complexity:- O(L * 10 * states_per_pos) ≈ O(L * 10 * 2 * 11 * k) ~ O(L * k) effectively with small constant (L≤19, k≤100) — fast.

Production notes for SRE:- Prefer iterative DP with arrays for predictable memory and latency.- Add input validation, timeouts, and caching for repeated k queries.- Benchmark with worst-case N and k to pick language/representation that fits latency SLO.

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.