Fundamental Algorithms and Techniques Questions

Covers core algorithmic concepts and problem solving patterns commonly assessed in technical interviews. Topics include searching algorithms such as binary search; sorting algorithms such as merge sort and quick sort; graph traversal methods such as breadth first search and depth first search; recursion and divide and conquer techniques; greedy heuristics; and dynamic programming including memoization and tabulation. Also includes implementation patterns such as two pointers, sliding window, prefix sums, and divide and conquer composition, as well as practical considerations like in place versus out of place implementations, stability for sorting, recursion stack and memory usage, and amortized analysis. Candidates should be able to implement these algorithms correctly, explain correctness and trade offs, analyze time and space complexity using Big O notation for best case average case and worst case, select appropriate approaches given input constraints, combine patterns to solve composite problems, and optimize or refactor solutions while handling edge cases.

MediumTechnical

73 practiced

Implement a Disjoint Set Union (Union-Find) data structure in Python with path compression and union by rank. Provide methods find(x) and union(x,y) and analyze why operations are nearly O(1) using inverse Ackermann notation. Give a sample use case for clustering or deduplication in data pipelines.

Sample Answer

To implement Disjoint Set Union (Union-Find) with path compression and union by rank, keep parent and rank arrays. find(x) compresses the path so future finds are fast; union(x,y) attaches the smaller-rank tree under the larger-rank tree. This makes operations amortized almost O(1) — formally O(α(n)) where α is the inverse Ackermann function, which grows <= 5 for any practical n.

python

class UnionFind:
    def __init__(self, n):
        # parent[i] = parent of i; rank[i] approx tree depth
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # optional: number of disjoint sets

    def find(self, x):
        # Path compression: make each node on path point to root
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        # Union by rank: attach smaller tree under larger
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False  # already connected
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1
        self.count -= 1
        return True

    def connected(self, x, y):
        return self.find(x) == self.find(y)

Key points:- Path compression flattens trees during find, making subsequent finds constant-time in practice.- Union by rank keeps tree height small.- Time complexity: amortized O(α(n)) per operation, where α(n) ≤ 5 for any realistic n, so effectively constant.- Space: O(n).

Edge cases:- Inputs outside [0,n-1] should be validated.- If elements are non-integer IDs, map them to integer indices (hash map).

Use case (deduplication / clustering in data pipelines):- Problem: deduplicate user records across datasets using pairwise similarity matches (email match, phone match, fuzzy-name match). For each detected match (a, b) emit union(a_id, b_id). After processing all matches (e.g., in a Spark job), call find(id) to assign canonical cluster ids for downstream joins or merge logic. Union-Find scales well for millions of items and many merge operations because of its near-constant amortized cost.

MediumTechnical

64 practiced

Describe algorithms to find the top k heavy hitters in a fast data stream using limited memory. Compare Count-Min Sketch, Space-Saving (Misra-Gries), and exact heap approaches. Explain error bounds, memory vs accuracy tradeoffs and give pseudocode for Space-Saving or Misra-Gries.

Sample Answer

Approach summary:- Problem: given a high-rate stream of items, report top-k heavy hitters using bounded memory.- Options trade between accuracy, probabilistic guarantees, and memory.

Algorithms and comparisons

1) Count-Min Sketch (CMS)- Structure: d x w array of counters with d hash functions. On arrival, increment counters at each row/hash.- Query: estimated count = min over d counters for the key.- Error bound: overestimate only; with w = ceil(eps^-1) and d = ceil(ln(1/delta)), estimate f̂(x) ≤ f(x) + eps * N with probability ≥ 1 - delta (N = total items).- Memory: O(1/eps * log(1/delta)). Good for many distinct keys; faster, simple merges. Cannot directly give exact top-k without extra bookkeeping; you scan candidate universe or maintain a heap of top estimates (may include false positives).

