Algorithms and Data Structures Questions

Comprehensive understanding of core data structures such as arrays, linked lists, stacks, queues, hash tables, trees, heaps, and graphs, and fundamental algorithms including sorting, searching, traversal, string manipulation, and graph algorithms. Ability to analyze and compare time and space complexity using asymptotic notation such as Big O, Big Theta, and Big Omega, and to reason about trade offs between different approaches. Skills include selecting the most appropriate data structure for a problem, designing efficient algorithms, applying algorithmic paradigms such as divide and conquer, dynamic programming, greedy methods, and graph search, and implementing correct and robust code for common interview problems. At more senior levels, this also covers optimizing for large scale through considerations of memory layout, caching, amortized analysis, parallelism and concurrency where applicable, and profiling and tuning for performance in realistic systems.

MediumTechnical

100 practiced

Write Python code to perform an in-place partition step used by quickselect (partition around a pivot) and explain how quickselect finds the k-th smallest element in average O(n) time. Discuss worst-case behavior and practical improvements to avoid pathological pivots (median-of-medians, sampling).

Sample Answer

To partition in-place around a pivot (Lomuto-style) and use Quickselect to find the k-th smallest:

1) Approach: choose a pivot, partition array so elements <= pivot are left, > pivot right; then recurse only into the side that contains the k-th element.

python

def partition(arr, lo, hi, pivot_index):
    """
    In-place partition arr[lo:hi+1] around arr[pivot_index].
    Returns the final index of the pivot.
    """
    arr[pivot_index], arr[hi] = arr[hi], arr[pivot_index]  # move pivot to end
    pivot = arr[hi]
    store = lo
    for i in range(lo, hi):
        if arr[i] <= pivot:
            arr[store], arr[i] = arr[i], arr[store]
            store += 1
    arr[store], arr[hi] = arr[hi], arr[store]  # move pivot to its final place
    return store

def quickselect(arr, k, lo=0, hi=None):
    """
    Find k-th smallest (0-based k). Modifies arr in-place.
    Average O(n) time, O(1) extra space (ignoring recursion).
    """
    if hi is None:
        hi = len(arr) - 1
    if not (0 <= k <= hi):
        raise IndexError("k out of range")
    while lo <= hi:
        # simple pivot choice: randomize to avoid deterministic worst-case
        import random
        pivot_index = random.randint(lo, hi)
        pivot_final = partition(arr, lo, hi, pivot_index)
        if pivot_final == k:
            return arr[pivot_final]
        elif k < pivot_final:
            hi = pivot_final - 1
        else:
            lo = pivot_final + 1
    return None

Key concepts:- Quickselect only recurses into one partition each step, so expected comparisons sum to O(n).- Average-case O(n): with good pivots, work is geometrically decreasing.- Worst-case O(n^2): occurs with consistently poor pivots (e.g., always min or max).

Practical improvements to avoid pathological pivots:- Randomized pivot (as above) makes worst-case extremely unlikely.- Median-of-medians (deterministic selection) provides guaranteed O(n) worst-case by selecting an approximate median as pivot — more code/overhead but worst-case safe.- Sampling: pick a small sample (e.g., 5-11 elements), use their median as pivot — practical balance between performance and robustness.

Edge cases:- Empty array, k out of range- Many duplicate values (handled by <= in partition)- Large recursion depth avoided by iterative loop above; use tail recursion elimination or iterative control for production.

HardSystem Design

93 practiced

You must maintain per-user distinct count (number of unique items) over a sliding 24-hour window for millions of users, with strict memory limits. Propose a hybrid design using approximate sketches (HLL) for most users, exact counters for heavy users, eviction strategies, hierarchical aggregation, and techniques to bound state size. Explain merging, error budgets, and cold-start behavior.

Sample Answer

Requirements & constraints:- Per-user distinct count over a 24-hour sliding window for millions of users.- Strict memory limits → most users approximate; a small fraction tracked exactly.- Soft real-time reads (query within seconds/minutes).- Mergeable, parallel-friendly, fault-tolerant.

