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

32 practiced

Explain feature-hashing (the hashing trick) for converting high-cardinality categorical features into fixed-size numeric vectors. Discuss how collisions affect model performance, the use of signed hashing to reduce bias, how to choose vector dimensionality, and when this approach is preferred over one-hot encoding.

HardTechnical

25 practiced

You must choose a non-cryptographic hash function to use for feature hashing in production. Design an experiment to evaluate candidate hash functions: define metrics (collision rate, distribution skew, throughput), dataset sampling strategy, statistical tests to compare distributions, and a safe roll-out plan to switch hashes with rollback capability.

Sample Answer

Approach summary: run controlled offline experiments + an online canary to compare candidate non-cryptographic hashes (e.g., xxHash, MurmurHash3, FarmHash, CityHash) vs. current hash. Measure collision behavior, distribution uniformity, and throughput; use statistical tests and safe staged rollout with ability to revert.

Metrics- Collision rate: proportion of distinct raw keys that map to same bucket for a target hash size (e.g., 2^20). Report overall and by cardinality bucket (low/medium/high).- Distribution skew: per-bucket counts → compute chi-square statistic, KL divergence vs. uniform, Gini coefficient, and 99/99.9-percentile load ratio (hot-bucket risk).- Throughput & latency: encode ops/sec, avg/p95/p99 latency for hashing under realistic CPU/core counts; measure memory and SIMD performance.- Downstream impact: change in model input sparsity, feature frequency rank correlation (Spearman) vs. baseline, and model metric proxies (log-loss, AUC) in shadow scoring.- Stability: seed sensitivity and cross-language consistency (same hash bits in Python/Java/C++).

Dataset sampling- Use a stratified sample of production keys: sample by feature type, account ID, geolocation, and cardinality strata; include tail heavy distribution (power-law) and recent temporal window + older data to catch drift.- Ensure sample size gives statistical power for collision differences (power analysis). Include a full high-cardinality subset (top-N keys) and a large random sample (~1-5M keys) depending on scale.- Create deterministic sample seeds so experiments are reproducible.

Experiment steps1. Precompute hashes for each candidate and baseline on sampled dataset.2. Compute metrics above; produce per-feature reports (heatmaps, bucket percentiles).3. Statistical tests: - Chi-square goodness-of-fit to test uniformity (aggregated buckets). - Kolmogorov–Smirnov (KS) for distribution differences of per-bucket counts. - Permutation/bootstrap tests for collision rate differences and KL divergence to get CIs. - Spearman correlation for rank stability of top keys. - Use multiple hypothesis correction (Benjamini-Hochberg) when testing many features.4. Benchmark throughput in isolation and under simulated load; measure multi-thread scaling.

Decision criteria (example)- Reject if collision rate increases > X% absolute or causes more than Y% increase in top-1% bucket load.- Prefer candidate minimizing KL and Gini while meeting throughput SLA and cross-language bit-equality.

Safe rollout & rollback plan1. Versioning: define hash version in feature spec; store hash_version alongside hashed features.2. Shadow/dual-write: run candidate hash in shadow mode—compute both baseline and candidate hashes for live traffic; feed candidate hashed features to model in “observe only” mode and compare distributions and model scores.3. Canary: route small % (1–5%) of traffic to new hash (both hashing and serving). Monitor bucket load, model metrics, latency, error rates, business KPIs.4. Gradual ramp: increase traffic in stages (5→25→50→100%) with automated health checks and rollback gates.5. Rollback triggers: if collision rate, hot-bucket ratio, downstream model metric degradation, or latency exceed thresholds for sustained window (e.g., 5 minutes), automatically revert routing and mark hash_version deprecated.6. Backwards compatibility: ensure ability to reprocess/rehash historical data (or maintain old hashed keys) if needed for feature store consistency.7. Post-deploy: periodic sampling to detect drift; keep both hash implementations available for quick repro and audits.

Operational notes- Ensure cross-language/unit tests produce identical bit outputs.- Keep deterministic seeding and document behavior for different input encodings.- Log sampled collisions and edge cases for forensic analysis.- Automate dashboards and alerts for the defined metrics.

This experiment balances statistical rigor, engineering performance, and safe production practices so you can pick a hash that minimizes collisions and skew without sacrificing throughput, and revert quickly if unforeseen issues appear.

MediumTechnical

30 practiced

You have millions of image embeddings (128-dimensional floats) and need to deduplicate near-duplicates in sub-second time. Describe how locality-sensitive hashing (LSH) can be applied: choose LSH family (e.g., random hyperplane / SimHash), design bucketization, discuss parameters (bands/rows or k/L), and trade-offs in recall vs precision and compute cost.

Sample Answer

Goal: find near-duplicate 128-D image embeddings in sub-second time across millions of items. LSH offers sublinear candidate retrieval by hashing similar vectors to same buckets.

