Recognizing Patterns and Selecting Algorithms Questions

Ability to recognize problem patterns and know which algorithm/data structure is appropriate. Includes pattern matching like 'this looks like a sliding window problem' or 'this is a backtracking problem'.

HardTechnical

82 practiced

Problem-solving / Data-structures: Maintain connectivity or shortest paths on a dynamic graph with edge insertions and deletions. Explain when union-find suffices (insertions only), and when more advanced data structures like link-cut trees or Euler-tour trees are necessary. Discuss amortized complexity and practical limitations.

Sample Answer

Situation: You're asked to maintain connectivity and/or shortest paths on a graph that changes by edge insertions and deletions. Here's a concise, interview-ready explanation that covers when simple disjoint-set (union‑find) is enough, when dynamic-tree structures are needed, amortized complexities, and practical trade-offs.

Answer:

- When union‑find suffices - If the graph only experiences edge insertions (incremental connectivity), union‑find (Disjoint Set Union with union by rank + path compression) is ideal. It answers “are u and v connected?” in practically O(α(n)) amortized time per operation (α is inverse Ackermann, ≈ constant). It cannot handle deletions: once two components are merged you lose information about which specific edges caused connectivity.

- When link‑cut trees / Euler‑tour trees are necessary - If you must support deletions (fully dynamic connectivity) on a forest (i.e., graph remains acyclic or you maintain a spanning forest), you need a dynamic forest structure that supports link (add tree edge), cut (remove tree edge), and connected(u,v) queries. - Link‑cut trees (Splay-based) and Euler‑tour trees (ET-trees implemented with balanced BSTs) both support these operations in O(log n) amortized time per operation for forests. ET-trees are often simpler to implement for subtree/aggregate queries; link‑cut gives more flexible path operations. - For general graphs (cycles allowed) you must maintain a dynamic spanning forest and handle replacement edges on deletions. Deterministic polylogarithmic solutions exist (e.g., Holm–de Lichtenberg–Thorup) with amortized O(log^2 n) per update; randomized approaches can do expected O(log n) or O(log^2 n).

- Shortest paths (dynamic distances) - Shortest paths are far harder. For incremental single-source or all-pairs you can sometimes run incremental Dijkstra/BFS from affected sources; amortized bounds depend on edge weights and update pattern. - Decremental (deletions-only) or fully dynamic APSP/SRSF have sophisticated algorithms (e.g., Thorup, King, Demetrescu-etc.) with polylog or sqrt trade-offs but large constants. In practice, for sparse or small batches, rerunning Dijkstra/BFS from affected nodes is common.

- Amortized complexity summary - Union‑find (insertions only): near O(α(n)) per op. - Link‑cut / ET‑tree (forest link/cut/conn): O(log n) amortized per op. - Holm et al. fully dynamic connectivity (general graphs): O(log^2 n) amortized. - Dynamic shortest-path algorithms: varied — from near-linear rebuilds to polylog guarantees with high constants.

- Practical limitations & engineering trade-offs - Implementation complexity: link‑cut trees and Holm et al. are nontrivial and bug-prone; ET-trees are easier. - Constants & memory: theoretical polylog algorithms often have big constants; for typical engineering workloads simpler rebuilding or batching (recompute BFS/Dijkstra on batch updates, or use decremental with lazy rebuild) can be faster and easier. - Deterministic vs randomized and amortized vs worst-case: choose based on SLAs. If worst-case latency matters (real‑time system), amortized bounds may be unacceptable. - Engineering heuristics: maintain a spanning forest + adjacency lists of non-tree edges; on deletion, search for replacement via limited BFS/levels; rebuild from scratch after many updates; or use libraries (Boost Graph, existing ET implementations).

Recommendation: Use union‑find for insert‑only. For deletions but forest-only problems, use ET‑trees or link‑cut trees. For fully dynamic general graphs, prefer well-tested libraries or simpler amortized approaches (Holm et al.) only if the scale/requirements justify complexity; otherwise use batching, incremental recomputation, or approximate answers.

HardSystem Design

88 practiced

System-design / Algorithms: You must find the most frequent items across terabytes of log data. Explain when to use exact approaches (external sort + merge) versus approximate streaming algorithms (Count-Min Sketch, Space-Saving), and outline a MapReduce approach that produces exact top-k per shard and merges results to final top-k.

Sample Answer

Requirements & trade-offs:- Functional: find global top-k most frequent items across terabytes of logs.- Non-functional: bounded memory, latency vs accuracy trade-off, cost.

When to use exact vs approximate:- Exact (external sort + merge, or hash-based counting with partitioning) when: correctness is mandatory (billing, compliance), k small relative to unique keys, or you can afford I/O and storage cost and longer latency. Complexity: O(N log N) for external sort or O(N) + disk-shuffle for partitioned counting; high IO and storage.- Approximate (Count-Min Sketch, Space-Saving, Lossy Counting) when: near-real-time insight, memory constrained, huge cardinality, or occasional bounded error acceptable. CMS gives one-sided error with sublinear memory; Space-Saving yields accurate top-k for heavy hitters with bounded error guarantees. Use sketches for streaming/low-latency dashboards.