High-level design:- Ingestion writes event {user_id, item_id, ts} into a streaming layer (Kafka).- Per-user state stored as time-partitioned sketches: fixed number of contiguous time buckets (e.g., 24 × 1h or 48 × 30m) to implement sliding window.- For each user-bucket maintain either: - HyperLogLog (HLL) sketch (compact, mergeable) for the majority. - Exact structure (hashset or count-min + exact set) for heavy users.- A coordinator periodically slides window: evict oldest bucket, merge remaining buckets to compute the 24h distinct estimate.

Components & responsibilities:1. Ingest/Router: samples user traffic, applies hot-user detection. Lightweight per-user counters track event volume; if a user exceeds threshold (rate or expected cardinality), mark heavy.2. Stream processors (Flink/Spark Structured Streaming): - Map events into (user_id, bucket_id). - Update per-user-bucket state: update HLL or exact set. - Emit periodic aggregated deltas to long-term store.3. State store: - For HLL: compact serialized sketches (e.g., 1–2 KB per user-bucket depending on precision). - For heavy users: exact sets kept in memory or tiered to Redis/SSD.4. Query layer / Aggregator: - For a request, fetch the user's buckets, merge sketches (or union exact sets), return count. - Support batched/hierarchical aggregation: per-shard partial merges then final.

Memory bounding techniques:- Fixed bucket count = window_size / bucket_size → upper bound on per-user buckets.- Choose HLL precision (p) to meet error budget; trade-off memory vs error.- Cap per-user state size: for non-heavy users, only HLL; for heavy users, set a per-user exact memory cap and use LRU eviction on item IDs when cap exceeded with a "graceful degrade" to HLL fallback.- Global eviction: if total memory usage exceeds budget, progressively increase HLL compression (if supported) or trigger demotion of low-activity heavy users to HLL.

Heavy-user handling:- Criteria: sustained high event rate, or estimated cardinality above threshold.- Heavy users promoted to exact mode; maintain exact sets for recent buckets.- If exact sets grow beyond allowed, snapshot to disk and continue exact up to cap; beyond cap, switch to hybrid: keep top-k exact + HLL for remainder.

Merging & correctness:- HLLs are mergeable by taking register-wise maxima; to compute 24h count, merge the K bucket HLLs for that user and read estimate.- Exact sets: union straightforward.- For heavy users using hybrid (top-k exact + HLL rest): estimate = |exact_set| + HLL_estimate_for_rest (ensure item IDs in exact set are not fed into HLL to avoid double-counting — can be achieved by routing).

Error budgets:- Allocate total allowable relative error ε_total (e.g., 2–5%). Budget split across sources: - HLL estimation error ε_HLL (dominant). - Bucketization temporal error (if using coarse buckets overlapping reduces boundary bias). - Promotion/demotion noise when switching representation — use buffered transition windows and forward compatibility (feed events to both representations during transition period).- Choose HLL precision p so that standard error ≈ 1.04 / sqrt(2^p) <= ε_HLL. Example: p=14 => ~0.8% error, memory ~1.6KB per sketch.

Sliding-window & bucket sizing:- Bucket size trade-offs: - Smaller buckets (e.g., 5–15 min): more accurate window boundary, but more buckets → more state. - Larger buckets (1h): less state, slightly coarser boundary; can use fractional subtraction using overlap if needed.- Use fixed circular buffer per user of N buckets; when time advances, zero/replace oldest bucket.

Cold-start behavior:- New users start in HLL mode with empty buckets. HLL handles sparse data well (low cardinalities have low absolute error).- Hot-detection buffer period: only promote to exact after exceeding threshold for a window to avoid thrashing.- To reduce startup bias, pre-seed HLLs with empty registers rather than null; queries for cold users that have no buckets return zero.

Operational considerations:- Sharding: partition by user_id to localize state and reduce cross-node merges.- Snapshots & recovery: persist serialized per-user-bucket sketches periodically to object store; use changelogs for fast restore.- Backpressure & throttling: if ingestion spikes, sample events for low-priority users and rely on HLL approximation; ensure heavy users always processed exactly.- Testing & monitoring: track empirical error by running ground-truth job for sample users; monitor promotion/demotion rates, memory per shard, tail latencies.

