Hashing and Hash Based Data Structures Questions

Comprehensive coverage of hashing and hash based associative data structures including hash tables, hash maps, dictionaries and hash sets. Candidates should explain hashing fundamentals and the role and properties of hash functions, causes of collisions, and common collision resolution strategies such as chaining and open addressing. Discuss load factor, resizing behavior and how these influence amortized performance and memory usage. Describe average case constant time behavior for lookup insertion and deletion and worst case linear time under pathological collision scenarios, and contrast trade offs with alternatives such as balanced search trees and sorting based approaches. Expect practical problem solving using hash based structures for frequency counting, duplicate detection, grouping, membership testing, two sum and pair problems, anagram detection, sliding window frequency problems and cache or memoization designs including least recently used eviction concepts. Be familiar with common language level implementations such as HashMap and HashSet in Java and dictionary and set in Python and be able to reason about implementation pitfalls including unhashable or mutable keys, custom hash and equality semantics, resizing costs, collision attacks and memory overhead. Interviewers will probe time and space trade offs, when a hash based approach is preferable, and optimization strategies when facing pathological inputs.

MediumTechnical

22 practiced

You observe periodic CPU and GC spikes in a Java service that correlate with large HashMap resizes during peak load. As an SRE, describe how you would investigate the root cause (metrics, logs, heap dumps), short-term mitigations you could apply in production, and longer-term fixes to prevent recurrence.

Sample Answer

Investigation (quick reproducible steps + evidence)- Clarify scope: which instances, time ranges, and requests correlate with spikes. Pull APM/metrics (CPU, heap, GC pause time, allocation rate), thread dumps, application logs, and GC logs for those windows.- Metrics to check: process CPU, system CPU, JVM heap usage, Young/Old gen sizes, GC frequency/duration (from GC logs or JFR), allocation rate, HashMap-related methods in flame graphs (e.g., rehash(), put()), thread states during pauses.- Logs and traces: search request traces for high-response paths; enable sampling to catch offending requests.- Heap/Thread/Flight Recorder: take heap dumps at/near peak and analyze with MAT or Eclipse Memory Analyzer to find large HashMap instances, their sizes, and retained sets; take thread dumps to see GC/lock contention and call stacks around maps.- Local repro: try to reproduce under load in staging with similar input to observe resize behavior.

Short-term mitigations (safe in production)- Reduce load: throttle or shed noncritical requests via rate limiting, circuit breakers, or autoscale additional app instances.- Tune JVM GC/heap: increase heap to reduce frequency of resizes triggering GC (short-term, if memory available); raise young generation size to reduce promotion churn.- Temporary config: if maps are created with unknown sizes, set a higher default initialCapacity for the offending code path via config or feature flag to avoid repeated resizes (e.g., from default 16 to estimated size).- Deploy a quick patch that caps incoming batch sizes or splits large payloads to prevent huge map population.- Restart strategy: staggered rolling restarts if instances are in pathological state.

Long-term fixes (code + infra)- Fix code: pre-size HashMaps using expected sizes (new HashMap(expectedSize)), or use maps that avoid O(n) rehash cost during resize (e.g., LinkedHashMap only if ordering required, or use Trove/fastutil for primitive-heavy use).- Consider using ConcurrentHashMap where concurrent access causes contention; use computeIfAbsent carefully.- Replace large in-memory aggregation with streaming/ incremental approaches, external caches (Redis) or bounded LRU caches; avoid unbounded collections.- Improve observability: add custom metrics for map sizes, allocation hotspots, and instrument critical code paths for flame graphs and allocation profiling (Async-profiler, JFR).- Load testing: create tests that mimic peak inputs, validate that maps and GC behavior are stable.- JVM tuning: choose appropriate GC (G1/ZGC) and tune ergonomics (MaxGCPauseMillis, region sizes) for predictable pauses.- Capacity planning & SLOs: define safe limits for request sizes and memory usage; implement automated circuit breakers when thresholds hit.

