Data Structure Selection and Trade Offs Questions

Skill in selecting appropriate data structures and algorithmic approaches for practical problems and performance constraints. Candidates should demonstrate how to choose between arrays lists maps sets trees heaps and specialized structures based on access patterns memory and CPU requirements and concurrency considerations. Coverage includes case based selection for domain specific systems such as games inventory or spatial indexing where structures like quadtrees or spatial hashing are appropriate, and language specific considerations such as value versus reference types or object pooling. Emphasis is on explaining rationale trade offs and expected performance implications in concrete scenarios.

MediumTechnical

62 practiced

Design a streaming algorithm and choose supporting data structures to detect 'hot' repeated patterns (strings or sequences) in an event stream with bounded memory. You can report approximate results with probabilistic guarantees. Describe how you'd keep memory bounded and report results continuously.

Sample Answer

Approach (summary)- Use a Count-Min Sketch (CMS) for frequency estimation (O(1) update, bounded memory) combined with a small Space-Saving (top-k) table to track candidate “hot” patterns precisely. Maintain time-awareness via either a sliding-window of fixed-length buckets (tumbling) or exponential decay.

Components & data structures1. Count-Min Sketch (w × d): stores hashed counts for all events; gives frequency estimate >= true count; error ≤ εN with probability 1 − δ if w = ceil(e/ε), d = ceil(ln 1/δ).2. Space-Saving/top-k heap (size k): stores k highest-frequency candidates with exact counts relative to seen items in the heap; helps reduce false positives when reporting.3. Time buckets for recency: - Sliding window: keep B CMS instances for consecutive time buckets and expire oldest (memory = B × CMS + top-k). - Or exponential decay: multiply CMS counters periodically by α < 1 (approximate).

Stream processing (continuous)- For each incoming pattern p: - Update current CMS: increment hashed counters. - If p in top-k, increment its exact counter; else consider replacing min entry if estimated count > min.- Periodically (e.g., every T seconds) merge active bucket CMSs (or read decayed CMS) to estimate counts over desired window and refresh top-k candidates.

Memory bounding & guarantees- Memory is fixed: CMS size (w×d) + top-k size + B buckets. Choose ε, δ, k, B to meet RAM budget.- Probabilistic guarantees: CMS overestimates by ≤ εN with probability ≥ 1−δ. Space-Saving guarantees any item with true frequency > (total/k) will appear in top-k.- Sliding window keeps recency strict; decay gives smoother forgetting with less bookkeeping.

Practical considerations- Choose hash functions (pairwise independent) and use 64-bit counters; use merging-friendly CMS for distributed ingestion.- Tune ε, δ empirically to balance false positives/negatives.- Expose API: get_top_k(window) returns top-k items with estimated counts and error bounds.- Persist periodic snapshots for recovery and horizontally scale by partitioning stream (consistent hashing) and merging sketches for global view.

This design yields continuous reporting, bounded memory, and well-known probabilistic error bounds appropriate for production streaming systems.

HardSystem Design

127 practiced

Design a distributed LRU cache that supports sharding, replication, and efficient eviction across nodes. Discuss the data structures you would use on each node for O(1) operations, how to handle hot-key eviction/migration when a shard is overloaded, and consistency trade-offs between strong and eventual consistency.

Sample Answer

Requirements (clarify):- Low-latency O(1) get/put per node, support sharding + replication, global capacity budget with efficient eviction, handle hot keys (skew), and expose configurable consistency (strong vs eventual).

High-level architecture:- Clients hash keys -> shard using consistent hashing with virtual nodes.- Each shard is a small cluster: one primary (leader) + N-1 replicas. Primaries handle writes; replicas serve reads depending on consistency mode.- Global coordinator (lightweight) maintains cluster membership, consistent-hash ring, and global capacity targets per shard (for eviction/migration decisions).