LSH family choice- Use random hyperplane LSH (a.k.a. SimHash) for cosine similarity since embeddings are L2-normalized commonly. It’s simple, fast, and binary-friendly for bit operations.- If using Euclidean distance, use p-stable LSH (Gaussian projections).

Bucketization and hashing design- For hyperplane LSH: generate k random hyperplanes → each embedding maps to a k-bit signature (sign of dot products). Store an inverted index: bucket key = k-bit integer → list of IDs.- To reduce false negatives, repeat with L independent hash tables (different random hyperplanes). At query time, compute signatures across L tables and union candidates from matching buckets, then re-rank by exact cosine distance.

Parameter tuning (k and L; or bands/rows)- Tradeoff: larger k → smaller buckets (higher precision, lower recall); larger L → higher recall (more tables) but higher memory/compute.- Heuristic: target average bucket size b (e.g., 50–500). For N items, expected buckets ~ 2^k, so pick k ≈ log2(N/b). Then choose L to meet recall: start L=10–50 and increase until recall target reached on validation set.- Alternative banding (for MinHash-like signatures): split a long signature into b bands of r rows; matches in any band count as candidate. Equivalent tradeoffs: more bands → higher recall for near matches.

Recall vs precision vs compute- Recall increases with L and smaller k; precision increases with larger k and fewer tables. More candidates → higher compute at re-ranking (exact cosine) and more memory for inverted lists.- Latency: signature computation is O(d·L) (d=128). Query cost ≈ O(d·L + sum bucket sizes + exact distance cost). Use SIMD/BLAS for dot products and pack hyperplanes into matrices to compute many projections in one matmul.

Practical optimizations- Use bit-packed k up to 64 and fast XOR/hamming for comparisons to find near buckets (for approximate Hamming neighbors).- Use multi-probe LSH: probe nearby buckets (flip few bits) instead of increasing L to reduce memory.- Shard indices, keep inverted lists on SSD with caching of hot buckets, and precompute normalized embeddings.- Validate on a labeled holdout: measure recall at K and queries/sec; tune k/L or probe radius accordingly.

Summary: For cosine-similarity image embeddings, use SimHash with k tuned to control bucket size and L tuned for recall; consider multi-probe to reduce memory. Always re-rank candidates using exact cosine to ensure precision.

MediumTechnical

24 practiced

Scenario-based: Design a memoization/cache layer for an expensive preprocessing function used during model training. Describe how you would construct cache keys (hashable representation of inputs), eviction strategy (in-memory LRU vs persistent store), serialization of keys/values, and measures to avoid memory leaks in long-running training jobs.

Sample Answer

Requirements & constraints: cache an expensive preprocessing(fn(inputs, params)) used across epochs and experiments; must be reproducible, handle large intermediate objects, work in single-process and distributed training, avoid unbounded memory growth.

Cache key construction:- Canonical fingerprint = hash(function_version || deterministic-serialized(inputs) || deterministic-serialized(params) || dataset-version)- Use SHA-256 over a canonical binary representation (e.g., protobuf or msgpack with sorted keys). Example key: SHA256(func_name + ":" + func_git_sha + ":" + msgpack(inputs_sorted) + ":" + msgpack(params_sorted))- Include function code/version to prevent stale results when preprocessing logic changes.

Serialization of keys/values:- Keys: binary hash string (fixed length) — small and safe for lookups.- Values: serialize preprocessed tensors/arrays using efficient formats: PyTorch tensors -> torch.save (or pickled tensor with storage serialization), NumPy -> .npy or msgpack + zstd compression for disk; for Redis use msgpack + compression. Prefer formats that preserve dtype, shape, device.- Ensure deterministic serialization: sort dict keys, convert sets to sorted lists, cast floats with controlled precision if necessary.

Eviction & storage strategy:- Hybrid approach: - In-memory LRU cache (bounded, e.g., cachetools LRU with max_bytes or max_items) for hottest items to reduce latency. - Persistent backing store (Redis or cloud object store like S3 / MinIO) for larger or less-frequent items with TTL and optional versioned keys. On miss in memory, check persistent store, then recompute if absent.- Configure policies: keep small memory footprint (e.g., 4–8 GB), set Redis maxmemory with LRU policy and TTLs for ephemeral data.- For distributed training, store large preprocessed artifacts in shared object store (S3) and keep only metadata/keys in Redis.

Concurrency, correctness & freshness:- Use atomic writes or write-through locks (e.g., Redis SETNX or file lock) to prevent duplicate expensive computation.- Include function_version in key to force recompute when code changes.

Avoiding memory leaks & long-running jobs:- Use bounded caches and monitor memory by bytes, not item count.- Use weak references for in-memory metadata where appropriate; ensure PyTorch tensors moved to CPU and freed (del tensor; torch.cuda.empty_cache()) when serializing.- Periodic compaction: a background thread evicts entries by age/size; periodic GC and profiling.- Instrument metrics (cache hit/miss, sizes, object counts) and alert on growth trends.- For multiprocessing, avoid per-worker unbounded caches: use shared Redis or local LRU with a small cap per worker.

