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.

HardTechnical

31 practiced

A production Java microservice using HashMap now experiences high tail latencies for lookups. Describe step-by-step diagnostics to determine if pathological collisions (bad hashCode) are causing O(n) behavior, including JVM tools, metrics to inspect, and how to reproduce and mitigate the issue with minimal disruption.

Sample Answer

Situation: Production microservice shows high tail latencies on lookups that used to be O(1). Suspect pathological HashMap collisions (bad hashCode) causing O(n) behavior.

Step‑by‑step diagnostics1. Triage metrics first- Confirm symptom: p50/p95/p99 read latencies, CPU, thread count, GC rates (CloudWatch/Prometheus/Grafana). Look for increased CPU and p99 spikes aligned to traffic.- Check allocation rate and safepoint/G1 GC pause time — pathological loops often show CPU, not GC.

2. Capture runtime evidence- Take several thread dumps (jstack) during a spike and inspect threads stuck in java.util.HashMap.get/put loops or in user code iterating large buckets.- Collect CPU flamegraph using async-profiler or Java Flight Recorder (JFR). Look for heavy CPU in java.util.HashMap.bucket traversal methods.- Use jcmd GC.class_histogram / jmap -histo to find many instances of the key class or unusually large HashMap instances.- If using older JVM (<8u), note HashMap doesn’t treeify by default; in modern Java, large bins become tree nodes — still can be expensive.

3. Confirm collisions- If CPU profile shows time in equals() or HashMap inner loops and histograms show many keys of same class, suspect identical/poor hashCode.- Reproduce locally: write a small harness that inserts and looks up millions of keys created from production-like inputs. Create a custom Key with hashCode() returning constant or low-entropy slices of the real key to mimic production.- Run the harness under same JVM flags and measure lookup time; compare with keys using good hashCode.

4. Minimal‑disruption mitigation & rolloutImmediate (low-risk, fast):- Apply input sanitization upstream: canonicalize or salt keys (append a shard byte) where feasible to increase hash spread.- Add a runtime feature flag to switch the Map implementation for the hot path to ConcurrentHashMap or a Guava ImmutableMap built at write time — these have better concurrency and collision behavior. Deploy behind flag and A/B test.- If single-threaded, switch to LinkedHashMap or TreeMap (TreeMap O(log n)) for pathological cases — TreeMap avoids O(n) bucket chains.

Permanent fixes:- Fix the offending key class: implement a proper hashCode() producing good distribution (use Objects.hash/Guava’s Hashing.goodFastHash for complex keys). Add unit tests asserting hashCode dispersion for representative inputs.- Consider upgrading JVM if treeification threshold or balancing improvements are absent in current version.- Add instrumentation: measure bucket-lengths or track Map sizes and p99 lookup time; alert when above threshold.

Rollback plan- Revert map change via feature flag, or scale down release; monitor latency metrics.

Why these steps- Thread dumps + CPU flamegraphs point to CPU-bound HashMap loops; histograms reveal key-class explosion. Repro harness proves causality. Runtime switches and input-sanitization are least disruptive; correct hashCode and instrumentation fix root cause and prevent recurrence.

MediumTechnical

23 practiced

When writing Parquet files for analytical queries, how would you choose partition keys? Compare hierarchical directory partitioning (e.g., date=2025-11-01/) vs hash bucketing (bucketed by user_id) in terms of file sizes, small-file problem, predicate pushdown, and handling skew. Provide recommendations for typical OLAP workloads.

Sample Answer

Start by asking: which columns are commonly used as query filters, cardinality, and data arrival pattern. Good partition keys maximize pruning while avoiding too many tiny files or hot partitions.

Comparison:

- Directory (hierarchical) partitioning (e.g., date=2025-11-01/): - File sizes: Easy to produce large files per partition if you write bulked daily files; predictable file sizes per partition. - Small-file problem: Less severe if you compact per partition; but high-frequency partition granularity (hour/minute) can create many small files. - Predicate pushdown: Excellent for predicate pruning when queries filter by partition columns (date). Engines skip entire directories. - Skew: If data or queries concentrate on a few partitions (e.g., recent dates), you get hot partitions and uneven read/compute.

- Hash bucketing (bucketed by user_id): - File sizes: Can control target file size by choosing number of buckets; each bucket maps to a file set—good for balanced file sizes across keys. - Small-file problem: Reduced because bucketing spreads rows evenly; but if many empty buckets exist for sparse keys, you’ll get small files. - Predicate pushdown: Less effective for range/time filters; equality on bucket key can be optimized if engine is bucket-aware (joins on bucketed key). - Skew: Bucketing evens out distribution for the hashed key, mitigating hot partitions for skewed user_id popularity.

