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

68 practiced

Write a function in Python that computes the number of unique paths in an m x n grid from top-left to bottom-right moving only right or down. Provide the DP recurrence and an implementation that handles m,n up to 1000 using combinatorics or DP with space optimization. Discuss numeric overflow and large answers.

Sample Answer

Approach summary- Recurrence (DP): paths[i][j] = paths[i-1][j] + paths[i][j-1], with paths[0][j]=paths[i][0]=1.- Closed form (combinatorics): number of unique paths = C((m-1)+(n-1), m-1) = C(m+n-2, m-1). Use multiplicative binomial to handle large m,n efficiently.

Python implementation (multiplicative binomial, O(min(m,n)) time, O(1) extra space):

python

def unique_paths(m, n):
    """
    Returns C(m+n-2, m-1) computed multiplicatively to avoid large factorials.
    Works for m,n up to ~1000 (and much larger) using Python big ints.
    """
    if m <= 0 or n <= 0:
        return 0
    # choose smaller k = min(m-1, n-1) for fewer iterations
    k = min(m - 1, n - 1)
    total = m + n - 2
    res = 1
    for i in range(1, k + 1):
        res = res * (total - k + i) // i  # keep intermediate results integer
    return res

Key points- Time: O(min(m,n)). Space: O(1) extra (besides big-int storage).- Alternative: DP with 1D array of length n: dp[j] = dp[j] + dp[j-1], O(m*n) time, O(n) space — useful if combinatorics unavailable.- Numeric overflow: Python ints are arbitrary-precision so no overflow; in languages with fixed-width integers (e.g., 64-bit) binomial answers for m,n ~1000 far exceed limits — use big integer libraries or return modulo (e.g., 10^9+7) if required.- Edge cases: m or n = 1 -> 1 path; invalid (<=0) -> 0.

HardTechnical

106 practiced

Implement the Cocke-Younger-Kasami (CYK) algorithm for parsing sentences using a CNF probabilistic context-free grammar (PCFG). Provide O(n^3 |G|) DP implementation, explain chart parsing, and discuss pruning, beam search, and packed representations for scaling to long sentences.

Sample Answer

We can implement probabilistic CYK (PCYK) for a CNF PCFG using dynamic programming over spans: for each span (i, j) store best probability for every nonterminal A that can derive substring words[i:j]. We use log-probabilities to avoid underflow and keep O(n^3 |G|) by iterating span length, split point, and binary rules A -> B C. Chart parsing means filling a triangular chart of span cells; each cell holds a map from nonterminal -> (best_log_prob, backpointer).

Approach:1. Preprocess grammar into CNF with log probabilities and index binary rules by (B,C) -> list of (A, logP).2. Initialize length-1 spans using terminal rules A -> word with unary conversions in CNF.3. For span length L from 2..n, for i=0..n-L, j=i+L: for split k in (i+1..j-1), for each B in chart[i,k], C in chart[k,j], for each A in rules[(B,C)]: compute score = logP(A->B C) + score(B) + score(C); keep max for A.4. Final parse = best A covering (0,n) for start symbol.

Example implementation (simplified, returns best parse tree):

python

import math
from collections import defaultdict

LOG0 = -1e300

def log(x): return math.log(x) if x>0 else LOG0

# grammar: list of (lhs, rhs_tuple, prob)
# rhs_tuple length 1 for terminals, 2 for binaries
def pcfg_cyk(words, grammar, start='S'):
    n = len(words)
    # index rules
    bin_index = defaultdict(list)   # (B,C) -> [(A,logp)]
    term_index = defaultdict(list)  # word -> [(A,logp)]
    for A, rhs, p in grammar:
        lp = log(p)
        if len(rhs)==1:
            term_index[rhs[0]].append((A, lp))
        else:
            bin_index[(rhs[0], rhs[1])].append((A, lp))

    chart = [ [dict() for _ in range(n+1)] for _ in range(n) ]
    back = [ [dict() for _ in range(n+1)] for _ in range(n) ]

    # length-1
    for i,w in enumerate(words):
        for A, lp in term_index.get(w,[]):
            chart[i][i+1][A] = lp
            back[i][i+1][A] = (w,)
    # DP
    for L in range(2, n+1):
        for i in range(0, n-L+1):
            j = i+L
            cell = chart[i][j]
            for k in range(i+1, j):
                left = chart[i][k]
                right = chart[k][j]
                for B, lb in left.items():
                    for C, lc in right.items():
                        for A, lap in bin_index.get((B,C),[]):
                            score = lap + lb + lc
                            if score > cell.get(A, LOG0):
                                cell[A] = score
                                back[i][j][A] = (k, B, C)
    # reconstruct
    if start not in chart[0][n]:
        return None
    def build(i,j,A):
        bp = back[i][j][A]
        if len(bp)==1:
            return (A, bp[0])
        k,B,C = bp
        return (A, build(i,k,B), build(k,j,C))
    return build(0,n,start)