Edge cases & trade-offs:- Deterministic serialization adds CPU overhead — balance by hashing only salient fields (e.g., subset of inputs) when safe.- Persistent stores add latency and cost; use compression and chunking for very large artifacts.- Security: avoid storing secrets in keys/values; encrypt at rest if needed.

This design balances low-latency training loops (in-memory LRU), reproducibility (deterministic keys/versioning), scalable sharing (persistent store), and safety for long-running jobs (bounded resources, monitoring).

HardSystem Design

24 practiced

System design (hard): Design a streaming deduplication system for event logs at 100k events/sec with only 1GB of RAM available for state. Propose an architecture using approximate structures (Bloom filters, Count-Min Sketch), short-term exact caches (LRU), and a multi-level approach. Provide pseudocode for admission, eviction, and recovery from filter saturation.

Sample Answer

Requirements & constraints:- Input: 100k events/sec, high ingest, deduplicate by event-id within short window (minutes–hours).- Memory: 1 GB for state; must be approximate for long window, exact cache for hot items.- Latency: <100ms per decision. False positives acceptable (drop unique rarely); false negatives should be minimized.- Durability: Minimal operator restarts; filters can be rebuilt from short-term persistent log.

High-level multi-level design:1. Front: fast exact short-term cache (in-memory LRU hash) holding recent K IDs (e.g., 10M entries if fits).2. Mid: Counting Bloom Filter (CBF) for sliding window membership with decay/periodic rotate to forget old items.3. Back: Count-Min Sketch (CMS) for frequency estimates to assist admission (prevent poisoning by high-volume IDs).4. Write-ahead log (append-only) for recent events on local SSD for recovery and rebuilding filters.

Component responsibilities:- Ingest worker: validate, hash id, consult levels, decide emit/drop, append to WAL, update structures.- Eviction manager: maintain LRU size, rotate Bloom filters periodically (e.g., every T minutes), decrement CBF counts or swap to new filter to implement sliding window.- Recovery service: replay WAL up to a cutoff to reconstruct LRU and CBF/CMS.

Data flow:Event -> Ingest worker -> LRU exact check -> CBF check -> CMS evaluate (admit or not) -> emit/drop -> append WAL -> update LRU/CBF/CMS.

Memory budgeting (example):- LRU: 200MB (store recent 2M compact IDs using 8-byte hashed keys + overhead)- CBF: 600MB (counting buckets)- CMS: 200MB

Pseudocode (admission, eviction, recovery):

python

# compact hash function
def h(id): return farmhash64(id)  # 64-bit

# Admission logic
def admit(event_id):
    key = h(event_id)
    if LRU.contains(key):
        return DROP  # exact duplicate
    if CBF.might_contain(key):
        # possible duplicate
        return DROP_WITH_FP_RATE  # acceptable false positive
    # use CMS to check heavy hitter protection
    if CMS.estimate(key) > HEAVY_THRESHOLD:
        # protect against skew: prefer admitting to avoid dropping many uniques from heavy ID? or vice-versa
        # here we still insert but mark as heavy
        pass
    # new item
    LRU.insert(key)
    CBF.add(key)
    CMS.update(key, 1)
    WAL.append(key)
    return EMIT

# Periodic eviction / rotate (run every T seconds)
def rotate_filters():
    # use double-buffered Bloom filters to implement sliding window
    old_bf = bf_old
    bf_old = bf_current
    bf_current = CountingBloom(size=...)  # fresh zeroed
    # To decay counts: swap and rebuild CMS if needed
    # Optionally replay subset of WAL for last window to restore precise counts

# Recovery (on restart)
def recover():
    # Read WAL from last checkpoint position
    for key, ts in WAL.read_from(checkpoint):
        if ts >= now - WINDOW:
            LRU.insert(key)         # up to capacity
            CBF.add(key)
            CMS.update(key,1)

Key trade-offs and reasoning:- Bloom/CBF offers compact membership with controlled false positives; Counting Bloom supports deletions/decay by using count buckets or periodic rotation.- LRU ensures zero-FP for very recent items; tuning LRU size reduces FP at cost of memory.- CMS helps detect heavy hitters so we can bias admission/eviction policies (prevent poisoning).- WAL allows bounded recovery without full upstream replay.- Tune parameters: BF false-positive p, number of hash functions k, CMS width/depth given 1GB budget.

Edge cases:- Filter saturation: when CBF counters approach max, trigger rotate and partial WAL replay to reconstruct only active window.- Clock skew: use event timestamps and windowing consistent across workers.- Hot keys: shard by hash to distribute state; each shard keeps its own LRU/filters.

This multi-level approach balances memory, throughput, and acceptable error rates for ML pipelines that consume deduplicated logs.

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.