Per-node data structures for O(1) ops:- HashMap<Key, NodeRef> mapping key -> pointer to an entry in a doubly-linked list.- Doubly-linked list ordered by recency (head = MRU, tail = LRU). get/put/update moves node to head; eviction pops from tail.- Entry contains value, version/timestamp, TTL, size, and replication metadata.- Optional segementation: multiple independent LRU segments (shards within node) to reduce lock contention; use concurrent hashmap + segment-level locks or lock-free lists.

Replication & consistency:- Synchronous (strong): primary writes synchronously to a majority/quorum of replicas before acknowledging. Guarantees linearizability but adds latency and reduces throughput.- Asynchronous (eventual): primary acknowledges after local write and replicates in background. Low latency, possible stale reads. Use vector clocks or per-key version numbers to reconcile conflicts.- Read strategies: read-from-primary for strong, read-from-any with version checks/quorum for bounded staleness.

Hot-key eviction/migration:- Detection: measure per-key request rates and per-shard load (CPU, mem, request QPS). If a shard's working set exceeds its capacity or a key's access rate >> average, mark as hot.- Strategies: 1. Replicate hot key across multiple shards (cache-side replication / fan-out reads). Update replication asynchronously with versioning or use primary-forwarding for writes. 2. Migrate key ownership: coordinator reassigns that key’s vnode(s) to less-loaded nodes (consistent-hash rebalancing of a small subset). Transfer entry and metadata; clients pick up new location via ring update. 3. Serve hot keys via read-through proxy or dedicated “hot-key” nodes: route reads for that key to replicas with local copies.- Eviction cooperation: when a shard is overloaded, instead of evicting useful hot items, it pushes LRU candidates to other shards (remote insertion) if global capacity allows, or triggers rebalancing.

Efficient cross-node eviction:- Maintain global capacity targets per vnode. Coordinator periodically gathers shard usage and suggests capacity deltas.- Proactive balancing: use consistent hashing with load-aware vnode assignment (more vnodes to underutilized nodes). For immediate relief, allow remote-swap protocol: overloaded node picks LRU candidates, attempts remote-insert on underloaded node (RPC: tryReserveSpace + transfer). If accepted, remove locally.- To avoid thrash, enforce hysteresis and rate limits on migrations.

Failure and correctness:- Use write-ahead log and snapshots for transfer durability. During migration, use a handoff protocol: mark key as migrating, accept reads/writes at primary, replicate to target, then update ring and remove from source.- Resolve concurrent updates with version vectors or last-writer-wins depending on tolerance.

Trade-offs:- Strong consistency: safer for correctness, simpler conflict model, higher write latency and lower availability during partitions.- Eventual consistency: higher availability and throughput, lower latency, but clients may see stale reads; needs merge/conflict resolution and careful metadata/versioning.- Hybrid: use configurable per-key consistency (e.g., metadata or namespace-level) — hot read-heavy keys can be eventually consistent, critical keys strong.

Operational concerns:- Metrics (hit/miss, evictions, load), backpressure for overload, TTLs for natural eviction, automated rebalancing, and safeguards to limit migration frequency.- Testing: chaos/failure inject, large-scale load tests with skewed distributions.

This design yields O(1) local ops, supports shard-level scaling, provides mechanisms to mitigate hot keys via replication/migration, and gives clear consistency trade-offs so product teams can choose latency vs correctness.

MediumTechnical

75 practiced

In a 2D multiplayer game with many moving objects, you need frequent proximity queries (find objects within radius r) and frequent updates (objects move each tick). Compare quadtrees, k-d trees, and spatial hashing (grid-based) for this workload. Discuss update cost, query cost, memory overhead, and which structure you'd choose for millions of moving objects at 60Hz.

Sample Answer

Short answer: for millions of frequently-moving 2D objects at 60Hz, spatial hashing (uniform grid) is usually the best choice. It gives the lowest update cost, predictable memory and query cost, and is simplest to parallelize and tune for game workloads. Below is a structured comparison and rationale.