Practical recommendations for OLAP:- Use coarse-grained directory partitioning on time (day/month) because time predicates are common—avoid minute/hour unless query patterns require it.- Combine: partition by date (coarse) + within each partition write files aligned to hash buckets (or use partitioned writes with salting) to balance file sizes and reduce skew.- Aim for 128 MB–1 GB parquet files for scan efficiency; compact small files during ETL or use write-side buffering/continuous compaction.- Choose bucket key for high-cardinality, frequently-joined equality keys (user_id) to speed joins and balance data; only use bucketing when your execution engine (Spark/Hive/Trino) supports bucket-aware optimizations.- Monitor: track file counts per partition, read hotness, and table scan patterns; adjust partition granularity and number of buckets accordingly.

Summary: Partition by time (coarse) for pruning, add hashing/bucketing or salting to balance files and handle skew, and target large Parquet files with periodic compaction.

MediumTechnical

27 practiced

Describe double hashing for open addressing and implement a Python function that generates the probe sequence indices for a given key and table size m. Explain how to choose the second hash function so the probe sequence visits every slot (i.e., h2 relatively prime to m).

Sample Answer

Approach: In open addressing double hashing the probe sequence for key k ish(k,i) = (h1(k) + i * h2(k)) mod m, i = 0,1,2,...To guarantee the sequence visits every slot before repeating, h2(k) must be relatively prime to m (gcd(h2,m)=1). Common practical choices:- If m is prime: h2(k) = 1 + (hash(k) mod (m-1))- For general m: pick a fixed R with gcd(R,m)=1 (e.g., largest prime < m) and set h2(k) = 1 + (hash(k) mod R)

Implementation: generator that yields up to m distinct probe indices.

python

import math

def probe_sequence(key, m, h1=None, h2_factory=None):
    """
    Generate up to m probe indices for key using double hashing.
    - key: any hashable object
    - m: table size (int > 0)
    - h1: optional primary hash function h1(x) -> int; defaults to builtin hash mod m
    - h2_factory: optional function h2_factory(key, m) -> int (must be 1..m-1 and gcd(h2,m)=1)
    Yields integers in [0, m-1].
    """
    if m <= 0:
        raise ValueError("m must be > 0")
    h = hash(key)
    if h1 is None:
        h1_val = (h % m + m) % m
    else:
        h1_val = h1(key) % m

    if h2_factory is None:
        # default: if m is prime use m-1; else use R = largest prime < m (simple fallback: m-1)
        # ensure h2 in [1, m-1] and gcd(h2,m)=1
        def default_h2_factory(k, m):
            candidate = 1 + (hash(k) % (m - 1)) if m > 1 else 1
            # if gcd fails, increment until relatively prime (bounded loops since m small-ish)
            while math.gcd(candidate, m) != 1:
                candidate = (candidate % (m - 1)) + 1
            return candidate
        h2_factory = default_h2_factory

    h2_val = h2_factory(key, m)
    if math.gcd(h2_val, m) != 1:
        raise ValueError("h2 must be relatively prime to m")

    for i in range(m):
        yield (h1_val + i * h2_val) % m

Key points:- Correctness: if gcd(h2,m)=1 then i*h2 mod m cycles through all residues → visits every slot.- Time/space: producing up to m probes is O(m) time, O(1) extra space (generator).Edge cases:- m <= 0 invalid- If h2 accidentally shares factor with m the sequence may cycle through a subset; validate gcd.Alternatives:- Linear probing (h2=1) simpler but higher clustering- Quadratic probing avoids primary clustering but may not probe all slots unless m prime and coefficients chosen carefully

This implementation uses Python's hash and a safe default h2; in production choose m and h2 strategy to match table-growth/rehash policies and concurrency constraints.

HardTechnical

32 practiced

Describe the broadcast-hash-join and shuffle-hash-join strategies used in distributed query engines. For each, explain when it is appropriate, network I/O characteristics, memory requirements, and how data skew and partitioning can affect performance.

Sample Answer

Broadcast Hash Join:- When appropriate: use when one side (build side) is small enough to fit in memory on each worker (e.g., dimension table, lookup). Common in star-joins, small-dimension joins, or after filter that shrinks one side.- Network I/O: low — the small build table is sent (broadcast) to every executor; no shuffle of the large table.- Memory requirements: every worker must hold the entire build-side hash table in-memory (plus overhead). If it exceeds memory, OOM or fallback to other strategies.- Skew & partitioning effects: less sensitive to partitioning of the large side because build is local; however heavy skew on probe side can cause hotspots in processing (CPU/memory) but not network imbalance. If build is larger than estimated, broadcast costs spike.