Edge cases:- Very high cardinality bursts — promote quickly and cap exact set size with fallback to HLL.- Duplicated events/timestamps — idempotence required at ingestion (dedupe if possible) or accept duplicates as HLL handles duplicates naturally.- Clock skew — base bucketing on event time with watermarking to place late events into earlier buckets up to configured lateness.

Example numbers (rough capacity planning):- Millions users (5M), bucket count 24, HLL ~1.6KB → worst-case HLL-only = 5M * 24 * 1.6KB ≈ 192TB (too large).- Therefore: most users only have small active buckets: use sparse storage: only store buckets that received events. If active users/hour = 500k, then storage ≈ 500k * 24 * 1.6KB = ~19.2GB (acceptable). Tail users handled exactly with per-user caps.

This hybrid guarantees bounded memory via fixed bucket count, sparse materialization, HLL compactness, and strict promotion/demotion rules while giving exact counts for heavy users and controllable error via HLL precision and explicit error budgeting.

HardSystem Design

91 practiced

Design a streaming deduplication system with exactly-once semantics for events ingested via Kafka, processed by a stream processor (for example Flink). Consider event IDs, state backend choices (RocksDB), state TTL, checkpointing, latency, and how to bound state size while preserving correctness. Describe algorithmic steps and failure recovery behavior.

Sample Answer

Requirements & constraints:- Exactly-once delivery semantics for events ingested from Kafka and output to downstream sinks.- Deduplicate based on event_id (could be UUID).- Bounded state size despite unbounded input.- Use Flink + RocksDB state backend, support failure recovery via checkpointing.- Low processing latency with configurable dedupe window.

High-level design:- Kafka → Flink stream (KeyBy event_id or partitioned key) → Dedup operator (stateful) → downstream sink (Kafka or DB) with EOS (transactions) enabled.

Algorithm (per-key dedupe with bounded retention):1. Key the stream by event_id (or a business key if dedupe window per key).2. In the keyed dedupe operator keep a RocksDB-managed keyed state: a small metadata entry (e.g., firstSeenTimestamp and optional payload hash) per event_id.3. Set state TTL equal to dedupe window W (e.g., 24h or business-defined). Configure RocksDB TTL backend (or Flink TTL) to automatically evict old keys.4. On event arrival: - Check state for event_id: - If absent → treat as new: write state with current processing timestamp, emit event downstream. - If present and within TTL → drop as duplicate. - If present but expired (evicted by TTL) → treat as new.5. Use Flink’s exactly-once checkpointing (aligned or unaligned) with RocksDB snapshots. Sink must support transactions/EOS (Kafka transactional producer or two-phase commit sink) so emitted events on successful checkpoint are committed exactly once.

Bounding state & optimizations:- Use TTL to bound per-event lifetime; state size ≤ incoming unique events within window W.- If W still too large, partition dedupe scope: dedupe per user/session instead of global event_id.- Use compact representations: store only fixed-size hash (e.g., 64-bit) instead of full payload; use probabilistic structures (Counting Bloom filters) for extra compression with configurable false positive rate — but be aware FP causes some false deduplication (not acceptable if strict correctness required).- RocksDB options: enable compaction, set write buffers and memory limits; use incremental checkpoints to reduce snapshot size.

Checkpointing, transactions, and failure recovery:- Enable Flink checkpointing interval tuned to latency/throughput trade-off.- Use Kafka sink with FlinkKafkaProducer in EOS mode (transactions) or TwoPhaseCommitSinkFunction to tie emitted output to checkpoints.- On checkpoint success: Flink commits the sink transaction; RocksDB snapshot persists.- On failure and restart: Flink rolls back to last successful checkpoint. Operator state is restored from RocksDB snapshot. Any in-flight or partially committed sink transactions are aborted by the sink coordinator. Because state + output commit are coordinated via checkpoint, exactly-once is preserved.