2) Misra-Gries (Space-Saving family; deterministic)- Structure: maintain at most m counters (often m = k). For each incoming item: - If item in counters: increment its count. - Else if counters < m: add item with count=1. - Else: decrement all counters by 1 (or replace min counter in Space-Saving variant).- Guarantee (Misra-Gries): for parameter m, reported count ĉ(x) satisfies ĉ(x) ≤ f(x) and f(x) ≤ ĉ(x) + N/(m+1). So error ≤ N/(m+1).- Space-Saving variant improves practical accuracy: when full, replace the minimum-counter entry with new key and set its count = min_count + 1; provides tighter empirical error and simpler per-item update using a min-heap or doubly-linked buckets.- Memory: O(m) = O(k). Deterministic bounded error; ideal when you need small memory and deterministic guarantees.

3) Exact heap (naive/top-k with hashmap + heap)- Keep a hashmap of counts for every distinct key; maintain a min-heap of size k for top-k.- Accuracy: exact.- Memory: O(U) where U = number of distinct keys (can be huge). Not feasible for high-cardinality streams.

Memory vs accuracy tradeoffs- Exact counters: best accuracy (exact) but memory scales with distinct keys.- Misra-Gries/Space-Saving: deterministic bounded error proportional to N/m; memory O(m). Good for strict memory budgets and deterministic guarantees.- CMS: tunable probabilistic additive error epsilon*N, with memory independent of distinct keys; mergeable and fast. But CMS overestimates and needs candidate filtering to get top-k (may produce false positives).

When to choose:- Small memory & deterministic bound: Misra-Gries/Space-Saving.- Very high cardinality, need mergeability across machines: Count-Min Sketch.- When you can afford storing all keys: exact heap.

Pseudocode — Misra-Gries (m counters)

python

# Misra-Gries algorithm (m counters)
def misra_gries(stream, m):
    # counters: dict key -> count
    counters = {}  # at most m keys
    for item in stream:
        if item in counters:
            counters[item] += 1
        elif len(counters) < m:
            counters[item] = 1
        else:
            # decrement all counts by 1 and remove zeros
            keys_to_delete = []
            for k in list(counters.keys()):
                counters[k] -= 1
                if counters[k] == 0:
                    keys_to_delete.append(k)
            for k in keys_to_delete:
                del counters[k]
    return counters  # candidates with estimated counts (lower bounds)

Notes and practical tips- After Misra-Gries, to get true top-k, you often make a second pass over stored candidates to get exact counts (if feasible).- Space-Saving variant is recommended in practice for better precision; implement with hashmap + min-heap or bucket lists for O(log m) or amortized O(1) updates.- Combine CMS with a small heap of candidate keys discovered from sampling or MG to reduce false positives.- Choose parameters by acceptable additive error (eps) or by memory budget m: error ~ N/(m+1) for MG, and ~ eps*N for CMS.

MediumSystem Design

74 practiced

You need to merge k sorted files on disk into a single sorted stream when each file is too large to fit in memory and you have limited RAM. Describe a k-way merge algorithm including how to manage buffers, use a min-heap, minimize disk I/O and handle very large k that does not fit heap memory. Outline complexity and practical I/O tuning considerations.

Sample Answer

