String Algorithms and Pattern Matching Questions

Covers algorithmic techniques and practical skills for solving string problems and pattern matching tasks. Core algorithm knowledge includes substring search and pattern matching algorithms such as Knuth Morris Pratt, Rabin Karp, Boyer Moore, Z algorithm, Aho Corasick for multiple pattern matching, and rolling hash methods. Data structures and suffix structures are important, including tries, suffix arrays, suffix trees, and suffix automata, together with longest common prefix arrays and related construction techniques. Also includes dynamic programming approaches for string problems such as edit distance and longest common subsequence, palindrome and anagram detection methods, and regular expression concepts and engine behavior. Emphasizes algorithmic complexity analysis, time and space trade offs, memory and streaming constraints, and optimization strategies for very long inputs and high throughput text processing. Practical considerations include parsing and string manipulation idioms in common languages, Unicode and character encoding issues, edge case handling, test case design for strings, and real world applications such as log analysis, text search, and data transformation.

MediumTechnical

57 practiced

You need to search millions of DNA patterns against a reference genome (~3GB). Compare suffix tree vs suffix array (with LCP) for indexing: discuss construction time, memory footprint, query time, and practical compression/on-disk strategies (BWT/FM-index). Which would you pick and why?

MediumTechnical

60 practiced

Design an algorithm for streaming approximate substring matching: given a long stream of text and a pattern of length m, detect windows with at most k mismatches using low memory. Describe a practical filter+verify approach using partitioning, rolling hashes, and explain false positive/negative trade-offs.

Sample Answer

Approach (high level):- Use the classic partition-and-verify trick: split the pattern P (length m) into t = k+1 disjoint contiguous blocks. Any text window T of length m that has ≤ k mismatches must have at least one block that matches exactly. Use rolling hashes to quickly filter candidate windows where some block's hash equals the corresponding pattern block hash. Then verify candidates by counting mismatches (early-abandon when >k).- This is streaming: maintain rolling hashes for each block alignment as characters arrive, and keep a sliding buffer of m chars for verification.

Why this works:- With t = k+1 blocks, at most k blocks can be “bad”, so at least one block is exact — therefore the filter is lossless w.r.t. Hamming-distance ≤ k (no false negatives for substitution-only errors). False positives come only from hash collisions or from matching a block but the rest of window exceeding k mismatches.

Algorithm (pseudocode):

python

# rolling hash parameters
BASE = 257
MOD = 2**61-1  # or use two mods to reduce collisions

# Precompute pattern block hashes
blocks = split_pattern(P, t=k+1)  # contiguous blocks
pat_hashes = [hash(block) for block in blocks]

# streaming state
window = deque()  # keep last m chars
rolling_hashes = [RollingHash(len(block)) for block in blocks]
for char in stream:
    window.append(char)
    if len(window) > m:
        window.popleft()
    # update rolling hashes for each block position relative to window start
    for i, rh in enumerate(rolling_hashes):
        rh.push_char(char)   # maintains hash for current aligned block
        if rh.is_full():
            if rh.value() == pat_hashes[i]:
                # candidate: compute start index of window for this block alignment
                candidate_window = get_window_string(window)
                if verify_hamming(candidate_window, P, k):
                    report_match(window_start_index)

Key implementation details:- RollingHash supports push/pop to maintain block-length substring hash; use pow(BASE, L) precomputed to remove leftmost char.- To support different alignments: the i-th block of pattern aligns to window positions [b_i, b_i + len_i). In streaming you keep rolling hashes for each block length and alignment offset; you only compare when the block slot is full.- Verification: compare characters and count mismatches, abort when >k (O(m) worst-case but usually rare).

Complexity and memory:- Time: O(n * expected_filter_checks + total_verification_cost). Filter updates are O(1) per char per block (so O((k+1)*n)). Verifications occur rarely; with good hash and block sizes it's much less frequent than n.- Space: O(m) for window buffer + O(k) for hash state and stored pattern block hashes — low memory, independent of stream size.