Comparison:- Quadtrees: - Update cost: costly. As objects move you must frequently re-insert or rebalance nodes; worst-case can trigger deep traversals or node splits/merges. - Query cost: good for sparse, hierarchical culling (O(log n) average), but can degrade with non-uniform distributions or many small objects straddling node boundaries. - Memory: moderate to high (node overhead, pointers). - Notes: works when objects are mostly static or movement is small and localized.

- k-d trees: - Update cost: high. Balanced k-d trees are expensive to maintain under continuous movement; frequent rebuilds may be required. - Query cost: efficient for range queries in static data (O(sqrt(n)+k) expected in 2D), but performance breaks with dynamic data. - Memory: moderate (tree nodes), and rebuilding uses additional temporary memory. - Notes: better for mostly-static spatial datasets, not millions of moving entities.

- Spatial hashing / uniform grid: - Update cost: low. Each tick you compute cell coordinates (cheap hash) and move object between small per-cell lists. Average O(1) per object update. - Query cost: predictable. Radius queries check only neighboring cells within ceil(r / cellSize), so cost ≈ O(k + cellsChecked). With proper cell size around r (or r/√2), you minimize extra cell checks. - Memory: low-to-moderate. Array or hashmap of buckets; memory scales with number of occupied cells rather than n if sparse. Per-object storage is small (id + pointer). - Notes: Handles worst-case uniform and highly dynamic workloads well; easy to parallelize (per-cell) and to incrementalize.

Which I'd choose and why:- Use spatial hashing with tunable cell size (roughly matching expected query radius), lock-free or per-thread buckets for parallel updates, and compact bucket lists (vectors, pooled arrays) to minimize allocation overhead. For extreme density variance, combine with lightweight local quadtrees inside high-density cells or use multi-level grids (coarse→fine).- Also consider continuous collision checks (swept tests) only when needed, and only query neighbors for objects that require proximity checks that tick.

Trade-offs and tuning:- Choose cellSize ≈ r (smaller increases bucket checks, larger increases false positives).- Use contiguous storage and object-to-bucket indices to make removals O(1).- Rehashing is cheap if using fixed-grid indexing; avoid per-frame memory allocations.

Summary: spatial hashing offers the best practical throughput, predictability, and simplicity for millions of moving objects at 60Hz; trees are better only when objects are mostly static or queries require complex hierarchical culling.

MediumTechnical

63 practiced

Discuss when to use lock-based data structures vs lock-free/lockless data structures. For a concurrent multi-producer multi-consumer queue, compare a simple mutex-protected queue, a lock-free Michael-Scott queue, and a ring-buffer with atomic indices. Explain trade-offs in throughput, fairness, latency, and implementation complexity.

Sample Answer

Start with the tradeoff principle: locks simplify reasoning and correctness but can cost latency, throughput, and fairness under contention; lock-free structures aim for higher concurrency and lower tail latency but increase implementation complexity and subtle correctness concerns (ABA, memory reclamation).

When to use which- Lock-based: use when contention is low-to-moderate, correctness and simplicity are priorities, or when platform/GC makes memory-reclamation hard. Good for fast development and maintainability.- Lock-free: use when you need predictable low tail-latency, very high throughput under heavy contention, or when blocking must be avoided (real-time systems, high-frequency infrastructure). Accept higher complexity and testing burden.

Compare three concurrent MPMC queue designs

1) Mutex-protected queue- Description: single mutex (and maybe condition variables) around push/pop.- Throughput: good at low concurrency, degrades sharply under many producers/consumers due to serialization.- Fairness: depends on OS scheduler; can be fair if using FIFO mutexes/conds.- Latency: low average at low load, high tail during contention (head-of-line blocking).- Complexity: simple to implement and reason about; easy correctness and memory management.

2) Michael–Scott (MS) lock-free queue- Description: canonical linked-list MPMC using CAS on head/tail pointers.- Throughput: excellent under high contention — non-blocking progress; often outperforms mutex when many threads.- Fairness: weaker guarantees; some threads may repeatedly fail CAS (starvation risk), but system as a whole makes progress.- Latency: lower tail latency than mutex because no global blocking, but CAS retries can spike latency.- Complexity: high — need ABA protection (tagging, hazard pointers), careful memory reclamation.

