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

29 practiced

Implement a Python function that returns all unique pairs of values from an integer array that sum to a target. Each pair should be sorted internally and the list of pairs should be unique (no duplicate pairs). Aim for O(n) average time using hash-based structures and explain how you handle duplicates and ordering of results.

Sample Answer

**1. Approach (brief)**

Use a single pass with a hashset to record seen numbers and another set to record result pairs (as tuples sorted) to avoid duplicates. This yields O(n) average time and O(n) space.

**2. Code implementation**

python

def unique_pairs(nums, target):
    """
    Return list of unique pairs [a, b] where a + b == target.
    Each pair is sorted internally (a <= b). Result order is arbitrary.
    """
    seen = set()           # numbers we've seen
    pairs = set()          # store pairs as tuples (a, b) to deduplicate

    for x in nums:
        y = target - x
        if y in seen:
            a, b = (x, y) if x <= y else (y, x)
            pairs.add((a, b))
        seen.add(x)

    # convert to list of lists
    return [ [a, b] for (a, b) in pairs ]

**3. Key concepts & reasoning**

- Use a hashset for O(1) average membership checks.- When a complement is found, create a sorted tuple (min, max) so (2,3) and (3,2) map to the same key, preventing duplicates.- Storing pairs in a set ensures uniqueness even with repeated numbers in input.

**4. Complexity**

- Time: O(n) average (single pass, O(1) average set ops).- Space: O(n) for seen and pairs.

**5. Edge cases**

- Multiple duplicates (e.g., [2,2,2], target=4) — works because once one 2 is seen, each subsequent 2 finds complement and adds same (2,2) tuple; set deduplicates.- Empty list or no pairs -> returns [].- Large inputs: memory proportional to unique numbers and found pairs.

**6. Alternatives / notes**

- If deterministic ordering required, sort final list (O(k log k)) where k is number of pairs.- For counts-sensitive results (e.g., return as many pairs as possible without reuse), use Counter and different logic.

MediumSystem Design

22 practiced

How would you design a persistent dictionary for a backend service that preserves a hash-based map across restarts with minimal downtime? Discuss snapshotting, write-ahead logs, on-disk hash table formats (for example LevelDB/RocksDB), and how to handle resizing and concurrent access during recovery.

Sample Answer

**Clarify goals & constraints**- Persist an in-memory hash map across restarts with minimal downtime, strong durability for acknowledged writes, and support concurrent reads/writes during normal operation and recovery.

**High-level design**- Combine write-ahead log (WAL) + periodic snapshot (checkpoint). Use an on-disk LSM-store (LevelDB/RocksDB) or custom mmap’d hash-file for compact storage and fast recovery.

**Components**- WAL: append-only file(s) for every mutating operation. Each entry = key, op, value, checksum, sequence number. fsync on commit (configurable for latency/durability).- Snapshot: Background thread creates consistent snapshot of the in-memory hash (or compacts WAL to SSTables) and rotates WAL. Snapshots are copies of the current state stored as SSTable or serialized hash buckets.- Storage engine: Prefer LevelDB/RocksDB for production — they handle compaction, bloom filters, durability, and efficient point lookups. For simple workloads, a memory-mapped hash table file with chaining can be used.

**Recovery & resizing**- On startup: load latest snapshot (fast) then replay WAL entries with seq > snapshot_seq. Replay can be multi-threaded by sharding WAL per partition.- Resizing: Keep fixed-number-of-buckets metadata in snapshot. For in-place mmap’d hash, perform resize as background operation producing a new table file; switch atomically (rename + pointer swap) after population. For LevelDB, resizing is handled by key-space rebalancing (no explicit resize).

**Concurrent access during recovery**- Use two-phase startup: - Phase 1 (read-only): serve reads from disk-backed store (LevelDB) while WAL replay builds in-memory cache asynchronously. - Phase 2 (full): after replay or when certain partitions are ready, promote to serve writes. Alternatively accept writes during recovery by appending them to a new WAL; ensure replay ordering by sequencing WAL files and applying older WALs then newer.- Locks: per-shard locks or RCU-style pointer swaps to avoid global blocking.

**Trade-offs**- LevelDB/RocksDB: less implementation effort, robust, but heavier dependency and compaction I/O.- Custom mmap hash: lower runtime overhead, more control for zero-copy, but harder to implement correct compaction/resizing and crash-safety.

**Operational notes**- Rotate WALs frequently; keep retention window for debugging.- Test crash scenarios and WAL/snapshot corruption handling.- Expose configuration: fsync policy, snapshot interval, shard count to balance latency vs durability.

HardTechnical

30 practiced

Provide a formal argument proving that using dynamic array doubling (capacity *= 2) for hash table capacity yields amortized O(1) insertion cost. Analyze alternative growth factors (for instance 1.5x) and their impact on both time (amortized cost) and space (wasted capacity). Discuss when a smaller growth factor may be preferable for memory-limited services.