Why these steps- Investigation narrows whether spikes are caused by allocation bursts, rehash CPU cost, or GC amplification. Short-term mitigations reduce impact quickly with minimal code change. Long-term fixes eliminate root cause by sizing, data-structure choice, streaming, and better observability so recurrence is prevented and detectable.

HardSystem Design

24 practiced

Design a distributed deduplication service that ensures at-least-once events are de-duplicated across multiple workers without a single coordinator. Discuss using consistent hashing for ownership, replication for durability, the choice between Bloom filters vs exact storage, eventual consistency implications, and latency vs correctness trade-offs.

Sample Answer

Requirements:- Deduplicate at-least-once events across many workers with no single coordinator.- High throughput, low latency, durable deduplication state, and graceful failure handling.- SLO: <=100ms p99 decision latency, false-positive rate ≤1% (configurable).

High-level design:- Partition event key space via consistent hashing ring. Each node (worker) is owner for a set of hash ranges (virtual nodes to balance).- For durability and availability, each key is replicated to R nodes: primary owner + R-1 successors on the ring. Any of the R nodes can answer dedupe queries.- Workers accept events, compute key hash, route (or locally handle if owner) to the replication set.

Deduplication state choices:1) Exact storage (e.g., RocksDB / LMDB per node): - Store seen event IDs with timestamp TTL. - Pros: zero false positives, simple correctness. - Cons: higher disk/IO and memory; higher read/write tail latency under load.

2) Bloom filters (in-memory, optionally backed by disk snapshots): - Fast, small memory footprint, O(1) checks. - Pros: low latency and memory; good for high-volume short-lived dedupe (set of recent IDs). - Cons: false positives (drop unique events), need periodic rotation or counting Bloom for deletes.

Hybrid pattern (recommended): Use a small L1 Bloom filter for fast negative checks and an L2 exact store for positives (or confirmations). Flow:- Check Bloom: if "not seen" -> accept and write to L2 asynchronously; if "maybe seen" -> consult exact store to confirm. This keeps p99 latency low while eliminating false-drop risk.

Replication & consistency:- Use quorum on R replicas for correctness trade-offs: - Read quorum r and write quorum w such that r + w > R (e.g., R=3, w=2, r=2) to prevent split-brain duplicates. - On event arrival, write marker to w replicas (idempotent upsert with timestamp). Consider write-then-ack to caller when w reached. - Read checks for existence use r replicas and reconcile (if disagreement, choose latest timestamp / tombstone).- To avoid a coordinator: client (or worker) performs parallel RPCs to the R replicas and waits for w acks; for reads waits for r responses and applies quorum logic.

Eventual consistency implications:- With asynchronous replication or w < R, there is a window where another node may accept the same event and produce duplicate processing. Mitigate with: - Short TTLs and monotonic timestamps. - Use logical clocks or vector clocks if ordering matters. - Detect late-arriving duplicates at application-side (idempotent handlers).

Latency vs correctness trade-offs:- Favor correctness: increase w and r (w=R) ensures strong durability but increases latency and reduces availability during replica outages.- Favor latency: w=1, r=1 gives lowest latency but higher duplicate risk.- Recommended SRE posture: configure default w=2, r=2 for R=3; allow dynamic tuning via feature flags per traffic class. Provide SLO-driven knobs: low-latency best-effort path vs high-correctness path for critical events.

Failure modes & recovery:- Node failure: consistent hashing reassigns ranges; use hinted handoff for writes to temporarily store for failed replicas.- Replica divergence: anti-entropy (gossip / Merkle trees) reconcile identity sets periodically.- Tombstones + TTLs to avoid resurrection after restore.- Rolling upgrades: drain ownership via ring membership update, stream state via range transfer.