Exact MapReduce approach (produce exact top-k per shard then merge):1. Map (sharding): Hash each log key to R reducers (partition by key). Emit (key,1).2. Combiner: locally aggregate counts per mapper to reduce network I/O.3. Reduce: each reducer receives all occurrences for its key; compute exact count per key. Keep reducer-local top-k (min-heap size k) while scanning counts (or simply emit all counts if feasible).4. Emit reducer-local top-k items (key, count).5. Final merge job (or single coordinator): - Gather all reducer-local top-k lists (R * k items). - Use a max-heap or sort these O(Rk) items to compute global top-k exactly (since all keys are globally counted by reducers, no duplicates across reducers).Optimization notes:- If keys are partitioned by hash, each key goes to exactly one reducer so final merge is trivial: collect and pick top-k across reducers.- If you instead pre-aggregate approximate per-shard, you must re-count candidates or use sketches with conservative merge.Scalability & failure:- Use combiners, compression, and adjustable partition count. For extreme cardinality, combine approximate sketches for pre-filtering heavy-hitter candidates, then run exact counts only for candidates to reduce work.

EasyTechnical

76 practiced

Given an array of positive integers and a target sum, explain how you would recognize that this is a sliding-window problem. Describe the key properties you look for (e.g., contiguous subarray requirement, ability to expand/contract window, non-negative items) and outline an O(n) algorithm sketch. Example to reason about: arr = [2, 1, 3, 2], target = 5.

EasyTechnical

93 practiced

Theoretical: For prefix-search and autocomplete, compare tries, hash tables, and sorted arrays (binary search). Discuss memory usage, latency for prefix queries, worst-case and average-case trade-offs, and when to prefer each structure in production systems.

Sample Answer

Definition: Prefix-search/autocomplete returns all (or top-k) strings starting with a given prefix. Common implementations: trie (prefix tree), hash table, sorted array with binary search.

Key properties:- Trie - Memory: High — one node per character (can be optimized with compressed/DAWG/radix trie). Pointer overhead dominates for sparse alphabets. - Latency for prefix query: O(p + m) where p = prefix length, m = number of reported items (traverse p chars then DFS). Lookup of prefix is deterministic and fast. - Worst/avg trade-offs: Worst-case memory heavy; average-case lookup O(p). Good for many shared prefixes, incremental search, and autocomplete suggestions. - When to prefer: Real-time prefix matching, incremental typing, suggestions with common prefixes, need to support lexicographic iteration.

- Hash table (hash set/map of full strings or buckets by prefix) - Memory: Moderate — stores full strings + hash overhead. If keyed by full string only, no inherent prefix support. - Latency: Exact-match O(1) average. Prefix queries require scanning buckets or maintaining additional prefix keys (e.g., store all prefixes) which explodes memory or costs O(n) scan. - Worst/avg trade-offs: Average exact lookups fast; prefix operations are poor unless you precompute prefixes (memory blowup). - When to prefer: Fast exact-match lookups, membership checks, or when autocomplete is implemented by querying a backend service that returns candidates; not ideal for native prefix enumeration.

- Sorted array / ordered list + binary search - Memory: Low — compact storage of strings contiguous in memory. - Latency: Find prefix range via two binary searches: O(p log n) to compare prefixes (string compare cost proportional to p), then scan range to collect results O(m). Binary searches are cache-friendly. - Worst/avg trade-offs: Predictable memory and latency; slower than trie for very short p and huge datasets but simpler and often faster in practice due to cache locality. - When to prefer: Read-heavy systems, static datasets, memory-constrained environments, or where you need lexicographic order and range queries.

Summary / Guidance:- Use trie (or compressed trie) when low-latency incremental prefix lookup and many shared prefixes matter and memory/complexity is acceptable.- Use sorted array when dataset is relatively static, you want low memory and excellent cache performance, and prefix queries can tolerate O(log n) cost.- Use hash table for exact matches or as part of hybrid designs (hash for top-k popularity, sorted/trie for fallback). In production, consider compressed tries, prefix indexes in databases, or combining structures with caching and scoring for autocomplete.

MediumTechnical

88 practiced

Problem-solving: You see a problem that asks 'every number appears twice except one that appears once'. Recognize the bit-manipulation/XOR pattern. Describe the XOR-based solution (single pass, O(1) extra space) and generalize to the case where elements appear three times except one that appears once: how would you approach it?

Sample Answer

For the “every number appears twice except one” pattern: use XOR. XORing all elements cancels pairs because x ^ x = 0 and x ^ 0 = x, so the single leftover remains.

Example (single-pass, O(1) extra space):

python

def single_number(nums):
    res = 0
    for x in nums:
        res ^= x
    return res

Time: O(n), Space: O(1).

Generalization: “every number appears three times except one appears once.” XOR alone fails. Use bitwise digit counting mod 3: for each bit position (0..31 for 32-bit ints) count how many numbers have that bit set, take count % 3 — the remainder gives the bits of the unique number. Reconstruct the result from those remainders. This is still O(n) time, O(1) extra space (constant 32 counters).

Efficient constant-space variant (two accumulators) tracks bits appearing once and twice:

python

def single_number_triplets(nums):
    ones = 0
    twos = 0
    for x in nums:
        ones = (ones ^ x) & ~twos
        twos  = (twos  ^ x) & ~ones
    return ones

Explanation: ones holds bits seen once modulo 3; twos holds bits seen twice modulo 3. When a bit reaches three occurrences it’s cleared from both. Time: O(n). Space: O(1).

Edge cases: negative numbers — ensure fixed bit-width behavior (use masking) in languages with infinite-precision integers.

Unlock Full Question Bank

Get access to hundreds of Recognizing Patterns and Selecting Algorithms interview questions and detailed answers.

Join thousands of developers preparing for their dream job.