False positives/negatives trade-offs:- Partitioning guarantee: for Hamming-distance only, t=k+1 gives zero false negatives from partition logic. If you allow insertions/deletions, this guarantee breaks (need edit-distance-specific techniques).- Hash collisions: rolling-hash collisions cause false positives (you’ll verify and discard most). Use strong 64-bit mods (e.g., 2**61-1) or double hashing to make probability negligible.- Block size choice: larger blocks → fewer accidental matches → fewer verifications but slightly higher chance of missing matches if we allowed indels. Smaller blocks → more candidate windows (more verifications) but more robust to localized errors.- Verification cost vs filter strictness: increasing t (splitting into >k+1 blocks) tightens filter (reduces false positives) but increases per-char hashing overhead and bookkeeping.

Practical tips:- Use two independent hashes (double hashing) to practically eliminate collisions.- Early-abandon verification and compare bytes, not heavy string copies — work on the circular buffer.- If edit distance needed, use q-grams or Ukkonen-style banded verification instead of direct partitioning.

MediumTechnical

53 practiced

Implement Rabin-Karp in Python: rabin_karp_search(text: str, pattern: str, base: int = 256, mod: int = 2**61-1) -> List[int]. Use a rolling hash and demonstrate how you update the hash in O(1). Explain how you handle hash collisions and the impact of modulus choice on false positives.

Sample Answer

Approach: Use a rolling polynomial hash (base^i * char) mod M. Compute pattern hash and initial window hash, then slide: remove leading char and add trailing char in O(1) using precomputed base^(m-1) mod M. On hash match, verify by direct string compare to avoid false positives from collisions.

python

from typing import List

def rabin_karp_search(text: str, pattern: str, base: int = 256, mod: int = 2**61-1) -> List[int]:
    """Return list of starting indices where pattern occurs in text."""
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n+1))
    if m > n:
        return []

    # helper: map char -> int
    def code(c): return ord(c)

    # precompute base^(m-1) % mod for removing leading char
    power = pow(base, m-1, mod)

    # initial hashes
    pat_hash = 0
    win_hash = 0
    for i in range(m):
        pat_hash = (pat_hash * base + code(pattern[i])) % mod
        win_hash = (win_hash * base + code(text[i])) % mod

    matches = []
    for i in range(n - m + 1):
        if win_hash == pat_hash:
            # verify to avoid false positive due to collision
            if text[i:i+m] == pattern:
                matches.append(i)
        if i < n - m:
            # remove leading char, multiply inverse effect by base, and add next char
            lead = (code(text[i]) * power) % mod
            win_hash = (win_hash - lead) % mod  # remove leading
            win_hash = (win_hash * base + code(text[i + m])) % mod  # shift and add
    return matches

Key points:- Rolling update is O(1): subtract lead*base^(m-1), multiply by base, add new char.- Verify on hash match to handle collisions.- Time: average O(n + m) with string checks only on hash matches; worst-case O(n*m) if many collisions.- Space: O(1) extra.- Modulus choice: large prime (e.g., 2**61-1, a Mersenne prime) reduces collision probability and avoids overflow when using 64-bit ops. For cryptographic-level safety or adversarial inputs, use double hashing (two different moduli) or a stronger hash to practically eliminate false positives.

MediumTechnical

59 practiced

Implement KMP in Python: write find_all_kmp(text: str, pattern: str) -> List[int] that returns all starting indices of overlapping matches. Your implementation should compute the prefix-function in O(m) and perform the search in O(n+m). Handle edge cases: empty pattern, pattern longer than text, and Unicode characters.

Sample Answer

To solve this, compute the prefix-function (pi) for the pattern in O(m) then run the KMP automaton over the text in O(n). Handle edge cases: empty pattern (every index is a match), pattern longer than text (no matches), and Unicode is naturally supported by Python str.

python

from typing import List

def compute_prefix(pattern: str) -> List[int]:
    m = len(pattern)
    pi = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
            pi[i] = j
    return pi

def find_all_kmp(text: str, pattern: str) -> List[int]:
    n, m = len(text), len(pattern)
    if m == 0:
        # By convention, return all starting indices (including n) for empty pattern
        return list(range(n + 1))
    if m > n:
        return []
    pi = compute_prefix(pattern)
    res = []
    j = 0  # current matched length in pattern
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = pi[j - 1]
        if text[i] == pattern[j]:
            j += 1
            if j == m:
                res.append(i - m + 1)  # match starts at this index
                j = pi[j - 1]         # allow overlapping matches
    return res