Operational concerns (SRE):- Metrics: dedupe hit/miss rates, Bloom FP rate, replication latencies, quorum timeouts, rehash churn.- Alerts: rising FP rate, increased duplicates detected downstream, prolonged replica downtime, quorum failures.- Testing: chaos (node kill), network partitions, load tests for p99 latency under R and quorum settings.- Backpressure: if the L2 store is overloaded, backpressure at ingress or degrade to best-effort with monitoring/alerts.

Example flow (R=3, w=2, r=2):- Worker receives event id X → hash → find replicas A,B,C.- Parallel write requests to A,B,C; on w=2 acks return ACCEPT and insert X into Bloom and persist to L2 asynchronously if not yet persisted.- If a concurrent worker checks and sees inconsistent state, quorum reads resolve with latest write; duplicates minimized by w+r>R.

This design balances no single coordinator, durability via replication, low-latency checks via Bloom + exact store, and explicit trade-offs (w/r) so SREs can tune correctness vs latency per SLO.

MediumTechnical

26 practiced

Compare using a hash map versus a balanced search tree (e.g., red-black tree) for maintaining an index used by a monitoring system. Discuss time complexity, memory overhead, predictability of latency, ordered iteration, and which you'd pick for workloads where adversarial inputs are possible.

MediumTechnical

26 practiced

Implement a server-side function to detect duplicate events within a sliding time window using a hash-based approach where exact detection (no false positives) is required. Describe the data structures, memory/time complexity, and how you'd bound memory for a long-running service under high cardinality.

Sample Answer

Approach: keep an exact in-memory hash map event_id -> last_seen_timestamp and a time-ordered queue for eviction. On ingest, check map for event_id; if present and last_seen >= now - window -> duplicate. Always insert/update map and append (timestamp, event_id) to the queue. Periodically evict queue head entries older than window to bound memory. This yields exact detection (no false positives).

python

import time
from collections import deque
from threading import Lock

class DuplicateDetector:
    def __init__(self, window_seconds):
        self.window = window_seconds
        self.last_seen = {}          # event_id -> timestamp
        self.queue = deque()         # (timestamp, event_id) ordered by arrival
        self.lock = Lock()

    def is_duplicate(self, event_id, now=None):
        """Return True if event_id seen within window, else False (and record it)."""
        now = now or time.time()
        with self.lock:
            # Evict old entries
            cutoff = now - self.window
            while self.queue and self.queue[0][0] < cutoff:
                ts, eid = self.queue.popleft()
                # Only remove from map if this timestamp was the last seen for that id
                if self.last_seen.get(eid) == ts:
                    del self.last_seen[eid]

            last = self.last_seen.get(event_id)
            dup = (last is not None and last >= cutoff)
            # Record current arrival
            self.last_seen[event_id] = now
            self.queue.append((now, event_id))
            return dup

Key points:- Data structures: hash map for O(1) lookup; deque for O(1) amortized eviction and ordering.- Time complexity: O(1) amortized per event (evictions across events cost O(1) per removed entry).- Space: O(U) where U = unique event IDs seen inside the window.

Bounding memory for long-running/high-cardinality:- This scheme bounds memory to the number of distinct event IDs seen in the sliding window. For very high cardinality you can: - Use external stores (Redis with maxmemory + volatile-ttl) to offload state, preserving exactness if using exact keys with TTL. - Shard detectors across processes/hosts by event partitioning (consistent hashing) to distribute memory. - Apply business-driven aggregation or canonicalization to reduce distinct keys (normalize IDs). - If you must cap memory strictly, implement an LRU on top of the map and accept that very-old-but-within-window entries could be evicted — document this trade-off (no longer strictly exact).

Edge cases:- Clock skew: use monotonic clocks or include source timestamp semantics.- Very bursty input: perform evictions before heavy insert bursts to avoid spikes.- Concurrency: ensure locking or use concurrent maps per shard.

HardSystem Design

26 practiced