3) Ring buffer with atomic indices (circular array)- Description: bounded array with atomic head/tail counters; often uses versioning or per-slot states.- Throughput: very high and cache-friendly (contiguous memory); best when capacity fits and contention pattern matches.- Fairness: good if implemented with per-slot atomic ops; potential for starvation if spinning.- Latency: very low and predictable (no allocations), but bounded capacity can cause producers to block or drop items.- Complexity: moderate — simpler than linked lock-free but must handle full/empty detection, ABA, and false-sharing (padding needed).

Practical guidance- If you need correctness fast and contention is modest → mutex queue.- If you need unbounded size and non-blocking progress → MS queue, but invest in safe reclamation (hazard pointers, epoch GC).- If bounded capacity is acceptable and extreme throughput/low latency matter → ring buffer with atomics (SPSC simpler; MPMC requires careful per-slot state).Also measure: benchmark in realistic workload, watch for false sharing, memory allocation costs, and system effects (NUMA, hyperthreading).

HardSystem Design

67 practiced

You’re building a key-value store that must support ACID transactions and also expose secondary indexes for attributes other than the primary key. Which data structures would you use for primary storage and for secondary indexes to ensure transactional consistency and efficient scans? Discuss how to maintain secondary indexes during transactions and the trade-offs between write amplification and read performance.

Sample Answer

Requirements & constraints:- ACID transactions (atomicity/isolation/durability) and efficient range/scan on secondary attributes.- Single-node or sharded store affects distributed commit choice (2PC vs single-coordinator).

High-level design:- Primary store: MVCC-backed B+ trees (or B-tree variant). B+ trees give stable ordered storage for efficient point/range scans and low-latency reads. MVCC provides snapshot isolation without blocking readers.- Secondary indexes: Each secondary attribute stored as a B+ tree mapping (secondaryKey -> list of primaryKey, version/timestamp). Use clustering or unique/non-unique variants as needed.

Maintaining indexes during transactions:- Use transactional writes that atomically update primary and secondary index entries within the same transaction under MVCC: - During tx, buffer intents: new primary row (with new version) and corresponding index insert/delete entries referencing the row version. - Persist intents to WAL (durability). - On commit, publish versions (make visible); index entries reference committed version. - On rollback, garbage-collect intents.- Concurrency: implement optimistic MVCC with write-conflict detection or use short-lived locks when updating index nodes to avoid anomalies like phantom reads.- For distributed sharding, coordinate with a single transactional coordinator or 2PC; include index partitions in the prepare/commit.

Trade-offs (write amplification vs read performance):- Synchronous index updates (strong consistency): higher write amplification — each write touches primary + N secondary indexes; more I/O and larger WAL. Pros: reads and scans on indexes are always consistent and fast.- Asynchronous/index-lazy updates (lower write tail-latency): write only primary, enqueue index update; reduces immediate write cost but introduces read staleness, requires validation on reads (e.g., check primary) and background reconciliation increasing eventual compaction/IO.- MVCC + tombstones: updates create versions and tombstones; compaction/GC later increases write amplification but keeps reads snapshot-consistent.- Design knobs: - Allow choosing index maintenance strategy per-index (strong vs eventual). - Use covering indexes to avoid extra lookups for common queries (better read perf, more space/amplification). - Batch index updates and optimize WAL layout to amortize I/O.

Edge considerations:- Range scans need index entries ordered by secondary key and stable pointers to committed primary versions to avoid returning deleted/rolled-back rows.- Compaction must preserve mapping from index entry -> visible version or postpone removing until safe.- Ensure garbage collection of old versions and index entries is coordinated with active transactions to avoid lost visibility.

This design balances ACID correctness (MVCC + transactional intent + WAL/commit protocol) with practical trade-offs: synchronous updates for correctness/performance vs async for lower write amplification.

Unlock Full Question Bank

Get access to hundreds of Data Structure Selection and Trade Offs interview questions and detailed answers.

Join thousands of developers preparing for their dream job.