Shuffle Hash Join:- When appropriate: both sides are large and cannot be broadcast; engine repartitions both inputs by join key, then builds hash tables per partition and probes them.- Network I/O: high — both inputs (or at least one) are shuffled across the cluster so matching keys land on same partition. Network cost ~size of shuffled datasets.- Memory requirements: per-partition memory must hold the build partition’s hash table. By controlling partition count you control per-task memory footprint.- Skew & partitioning effects: highly sensitive — key skew causes some partitions to be much larger, leading to stragglers, OOMs, and longer GC. Mitigations: salting (key append random), skew-aware partitioning, increasing parallelism (more partitions), map-side filtering, or using hybrid strategies (broadcast if one partition becomes small). Also choose appropriate partitioner and tune split sizes.

Trade-offs & practical notes:- Cost-based engines pick broadcast when build size << cluster memory and broadcast cost < shuffle cost. Collect accurate size stats or use adaptive execution (e.g., Spark AQE) to switch strategies at runtime.- Hybrid approaches: shuffle-replicate for medium tables, or broadcast only when below threshold. Monitor network, shuffle read/write metrics, executor memory, and skew metrics to tune join strategy.

HardTechnical

24 practiced

Compare hash-based grouping (hash aggregation) and sort-based grouping for large-scale data pipelines. Discuss memory usage, disk spill behavior, stability, streaming support, and which approach is preferable for unbounded streaming workloads with late data or for batch processing with limited RAM.

Sample Answer

Clarify requirements: grouping (GROUP BY / windowed aggregation) over large datasets can be done with hash-based aggregation or sort-based (sort-merge) aggregation. Below I compare them across your requested dimensions and give recommendations for unbounded streaming with late data vs batch with limited RAM.

Memory usage- Hash aggregation: keeps hash table of group keys + partial aggregates in memory → low per-group compute but memory grows with distinct groups. When RAM insufficient, needs externalization.- Sort-based: requires sorting keys (or runs) — needs memory for sorting buffers but can be tuned; external merge-sort writes runs to disk when buffers fill.

Disk-spill behavior- Hash: spills buckets or serializes entries to disk (external hash). Spilling can be incremental (spill hot buckets) but can degrade to heavy IO if many distinct groups.- Sort: naturally writes sorted runs and then merges; predictable IO pattern (sequential writes/reads), often more efficient on disk than random spills from hash.

Stability (deterministic ordering / reproducibility)- Hash: non-deterministic order of groups unless you add explicit ordering; aggregation results are deterministic but output ordering isn’t.- Sort-based: stable in output order (sorted by key), which helps downstream deterministic pipelines and easier debugging.

Streaming support- Hash: aligns well with streaming (maintain state per key). Systems like Flink/Beam keep keyed state (in-memory + state-backend like RocksDB) and support incremental updates, windows, eviction. Handles late data via watermarks + allowed lateness; state grows with key cardinality.- Sort-based: poor fit for unbounded streams because you can’t globally sort an infinite stream; only practical for bounded windows where you sort the window content before finalizing.

Which to prefer- Unbounded streaming with late data: use hash-based (keyed state) with a scalable state backend (e.g., RocksDB, remote state stores). Combine with watermarks, allowed-lateness, incremental pre-aggregations (map-side combine), TTL or periodic eviction to bound state. Advantage: incremental results, low latency, supports updates on late arrivals.- Batch processing with limited RAM: prefer sort-based external merge (sort-merge aggregation) when distinct-key cardinality is high relative to memory. Its predictable spill pattern and sequential IO make it robust with limited RAM. If cardinality is moderate, hash-aggregation with spill to disk (external hash) or hybrid (hash until threshold then fallback to sort) is also good.

Practical tips- Hybrid strategies: many engines use hash-first for speed, falling back to external sort when memory or skew forces it.- Handle skew: for hash, use salt/shuffle techniques; for sort, ensure merge parallelism.- For streaming, prefer state backends that spill (RocksDB) and use checkpointing; for batch, tune memory, buffer sizes, and number of merge threads.

Bottom line: streaming + late data → hash/keyed incremental aggregation with robust state backend; batch + constrained RAM → external sort-merge (or hybrid) for predictable disk behavior.

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.