Latency considerations:- Shorter checkpoint intervals reduce recovery window but increase overhead. Use unaligned checkpoints for low-latency streaming when network backpressure occurs.- RocksDB I/O tuned (async I/O, proper memory config) to balance throughput and latency.- TTL eviction may run asynchronously; avoid synchronous scans.

Edge cases & correctness:- Clock skew: use Flink processing time or event time consistently; for event-time dedupe, advance watermarks and use timers to remove state when watermark passes event_time + W.- Late events: if event arrives after TTL, it will be treated as new — choose W to cover expected lateness.- Exactly-once requires sink transactional guarantees; if downstream sink cannot do transactions, implement idempotent writes keyed by event_id at sink.

Failure scenarios:- Driver failure before checkpoint commit: on restart, outputs from that failed attempt are not committed; state restored to last checkpoint; duplicates suppressed correctly because only committed state is used.- Kafka producer/transaction failure: transactional abort ensures no partial commits.- RocksDB corruption: rely on periodic checkpoints and durable storage (S3/GCS) for checkpoint files; restart recovers from latest checkpoint.

Trade-offs:- Larger W increases correctness for late arrivals but grows state.- Probabilistic structures reduce state but risk false deduplication.- Keying strategy affects parallelism: keyBy event_id can have high cardinality; consider hashing to balance load.

This design provides exactly-once deduplication using Flink’s state+checkpoint coordination with transactional sinks, RocksDB for durable keyed state, TTL to bound growth, and clear failure recovery semantics.

MediumTechnical

78 practiced

You need to deduplicate billions of incoming IDs in a streaming ingestion pipeline where RAM is limited. Describe how a Bloom filter can be used for deduplication, derive formulas for sizing the filter (bits per element and number of hash functions) given expected n and acceptable false positive rate p, and discuss operational concerns like false positives, inability to delete, and checkpointing.

Sample Answer

Approach (why Bloom): For streaming deduplication with billions of IDs and limited RAM, a Bloom filter provides a compact probabilistic set: membership queries are fast and memory-efficient. It never has false negatives (if an ID is in the filter it may be reported unseen only once), but it has tunable false positives (it may say an unseen ID is duplicate). Use the Bloom filter as the first-stage filter to drop most duplicates in-memory; optionally confirm positives against a slower persistent store if false positives are unacceptable.

Sizing formulas (derive and use):- Let n = expected distinct IDs, p = acceptable false positive rate, m = number of bits, k = number of hash functions.- Optimal bits per element: m = - (n * ln p) / (ln 2)^2 => bits per element b = m/n = - ln p / (ln 2)^2 ≈ -1.44 * ln p- Optimal number of hashes: k = (m / n) * ln 2 ≈ 0.693 * (m/n)Equivalently: k = ln(1/p) / ln 2Example: for n=1e9, p=1e-3 -> b ≈ 10.9 bits/element -> m≈10.9e9 bits (~1.36 GB); k≈7.6 -> use k=7 or 8.

Implementation notes:- Use double hashing (two independent hashes h1,h2) to generate k indices: idx_i = (h1 + i*h2) mod m. This avoids k independent hash computations while retaining quality.- Use bit-packed arrays and CPU-friendly libraries; for distributed workers partition by ID hash so each worker holds a shard of the filter.

Operational concerns- False positives: bloom may wrongly mark new IDs as duplicates — if that’s unacceptable, use a two-tier approach: Bloom filter rejects most; candidates that Bloom says "seen" are verified against persistent store (rocksDB, DynamoDB). This balances memory/latency/cost.- No deletions: standard Bloom can't remove items. Solutions: - Use Counting Bloom (counters per bucket) at higher memory cost to allow deletes. - Use time-windowed rotating Bloom filters: keep W filters (e.g., one per hour). When sliding window advances, drop oldest filter and start fresh—this bounds deduplication to desired retention window.- Checkpointing and recovery: - Persist the bit array (or counting array) periodically to durable storage; bit arrays compress well (gzip). On restart, load bits + k to continue. - For distributed system, Bloom filters for shards can be merged by bitwise OR; use that for aggregator checkpoints. - Ensure consistent hashing and stable worker assignments or include logic to rehydrate filters after rebalance.- Memory/scale trade-offs: - Increasing n or decreasing p increases m linearly; choose acceptable p based on business cost of false positives. - Consider hybrid: bloom for hot, LRU cache or disk-backed store for cold confirmations.- Hash quality and speed: use non-cryptographic fast hashes (Murmur3, xxHash) for throughput; ensure seeds for independent h1,h2.