Sample Answer

**Claim & approach (aggregate amortized analysis)** When resizing by doubling (capacity *= 2), sequence of n insertions from empty array costs O(n) total, so amortized O(1) per insert. Use aggregate method: count actual insert cost = 1; resizing cost = copying k elements when growing from k to 2k.

**Formal sum of copy costs** Each element gets copied at most once per doubling level. Over n inserts, total copy work ≤ sum of powers of two ≤ 2n. Formally:

text

Total copy cost ≤ 1 + 2 + 4 + ... + 2^{⌊log n⌋} ≤ 2n

So total work = n (inserts) + ≤2n (copies) = O(n) ⇒ amortized insertion cost = O(1).

**Alternative growth factor α (1 < α ≤ 2)** Resize when size = capacity; new capacity = ⌈α·capacity⌉. Total copy cost over n inserts is bounded by geometric series:

text

Total copies ≤ n · (1/(α - 1))

Plain-English: as α → 1+, cost multiplier blows up; as α = 2, coefficient = 1/(2-1)=1 (matches earlier constant).

Amortized cost per insert = O(1 + 1/(α - 1)) constant.

**Space (wasted capacity)** Expected wasted fraction ≈ (α - 1)/α on average (between half-full for α=2, and smaller for α near 1). Average wasted ≈ (α/(α - 1) - 1) derivable from geometric distribution; simpler view: after resize you have (α - 1)/α empty fraction.

**Trade-offs & when to use smaller α** - Larger α (2): fewer resizes, lower amortized constant, higher peak wasted memory (up to ~50%). Good for latency-sensitive services. - Smaller α (1.5 or 1.25): lower memory waste (e.g., α=1.5 wastes ~33%), but more frequent copies; amortized constant increases ~1/(α-1). Use when memory constrained (embedded, multi-tenant services) or when working set size is large relative to available RAM. Also consider copying cost: if copying is cheap (primitive array) smaller α is acceptable; if copying triggers heavy object moves/GC, prefer larger α.

**Practical guidance for backend systems** - Default α=2 is safe for general-purpose servers. - Use α≈1.5 for memory-limited environments or when minimizing peak footprint is critical. - Measure: benchmark real workloads (copying cost, GC pressure) and pick α balancing latency and memory.

EasyTechnical

27 practiced

Explain the concept of load factor in hash tables. Describe how load factor influences resizing behavior, memory usage, and amortized performance of insertions. Include common resizing strategies (doubling, incremental resizing) and their pros/cons for backend services serving latency-sensitive requests.

HardSystem Design

29 practiced

Design a thread-safe concurrent hash map suitable for a backend service that needs high concurrency. Describe lock striping (bucket-level locking), per-bucket locks, lock-free alternatives using compare-and-swap (CAS), and strategies to handle resizing without acquiring a global lock. Reference Java's ConcurrentHashMap design in your explanation.

Sample Answer

**Clarify goal & constraints**Design a hash map that supports very high read/write concurrency, low latency for common ops (get/put/remove), and safe resizing without a global pause. Assume JVM-like memory model.

**Lock striping / per-bucket locks**- Partition buckets into independent lock units (either one lock per bucket or N locks covering multiple buckets). - On put/remove: lock only the corresponding stripe (lock = locks[hash % numLocks]). On get: do an optimistic volatile read first; only acquire lock on observed inconsistency. - Benefits: reduces contention vs a single global lock; simple correctness model. Costs: more memory for locks and possible hotspot if keys collide.

**Lock-free alternatives (CAS)**- Use CAS on bucket head pointers (AtomicReference<Node>) and immutable Node objects or compare-and-swap updates to Node.next. - Implement put as: read head, create new Node pointing to old head, attempt CAS to swap head. For replace/update, use CAS loops to replace target Node by copying chain with modification then CAS head (or use AtomicStampedReference for versioning). - Benefits: no blocking, better latency under contention. Costs: complex memory management, ABA problems, longer CAS loops under contention.

**Resizing without a global lock**- Incremental/parallel transfer: allocate a new table and move buckets gradually. Writers accessing bucket i check if resize in progress and help transfer that bucket (work-stealing). Reads consult both tables until bucket is transferred. - Java 8 ConcurrentHashMap approach: uses bin-level synchronization for treeify and CAS-based table initialization; resizing is done with multiple threads cooperating using a transferIndex to claim ranges. No single global lock; parts of table marked as forwarded so readers follow to new table. - Ensure size accounting uses atomic counters (LongAdder) to avoid central contention.

**Trade-offs & best practices**- Start with lock striping for simplicity; move to CAS-based buckets if low-latency under heavy contention is required. - Use volatile and atomic primitives for visibility; avoid per-entry locks. - Provide metrics and backoff to detect hotspots; consider rehashing policy tuned to throughput.

This mirrors Java's ConcurrentHashMap evolution: segments -> per-bin CAS + treeify + cooperative, non-blocking resizing.

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.