Requirements & constraints:- k sorted files on disk; total data >> RAM. Need a single sorted output stream.- Limited RAM M. Minimize disk I/O and CPU. k may be very large (k' such that keeping one heap node per file exceeds memory).

High-level approach:- External k-way merge using buffered reads + a min-heap (or loser tree) over the current head element of each file. If k is too large for one pass, do hierarchical (multi-pass) merging grouping files.

Design details:1. Buffers:- Allocate a small read buffer (B bytes, e.g., multiples of filesystem block / page size) per input stream and one write buffer for output. Choose B so that k*B + output_buffer <= M.- Read file data in blocks asynchronously (aio/prefetch). Fill buffers with a block at a time and keep a pointer to the next record.- Use memory-mapped I/O (mmap) or large sequential read with OS readahead if random access is limited.

2. Min-heap / priority structure:- Maintain a min-heap keyed by the current head record from each file. On pop, emit to output buffer, advance that file's pointer; when its buffer is exhausted, issue an asynchronous read to refill.- Use a loser tree (tournament tree) instead of a binary heap to reduce comparisons constant factor: winner selection in O(1) amortized per output with O(log k) updates.

3. Minimizing disk I/O:- Ensure reads are large sequential block reads (not record-by-record). Read chunks into memory buffers; process many records before issuing another read.- Use write buffering and flush when full.- Use asynchronous I/O and multiple outstanding requests to hide latency.- Compress on-disk runs (if CPU allows) to reduce bytes read.

4. Handling very large k:- If k*node_size > M, do multi-level merging: - Group files into batches of size g where g*B + heap_overhead <= M. - Perform parallel/serial g-way merge producing intermediate runs; repeat merging intermediate runs until single output remains (multi-pass external merge). Choose g (fan-in) to minimize passes: passes ≈ ceil(log_g k). - Alternatively use an on-disk priority queue (B-tree or buffer tree) but multi-pass grouping is simpler and I/O-efficient.- Use parallelism: merge independent groups concurrently if I/O bandwidth allows.

Complexity:- CPU comparisons: O(N log k) total comparisons (loser tree reduces constant).- Disk I/O: roughly read N input bytes + write N output bytes, but cost depends on block size and number of passes. With p passes, bytes transferred ≈ (p+1) * N.- Memory: O(k) for heap nodes + k*B buffers (or O(g) per pass if grouping).

Practical tuning tips:- Set buffer B to be a few MB (aligned to FS block) to maximize sequential throughput and readahead efficiency.- Choose g=max fan-in that fits M to minimize passes; trade-off: larger g increases heap overhead.- Use asynchronous I/O and multithreaded readers to keep disks saturated.- Monitor IOPS vs throughput: prefer fewer large sequential reads over many small ones.- If storage supports it, stripe files across disks to increase parallel transfer bandwidth.- Consider directly streaming into downstream processing (avoid writing intermediate results) to save I/O.

Edge cases:- Very skewed file sizes: process largest files first or adjust buffer allocation proportionally.- Variable-length records: ensure buffer boundary logic handles partial records and carryover.- Fault tolerance: write intermediate runs atomically and resume merging from checkpoints.

This design balances limited RAM, minimizes disk seeks by favoring large sequential IO, and handles very large k via hierarchical merging or on-disk structures.

MediumTechnical

87 practiced

Implement Kahn's algorithm to produce a topological ordering of a directed acyclic graph and detect cycles. Write code or pseudocode that returns a topological order list if possible or reports a cycle. Analyze time and space complexity and discuss applications such as job scheduling and dependency resolution in ETL pipelines.

Sample Answer

To produce a topological ordering and detect cycles, Kahn’s algorithm repeatedly removes nodes with zero in-degree and appends them to the output. If at the end some nodes remain, a cycle exists.

python

from collections import defaultdict, deque
def kahn_topological_sort(edges):
    """
    edges: iterable of (u, v) directed edges meaning u -> v
    Returns (order_list, None) if DAG, or (None, cycle_nodes) if cycle detected.
    """
    adj = defaultdict(list)
    indeg = defaultdict(int)
    nodes = set()
    # Build graph
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
        nodes.add(u); nodes.add(v)
    # initialize zero in-degree queue (include isolated nodes)
    q = deque([n for n in nodes if indeg[n] == 0])
    order = []
    while q:
        n = q.popleft()
        order.append(n)
        for nei in adj[n]:
            indeg[nei] -= 1
            if indeg[nei] == 0:
                q.append(nei)
    if len(order) == len(nodes):
        return order, None
    # cycle detected: nodes with indeg > 0 are in or reachable from cycles
    cycle_nodes = [n for n in nodes if indeg[n] > 0]
    return None, cycle_nodes

Key concepts:- Start from nodes with indegree 0, remove them, decrement neighbors’ indegree.- If processed count < total nodes, remaining nodes form/are affected by cycle.

Time and space complexity:- Time: O(V + E) — each node/edge processed once.- Space: O(V + E) for adjacency list and indegree map.

Edge cases:- Graph with isolated nodes (handled).- Parallel edges: indegree counts multiples appropriately.- Large graphs: use streaming / external memory or partitioned processing for very large pipelines.

Alternatives:- DFS-based topological sort with recursion and back-edge cycle detection (can risk stack overflow on deep graphs).

Applications for Data Engineering:- Job scheduling: order ETL tasks respecting data dependencies; detect cycles in DAG of jobs before scheduling to avoid deadlock.- Dependency resolution: ensure tables/views are built in correct order; detect cyclic table/view definitions.- Orchestration systems (Airflow, Luigi): validate DAGs, generate execution order, and fail early if cycles exist.

HardTechnical

131 practiced

Design an algorithm or data structure to compute streaming quantiles (for example median or 90th percentile) with bounded memory. Describe Greenwald-Khanna and t-digest approaches, their error guarantees, mergeability, and practical parameter choices for 1% error on high throughput streams.

Sample Answer

Start by clarifying goal: we need bounded-memory summaries that answer rank queries (quantiles) on a stream with controllable error ε (e.g., 1% ≈ 0.01 of rank). Two practical, widely-used methods are Greenwald–Khanna (GK) and t-digest — they trade deterministic guarantees vs practical accuracy for non-uniform error and mergeability.

Greenwald–Khanna (GK)- Approach: deterministic summary of tuples (value, g, Δ) that maintain rank bounds. On insert, GK appends and occasionally compresses neighboring tuples while preserving invariant that each tuple’s rank interval ≤ εN.- Error guarantees: provable deterministic bound: reported rank r̂ satisfies |r̂ − r| ≤ εN (so quantile error ≤ ε). Good for uniform rank error.- Memory/time: O(1/ε) tuples worst-case; insert amortized O(1) with periodic compress; space bound is linear in 1/ε.- Mergeability: native GK is not trivially mergeable without increasing error; you can merge by replaying one summary into another (costly) or use specialized variants that sacrifice simplicity. Not cheap for distributed aggregation.- Practical tuning: for 1% rank error, set ε = 0.01; expect ~O(100)–O(200) tuples per summary depending on data distribution and implementation. Use for cases needing strict deterministic rank bounds.

t-digest- Approach: probabilistic, cluster-based summary optimized for accurate tail quantiles. Maintains centroids (mean, weight) and a scale function k(q) to make clusters near tails small. Insert merges point into nearest centroid; periodic compression keeps centroid count bounded.- Error guarantees: no strict deterministic rank bound; empirical error is small for quantiles, especially tails. Theoretical work gives probabilistic bounds but not the simple εN guarantee. It targets lower absolute quantile error near 0/1 and slightly larger near median.- Memory/time: memory roughly O(δ) centroids where δ is compression factor (commonly 100–1000). Insert is amortized O(log m) or O(1) with buffering + batch compress.- Mergeability: highly mergeable — you can merge two t-digests by feeding centroids into a new digest; excellent for distributed systems (map-reduce, streaming windows).- Practical tuning for 1% target: choose compression parameter compress ≈ 200–500. For high-throughput streams, use a buffering strategy (accumulate ~1k points, then batch-compress) for speed. Empirically, compress=200 often yields <1% quantile relative error for many distributions; increase to 500 for heavy-tailed or adversarial data.- Notes: t-digest provides much better relative error at extremes; median error typically far below 1% in practice.

Which to pick?- If you need strict deterministic rank guarantees (auditable bounds), use GK with ε=0.01. Accept less-friendly merger behavior; handle distributed aggregation by replaying or using hierarchical merging with careful error composition.- If you need production scalability, low memory, and easy merge/parallel reduce with excellent tail accuracy, use t-digest with compress 200–500 and buffering. Monitor with periodic accuracy checks on sampled full data to validate error for your data skew.Operational tips- Always test against representative data (simulated tails/heavy skew). Track errors by keeping a sliding sample and comparing.- For distributed pipelines: use t-digest for map-reduce-friendly summaries. If using GK, consider deterministic sketches that are mergeable (e.g., KLL sketch) — KLL gives provable ε-rank bounds with better mergeability and space than GK; consider KLL as a third option (space O(1/ε log log 1/ε)).- Memory footprint: for 1% target, expect tens to a few hundreds of centroids/tuples per worker; multiply by parallelism to size memory.This balances correctness, mergeability, and production practicality for high-throughput streams.

Unlock Full Question Bank

Get access to hundreds of Fundamental Algorithms and Techniques interview questions and detailed answers.

Join thousands of developers preparing for their dream job.