Key points:- compute_prefix runs in O(m); search runs in O(n).- Space O(m) for pi plus output list.- Works with Unicode because Python strings are Unicode-aware.- Edge cases covered: empty pattern returns all indices 0..n; pattern longer than text returns [].- Overlapping matches are returned by resetting j to pi[j-1] after a full match.

HardTechnical

49 practiced

Given millions of user search queries, design an algorithm to detect and cluster near-duplicate queries (typos, reordered words, paraphrases). Compare shingling+MinHash+LSH, edit-distance clustering, and embedding-based approaches. Discuss scalability, accuracy, and which approach you'd pick for real-time deduplication.

Sample Answer

Requirements & constraints:- Input: millions/day search queries (short text), must detect near-duplicates (typos, reordering, paraphrase).- Goals: high recall for near-duplicates, precision to avoid false merges, latency requirement (real-time dedup for UX), operate at web scale, cost-bounded.

Comparison of approaches

1) Shingling + MinHash + LSH- What: Tokenize into k-grams (words or chars), compute MinHash signatures, use LSH to bucket similar signatures.- Accuracy: Good for reorderings and partial overlaps; character n-grams handle typos; struggles with semantic paraphrase (different words same meaning).- Scalability: Very scalable and sublinear lookup — signatures are small, LSH buckets allow constant-time candidate retrieval on avg. Easy to parallelize and index in a key-value store.- Latency: Low — suitable for near-real-time lookups.- Cost/Complexity: Moderate (tuning k, number of hashes/LSH bands). Deterministic behavior aids debugging.

2) Edit-distance clustering (e.g., BK-tree, hierarchical clustering with Levenshtein)- What: Compute pairwise edit distances to cluster typos and small edits.- Accuracy: Excellent for character-level typos and small edits; fails on reordered words/paraphrase where distance is high.- Scalability: Poor for millions; exact pairwise is quadratic. BK-trees or thresholded joins help but still costly for high cardinality and variable lengths.- Latency: High for real-time at scale unless prefiltered heavily.- Cost/Complexity: High compute; hard to parallelize for low-latency.

3) Embedding-based approaches (sentence embeddings + ANN)- What: Use transformer or fast sentence encoders (SBERT, FastText) to embed queries, then approximate nearest neighbor (Faiss/HNSW) for clustering.- Accuracy: Best at semantic paraphrases and synonyms; handles reordering; less reliable on minute character typos unless trained/augmented.- Scalability: ANN indices like HNSW or IVF+PQ scale to millions with sub-ms queries; index build and updates more complex.- Latency: Low for inference + ANN lookup; embedding computation adds cost per query but can be optimized (smaller models, caching).- Cost/Complexity: Higher (model inference cost, periodic reindexing), but high recall for semantics.

Recommendation for real-time deduplication- Hybrid approach: 1. Tier 1 (fast exact + shingle LSH): low-cost hashing and LSH on char n-grams to catch typos, reorderings, and high-overlap queries with very low latency. 2. Tier 2 (embedding + ANN): for candidates not matched in Tier 1 or for long-tail paraphrase detection, compute a lightweight embedding and query an ANN index. 3. Post-filter: apply simple edit-distance or normalized-string heuristics to avoid false merges (e.g., numeric tokens, entity differences).- Rationale: Combines scalability and low latency of MinHash+LSH with semantic power of embeddings. Keeps compute and cost manageable by only embedding when necessary. Monitor precision/recall, tune thresholds, and periodically re-evaluate models/indexes.

Metrics & operational notes- Track recall@k, precision, and false-merge rate; measure latency P95.- Use streaming batch updates (mini-batches) to ANN index; use caching for hot queries.- Privacy/regulatory: ensure embeddings don't leak PII; apply normalization or token masking.

This hybrid delivers the best trade-off: MinHash+LSH for speed and typos; embeddings for semantics; edit-distance as a lightweight validator.

Unlock Full Question Bank

Get access to hundreds of String Algorithms and Pattern Matching interview questions and detailed answers.

Join thousands of developers preparing for their dream job.