Key concepts:- Chart parsing stores partial derivations per span enabling reuse (dynamic programming).- Using log-probabilities converts products to sums; keep max (Viterbi parse).

Scaling techniques:- Pruning: discard low-probability entries per cell below a threshold relative to cell max (beam-like) to reduce pairings.- Beam search: keep top-K nonterminals per cell (chart cell beam); reduces combinations from |N|^2 to K^2 per split.- Packed representations: use shared packed forest (compact hypergraph) where identical subtrees share structure — store alternative derivations compactly rather than single backpointer; required for n-best or full posterior marginals (inside-outside).- Additional: use unary closure precomputation, sparse indexing (only iterate over present B/C), and parallelization over splits.

Edge cases:- Unknown words: add OOV rules or smoothing.- Non-CNF grammars: convert to CNF carefully preserving probabilities.

This implementation gives the standard O(n^3 |G|) Viterbi-CYK and the listed scaling techniques are practical ways to parse longer sentences in real systems.

MediumTechnical

59 practiced

Describe and implement the Viterbi algorithm for HMM sequence labeling in Python. Include log-probability handling to avoid underflow and discuss smoothing/unknown observation handling in practical NLP tagging tasks.

Sample Answer

To label a sequence with a Hidden Markov Model (HMM) we use Viterbi: dynamic programming that finds the most probable state path given emissions. Use log-probabilities to avoid underflow (sum of logs instead of product of probs).