Design a low-latency system to compute heavy hitters (top-k frequent elements) over a sliding window at 10M events/sec. Propose hash-based sketches or algorithms (Space-Saving, Frequent, count-min), explain how to parallelize and merge partial results across shards, and analyze error bounds, memory usage, and latency trade-offs.

Sample Answer

Requirements & constraints:- Ingest 10M events/sec, low-latency (<100ms to update/heavy-hitter answers), sliding window (e.g., last 5 min), fault-tolerant, memory-efficient.

High-level design:- Ingest layer: N partitioned shards (Kafka/topic with partitioning by key hash) → stream processors (one per shard) → local sketch per processor → periodic merge/queried aggregator serving top-k.

Algorithm choices:- Use Space-Saving per shard for precise top-k candidates (guaranteed error ≤ total_count / m for m counters) combined with Count-Min Sketch (CMS) for frequency estimation when items exceed counters or to estimate tails. Space-Saving gives exact IDs for heavy hitters; CMS provides conservative upper bounds and is merge-friendly.

Per-shard implementation:- Maintain a ring of time-partitioned Space-Saving sketches (e.g., 30s buckets) for sliding window. On event: update current bucket's Space-Saving (O(1)). Also update a per-bucket CMS for aggregate frequency queries.- Rotate buckets to evict old data; keep W/T buckets for window length W and bucket duration T.

Parallelization & merge:- Each shard exposes its top-(k+ε) from its space-saving per window and per-item counts via CMS.- Aggregator periodically collects candidates from all shards (pull or push). To compute global top-k: 1. Union candidate IDs. 2. For each candidate, query each shard's CMS (or aggregated CMS) to get estimated frequency; sum estimates → global estimate (CMS over shards can be merged by adding counters). 3. Rank and return top-k.- Merging Space-Saving directly is complex; instead rely on collecting candidate IDs (small set) and using merged CMS for frequencies. Optionally keep global Space-Saving at aggregator by feeding shard top candidates.

Error bounds & memory:- CMS: width w = ceil(e/ε) and depth d = ln(1/δ) gives error ≤ ε * total_count with probability 1-δ. Example: ε=0.005 (0.5%), δ=0.01 → w≈200, d≈5. Memory ≈ w*d counters.- Space-Saving: m counters gives max error ≤ total_count / m. To capture top-k reliably choose m ≈ α*k (α=10) depending on skew.- Per-shard memory: with S shards, split budget. For 10M/sec, 5-min window → 3e9 events total; but CMS error is relative to counts so choose ε accordingly. Use 32-bit counters; for w=2000,d=5 → 40k counters ≈160KB per bucket. With 10 buckets per shard ≈1.6MB.

Latency & trade-offs:- Updating sketches O(1) → microsecond-level per event; ensure batching and lock-free structures to maintain 10M/s across cores.- Smaller buckets reduce eviction latency but increase memory and merge ops.- More aggressive ε reduces memory but raises overestimation risk (false positives in top-k).- Pulling candidates more frequently reduces staleness but increases network/CPU.

Operational considerations (SRE):- Autoscale shard count based on ingress and CPU; provision high-throughput networking.- Use lock-free, per-core sketches (shard per core) to avoid contention; aggregate via async background merges.- Monitoring: track sketch error metrics (total_count vs sum of top counters), QPS, tail latencies, memory, and merge lag. Alert on merge-lag > window/4 or estimator drift.- Fault tolerance: persistent periodic checkpoints of sketches to durable store; on restart, resume with reconstructed buckets.- Testing: synthetic workloads with Zipf distributions to validate recall/precision for chosen parameters.

This design balances per-event latency (O(1) updates), memory (sketch parameters), and accuracy (tunable ε and m) while enabling scalable parallel ingestion and merge-friendly frequency estimation.

Unlock Full Question Bank

Get access to hundreds of Hashing and Hash Based Data Structures interview questions and detailed answers.

Join thousands of developers preparing for their dream job.