Edge cases & metrics:- Monitor observed false positive rate by sampling (send a subset to slow exact check) and compare to expected p.- Track bit saturation to know when to resize/rotate; when occupancy grows, p increases—plan for reallocation or rolling resets.

This design gives predictable memory usage, tunable false positives, and operational patterns (rotating filters, checkpoints, two-tier verification) suitable for large-scale streaming deduplication.

HardTechnical

123 practiced

You need to estimate join cardinality between two tables A and B for a query optimizer. Describe algorithmic approaches to estimate selectivity including histograms (equi-depth/equi-width), sketches, sampling, and how to combine column statistics for multi-column predicates. Discuss accuracy challenges with correlated columns and suggestions to mitigate them.

Sample Answer

Start by framing the goal: join cardinality = |A ⋈ B| = ∑_v freqA(v) * freqB(v) over join key values v. Estimating selectivity requires compact summaries of per-column distributions and methods for combining them.

Histogram-based approaches- Equi-width: split domain into fixed-size buckets; store counts. Cheap but poor for skewed data.- Equi-depth (frequency buckets): buckets with equal counts. Better at capturing heavy tails and skew. Store per-bucket min/max/count; for join, approximate overlap between corresponding buckets and multiply densities.- Multi-dimensional histograms (e.g., 2D): capture joint distribution of two columns directly but blow up in space (curse of dimensionality).

Sketches and probabilistic summaries- Count-min sketch: estimate frequencies of values with additive error; useful for high-cardinality keys.- HyperLogLog: estimate distinct counts (useful for estimating join result upper bounds).- Frequent-items (Lossy Counting, Space-Saving): capture heavy hitters explicitly to handle skew in joins.

Sampling- Random row/sample of each table and perform sample join to estimate selectivity; variance can be high for rare join values. Stratified sampling (ensure heavy hitters are represented) reduces variance. Use reservoir sampling or hash-based sampling for streaming/large-scale data.

Combining column statistics / multi-column predicates- Independence assumption: multiply marginal selectivities — fast but wrong when correlated.- Use pairwise joint statistics: store covariance, 2D histograms, or compressed contingency tables for common column pairs to adjust estimates.- Factorized models / graphical models: use Bayesian networks or maximum entropy models to combine low-dimensional joints into higher-dim estimates.

Accuracy challenges and mitigation- Correlation: independence gives large errors. Mitigate by tracking joint stats for columns known to be correlated (foreign-key relationships, temporal correlations), using multi-dimensional histograms or sampling to detect correlation.- Skew and heavy hitters: keep explicit heavy-hitter tables; treat remaining as uniform or use sketches.- High cardinality domains: prefer sketches and sampling over dense histograms.- Data freshness/staleness: maintain incremental/statistics pipelines; sample periodically or update sketches during ETL.- Cost/space trade-offs: prioritize stats for join keys and frequently-queried predicates; use adaptive techniques (on-demand detailed stats when optimizer repeatedly misestimates).

Practical suggestions for a data platform- Maintain per-column histograms + HLL for distinct counts + CMS for frequency estimates.- Track foreign-key relationships and store small joint frequency tables for FK-PK pairs.- Use periodic stratified sampling for complex multi-column predicates and feed corrections into the optimizer (feedback loop).- For distributed systems, compute sketches during ingestion to avoid scanning full tables.

Unlock Full Question Bank

Get access to hundreds of Algorithms and Data Structures interview questions and detailed answers.

Join thousands of developers preparing for their dream job.