Approach:1. Convert transition and emission probabilities to log space.2. Initialize dp[0][state] = log(start_prob[state]) + log(emission_prob[state][obs0])3. Recurrence: dp[t][s] = max_{s'} (dp[t-1][s'] + log_trans[s'][s]) + log_emission[s][obs_t]; track backpointers.4. Backtrack to recover best path.

Implementation (with log handling and simple add-k smoothing + UNK handling):

python

import math
from collections import defaultdict

LOG0 = -1e9  # large negative ~ log(0)

def log(x):
    return math.log(x) if x>0 else LOG0

def viterbi(obs_seq, states, start_p, trans_p, emit_p, unk_prob=1e-6, add_k=1e-5):
    # Precompute log probs with add-k smoothing for transitions and emissions
    S = len(states)
    state_idx = {s:i for i,s in enumerate(states)}
    log_start = {s: log(start_p.get(s,0)+add_k)}
    log_trans = defaultdict(dict)
    for a in states:
        for b in states:
            log_trans[a][b] = log(trans_p.get(a,{}).get(b,0)+add_k)
    # emissions: handle unknown words by giving small probability
    log_emit = defaultdict(dict)
    for s in states:
        for w,p in emit_p.get(s,{}).items():
            log_emit[s][w] = log(p + add_k)
        log_emit[s]['<UNK>'] = log(unk_prob)  # fallback

    T = len(obs_seq)
    dp = [defaultdict(lambda: LOG0) for _ in range(T)]
    bt = [dict() for _ in range(T)]

    # init
    o0 = obs_seq[0] if obs_seq else None
    for s in states:
        e = log_emit[s].get(o0, log_emit[s]['<UNK>'])
        dp[0][s] = log(start_p.get(s,0)+add_k) + e

    # recurrence
    for t in range(1, T):
        ot = obs_seq[t]
        for s in states:
            e = log_emit[s].get(ot, log_emit[s]['<UNK>'])
            best_score = LOG0
            best_prev = None
            for sp in states:
                score = dp[t-1][sp] + log_trans[sp][s] + e
                if score > best_score:
                    best_score = score
                    best_prev = sp
            dp[t][s] = best_score
            bt[t][s] = best_prev

    # termination
    best_last, best_score = None, LOG0
    for s in states:
        if dp[T-1][s] > best_score:
            best_score = dp[T-1][s]; best_last = s

    # backtrack
    path = [best_last]
    for t in range(T-1,0,-1):
        path.append(bt[t][path[-1]])
    return list(reversed(path)), best_score

Key points:- Use log-sum for comparisons; addition of logs replaces multiplication.- Complexity: O(T * K^2) time, O(T*K) space (T sequence length, K states).- Smoothing/unknowns: add-k smoothing for transitions/emissions reduces zero probs; reserve an <UNK> emission (or use morphological/character/backoff models) to handle OOV words. For large tagsets use beam search or Viterbi with pruning to scale.- Edge cases: empty sequence, all-zero probs, numerical underflow handled by log floor (LOG0).

MediumTechnical

71 practiced

Implement a digit DP in Python to count how many integers x in range [0, N] do not contain the digit '4'. Explain state design including position, tight flag, and leading-zero handling. Provide N up to 10^18 and discuss complexity.

Sample Answer

Approach (brief): use digit-DP over the decimal digits of N. At each digit position we decide the digit to place, tracking:- pos: current digit index (0 = most-significant)- tight: whether prefix equals N's prefix (so upper bound for this digit is restricted)- leading_zero: whether we've only placed leading zeros so far (so a leading zero doesn't count as containing '4')We forbid placing digit '4'. Use memoization (lru_cache). For N up to 1e18 digits ≤ 19, complexity is small.

python

from functools import lru_cache

def count_no4_up_to(N):
    s = str(N)
    L = len(s)

    @lru_cache(None)
    def dp(pos, tight, leading_zero):
        # pos: current index in s (0..L)
        # tight: 1 if prefix equals N's prefix else 0
        # leading_zero: 1 if all previous digits were zeros
        if pos == L:
            # Reached end: count this number.
            # We count 0 as valid (leading_zero True at end -> number 0)
            return 1
        limit = int(s[pos]) if tight else 9
        total = 0
        for d in range(0, limit + 1):
            if d == 4:
                continue  # forbid digit 4
            ntight = tight and (d == limit)
            nleading = leading_zero and (d == 0)
            total += dp(pos + 1, ntight, nleading)
        return total

    return dp(0, True, True)

# Examples
print(count_no4_up_to(0))      # 1 -> only 0
print(count_no4_up_to(9))      # 9 (0..9 except 4 => 9)
print(count_no4_up_to(100))    # counts numbers in [0,100] without digit 4

Key design notes:- Position: moves left-to-right through digits; base case pos==L returns 1 (a valid number formed).- Tight: constrains choices to not exceed N when tight==True.- Leading_zero: ensures we treat leading zeros correctly (they don't make a '4'); also lets 0 be counted.- We skip digit 4 for all positions; that automatically excludes any number containing 4.

Complexity:- States: O(L * 2 * 2) where L ≤ 19, and per state we iterate up to 10 digits → O(10 * L) ~ O(L).- For N up to 1e18 this is trivial: about a few hundred operations.

Edge cases:- N = 0 (returns 1)- Large N (up to 10^18) handled as string of digits- Ensure memoization cleared between calls if reusing function with different N.

HardTechnical

54 practiced

Advanced digit DP: count numbers in [0, N] where sum of digits modulo K equals r, for N up to 10^18 and K up to 100. Provide state design, memoization strategy, and a Python or C++ implementation. Discuss time complexity and optimizations for larger K.

Sample Answer

Approach (brief)Use digit DP over decimal digits of N. State: (pos, tight, mod, started) where- pos: index in digits (0..len-1)- tight: whether prefix equals N's prefix (0/1)- mod: current sum of digits modulo K (0..K-1)- started: whether we've placed any non-leading digit (to handle leading zeros so 0 is counted correctly)

Transition: for current digit choose d in [0, up] where up = digits[pos] if tight else 9. New_mod = (mod + d) % K. New_tight = tight && (d == up). At end (pos==len), if started (or allow zero separately) and mod == r, return 1.

Memoization: use lru_cache or a 4D array sized [pos][tight][mod][started]. With len<=19 and K<=100 this is small (~19*2*100*2 states).

Python implementation

python

from functools import lru_cache

def count_mod_sum(N: int, K: int, r: int) -> int:
    digits = list(map(int, str(N)))
    n = len(digits)

    @lru_cache(None)
    def dp(pos: int, tight: int, mod: int, started: int) -> int:
        if pos == n:
            # allow counting 0: if not started, treat sum=0
            return 1 if (mod % K == r) else 0
        up = digits[pos] if tight else 9
        res = 0
        for d in range(0, up + 1):
            ntight = tight and (d == up)
            nstarted = started or (d != 0)
            nmod = (mod + d) % K
            res += dp(pos + 1, ntight, nmod, nstarted)
        return res

    return dp(0, True, 0, False)

Key points and correctness- We accumulate digit sum modulo K to keep state small.- Leading zeros are handled; when all digits zero sum=0 included.- dp uses memoization keyed by (pos, tight, mod, started). Tight=1 states are rarely reusable; the majority are untight and heavily memoized.

Time & Space complexity- States: O(len * 2 * K * 2) ~ O(len * K).- Transitions: each state iterates up to 10 digits => Time O(10 * len * K) ≈ O(len * K).- For N up to 1e18, len ≤ 19, K ≤ 100 → ~19*100*10 ~ 19k operations; trivial.

Optimizations for larger K- If K grows large (~1e4), DP cost O(len*K) may become heavy. For many queries or very large K consider: - Use transition matrix for untight blocks: build 10-digit transition matrix T (KxK) where T[a][b] counts transitions adding a digit (shift by digit). Raise T to power of remaining positions using fast exponentiation and combine with prefix tight portion. Complexity O(K^3 log len) for naive matrix mult; use FFT/NTT-based convolution to speed to ~O(K log K). - Use number-theoretic transforms if representing mod-add transitions as cyclic convolutions. - Reduce mod state via gcd: if r and K share structure, sometimes modulus can be reduced if you only care about subset of residues.Edge cases- Ensure r in [0,K-1], N=0 handled (sum=0), large K validate memory.

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.