Arrays and Hash Map Operations Questions

Covers algorithmic patterns that use arrays together with hash based maps or dictionaries to achieve efficient lookup and counting. Topics include frequency counting, duplicate detection, two sum and k sum variants, sliding window with counts, index mapping, grouping by keys, and using hash maps to reduce time complexity from quadratic to linear. Emphasize insertion deletion and lookup costs, collision and memory considerations, trade offs between using hash maps versus sorting or two pointer techniques, and typical interview problem families that rely on combining arrays with associative containers.

HardSystem Design

43 practiced

Design architecture for distributed embedding table lookups and updates across multiple GPUs during model training. Focus on hash-map-like structures mapping sparse feature indices to embedding vectors, consistency of updates across GPUs, memory constraints per GPU, and latency for forward/backward passes. Discuss model-parallel sharding, parameter server patterns, and caching hot embeddings on GPU.

Sample Answer

Requirements & constraints:- Functional: map sparse feature indices -> embedding vectors; support forward lookup and gradient updates during training.- Non-functional: per-GPU memory limits, low lookup latency for forward/backward, high update throughput, consistency across GPUs, fault tolerance.

High-level architecture:- Hybrid model-parallel sharding + parameter-server (PS) pattern with GPU-side caches.- Global Embedding Store: sharded across N parameter servers (each PS = one or more GPUs or CPU+GPU) using hash-based consistent sharding by index range or mod(hash,index) to evenly partition keys.- Worker GPUs run training; each worker has: - Local GPU embedding cache (LRU or frequency-based) holding "hot" embeddings. - Async fetcher to PS for misses and write-back buffer for updates. - Sparse-feature aggregator that dedups indices per micro-batch to reduce RPCs.

Data flow:1. Forward: worker dedups indices → lookup local cache (O(1) hashmap on GPU) → missing keys batched and fetched from PS (RPCs, compressed & pinned memory) → populate cache → perform embedding lookup and forward compute.2. Backward: compute gradients for unique indices → accumulate per-key gradients locally → either - Synchronous mode: all-reduce per-shard across workers then apply on PS (consistent updates), or - Asynchronous mode: send gradient updates to owning PS, PS applies with atomic add; PS periodically pushes fresh embedding deltas to workers.3. Consistency: offer two modes: - Strong: synchronous gradient aggregation across workers + barrier apply — consistent but higher latency. - Eventual/Relaxed: async updates with versioning and staleness bounds; enforce TTL or version checks for critical features.

Key components & data structures:- PS shard: on-GPU hash table (open addressing/CUCKOO) storing key → embedding vector + version + lock/atomic apply. Use GPU-friendly hashmap libs (e.g., cuco) or CPU-resident hash with pinned buffer for large shards.- Worker cache: GPU hash map + bloom filter to avoid frequent PS lookups; metadata stores last-update-version to detect staleness.- RPC & batching: group requests by PS shard, compress sparse IDs and gradients, use RDMA/NCCL or gRPC with protobuf for control.

Memory & latency optimizations:- Quantize embeddings (FP16/INT8) in cache; store master copy in FP32 on PS for numerical stability; dequantize for compute.- Gradient accumulation and sparsity-aware batching reduce network overhead.- Pre-fetching based on access patterns and short-term LRU+LFU hybrid caching.- Use pinned host buffers and CUDA IPC/RDMA to minimize copy latency.

Scalability & trade-offs:- Sharding across PS scales capacity and write throughput; but increases cross-network latency for misses.- Fully sharded model-parallel (each GPU owns a disjoint embedding shard) minimizes network during update but requires cross-GPU all-gather for forward if features distributed—works best when feature locality per worker is high.- Parameter-server simplifies ownership and atomicity; model-parallel reduces network if data placement aligned.- Strong consistency increases sync overhead; eventual consistency improves throughput but may harm convergence—recommend hybrid: strong for rare critical features, relaxed for long-tail features.

Fault tolerance & operations:- PS shards checkpoint to distributed storage asynchronously; workers can fetch replacements.- Rebalance shards using consistent hashing; maintain cold storage (disk) for very large embedding vocab.

Example numbers (engineering guidance):- Batch dedup can reduce unique keys per batch by 5–20x.- Aim for PS batching latency <1–2ms per RPC; cache hit rate >90% for tail latency under 5ms.- Use mixed precision and 4–8 byte embeddings compressed to balance memory vs accuracy.

This design supports low-latency forward/backward with tunable consistency, scales by adding PS shards, and leverages GPU caching and quantization to respect per-GPU memory limits.

MediumTechnical

44 practiced

Implement 'all_pairs(nums, target)' in Python that returns a list of unique pairs of values (not indices) that sum to target. The input may contain duplicates but output should not include duplicate value pairs. Example: nums=[1,1,2,3,2], target=3 -> [[1,2]]. Use a hashmap to count values and explain handling of (x,x) pairs.

Sample Answer

Approach:Use a hashmap (Counter) to count occurrences of each value. Iterate over unique values; for each x compute y = target - x. To avoid duplicate value-pairs, only emit pair (min(x,y), max(x,y)) once — e.g., iterate keys in sorted order or ensure x <= y before adding. For the special case x == y, require count[x] >= 2.

python

from collections import Counter

def all_pairs(nums, target):
    """
    Return list of unique value pairs [a, b] (a <= b) where a + b == target.
    Uses a hashmap for counts and avoids duplicate value pairs.
    """
    counts = Counter(nums)
    result = []
    # iterate through sorted unique keys to ensure determinism and avoid duplicates
    for x in sorted(counts):
        y = target - x
        if y < x:
            # already considered when x was smaller
            continue
        if y not in counts:
            continue
        if x == y:
            # need at least two occurrences to form a pair (x, x)
            if counts[x] >= 2:
                result.append([x, y])
        else:
            result.append([x, y])
    return result

Key points:- Using Counter gives O(n) to build counts.- Sorting unique keys costs O(k log k) where k is distinct values; you can avoid sorting by using a set and checking x <= y to prevent duplicates.Time complexity: O(n + k log k) with sorting, or O(n + k) without sorting. Space: O(k).Edge cases:- Empty list -> [].- All identical values -> only include [x,x] if count >= 2.- Negative numbers handled naturally.

HardSystem Design

35 practiced

Design a system to deduplicate 10 billion text documents (avg 2KB) at ingest time with expected duplicate fraction 5%. Requirements: near-real-time detection (<1s per doc), false positive rate < 1e-6, throughput 50k docs/sec, incremental updates allowed. Describe hashing strategy, sharding, storage choices, collision handling and verification, memory estimates, and fallback strategies.

Sample Answer

Requirements clarification:- 10B docs (~2KB each), ~5% duplicates → ~9.5B unique keys.- R/T ≤1s/doc, throughput 50k/s, FP <1e-6, incremental ingest.

Overall approach (two-stage fingerprint + distributed sharding):1) Hashing strategy- Fast fingerprint: non-cryptographic 64-bit (xxh3 or CityHash) for routing and quick reject.- Strong verification: SHA-256 (or BLAKE2b-256) computed for any candidate match to guarantee correctness.- Normalize text prior to hashing (unicode normalization, whitespace, lowercasing, optional stopword removal) to avoid superficial duplicates.

2) Sharding & routing- Partition by fast fingerprint: shard = hash64(doc) mod N. Choose N so per-shard load ≈ 50k/N docs/sec. For 50k/s, N=200 → 250 docs/s/shard; pick N=256 or 512 for headroom.- Use consistent hashing to allow resharding with minimal movement. Route via a lightweight gateway (stateless) or client-side hashing.

3) In-memory index + persistent store- Per shard keep: - Bloom filter in RAM for O(1) reject with target FP p_total ≤1e-6. - Small in-memory cache (LRU) of most recent fingerprints.- Persistent backing store: RocksDB / Cassandra / Scylla per shard storing {sha256: metadata, ref-count, doc-id, timestamp}. Use LSM for write throughput.

Bloom filter sizing (estimate)- n ≈ 10e9; target p = 1e-6.- m ≈ -n * ln p / (ln2)^2 ≈ 2.87e11 bits ≈ 36 GB total RAM across system.- k (hashes) ≈ (m/n) ln2 ≈ ~20 hash functions.- Distribute Bloom filter shards so each shard stores ~36GB/N. With N=256 → ~140MB/shard.

Memory & CPU estimates- Bloom filters: ~36GB total.- Per stored SHA-256 index: 32 bytes-key + 8–16 bytes metadata ≈ 50 bytes * 9.5B ≈ 475GB persistent (on-disk); use compression and column store to reduce.- In-memory hot-cache: per shard 1–4GB for BTS/metadata and LRU.- CPU: hashing (xxh3 + sha256) at 50k/s — modest: use multi-core per shard; hardware SHA acceleration if available.

Detection flow (per doc)1. Normalize -> compute xxh3_64.2. Route to shard and check shard Bloom filter: - If Bloom says "not present" → accept as new; write sha256 to persistent store, update Bloom. - If Bloom says "possibly present" → fetch candidate(s) by fast fingerprint from store (index keyed by first 64 bits or full sha256 index).3. Compute SHA-256 of normalized content and compare against stored hashes for exact match: - If equal → declare duplicate. - If unequal → hash collision or near-duplicate; treat as distinct (store new sha256) and log collision metrics.

Collision handling & verification- Use SHA-256 to make true FP negligible; Bloom false positives cause only extra lookups, not wrong dedup decisions.- If SHA-256 matches → duplicate. If SHA-256 mismatch but same 64-bit prefix, this is acceptable rare collision; increase fingerprint width if collisions high (move to 128-bit fast fingerprint).- Optionally, keep a count of collisions per shard; if spike, audit.

Throughput & latency optimizations- Batch writes to RocksDB and use WAL; write path async: accept-and-ack after persistent write enqueued (if strict durability required, wait for commit).- Use SSDs with high IOPS per shard; tune compaction/GC.- Use goroutines/threads per shard and lock-free data structures.- Keep bloom filter fully in RAM to keep rejects O(1) and under 1s.

Fallback and robustness- Backpressure: if shard CPU or I/O saturates, gateway applies rate-limit or routes to spare shards.- Graceful resharding: consistent hashing + streaming replication to new shard nodes.- Near-duplicate handling: optional LSH/minhash stage for fuzzy dedupe (slower, asynchronous) if semantic dedupe needed.- Cold-start: rebuild bloom filters from persistent store in background; use persisted bitmaps to accelerate.

Trade-offs- Bloom filter memory (~36GB) is modest vs disk index (~0.5TB). Prioritizes RAM to keep per-doc latency <1s.- Two-stage hashing guarantees FP << 1e-6 while keeping routing fast.- Exact dedupe (sha256) prevents false positives; Bloom only reduces disk hits.

Metrics & monitoring- FP/FN rates, Bloom hit/miss, SHA-256 collision rate, per-shard latency, queue sizes. Alert and autoscale when per-shard 95th latency > target.

This design meets <1s per doc, 50k/s throughput, incremental updates, and FP << 1e-6 while keeping memory and storage within practical bounds.

MediumTechnical

64 practiced

Given an array of event intervals represented as (start, end), compute the maximum number of concurrent events. Implement using a hashmap-based sweep-line that records +1 at start and -1 at end then sweeps sorted keys. Explain time/space trade-offs and how to adapt the approach for streaming workloads with bounded memory.

Sample Answer

To compute the maximum number of concurrent events we can use a hashmap (dict) as a sweep-line: add +1 at each start timestamp and -1 at each end timestamp, then iterate timestamps in sorted order accumulating a running sum and tracking the max.

python

def max_concurrent(events):
    """
    events: list of (start, end) where end is exclusive or inclusive depending on spec.
    Treating end as exclusive here (event active for t in [start, end)).
    """
    if not events:
        return 0

    delta = {}
    for s, e in events:
        delta[s] = delta.get(s, 0) + 1
        delta[e] = delta.get(e, 0) - 1

    max_active = 0
    active = 0
    for t in sorted(delta):
        active += delta[t]
        if active > max_active:
            max_active = active
    return max_active

Key points:- Use dict to compactly accumulate changes; sorting keys creates the sweep order.- Time: O(n log n) due to sorting unique timestamps (n = number of intervals; worst-case unique timestamps = 2n). Space: O(m) for m unique timestamps (<=2n).

Edge cases:- Zero-length intervals; decide inclusive/exclusive semantics (adjust where to place -1).- Large coordinate range but few unique timestamps: dict is efficient.

Streaming / bounded-memory adaptation:- Use fixed-size time bucketing (e.g., minute/hour bins) to collapse many timestamps into fewer keys and maintain approximate concurrency.- For sliding-window streaming with exact counts, maintain an ordered dictionary or min-heap of recent timestamp deltas and periodically evict old keys beyond the window.- For very high-cardinality streams, use lossy summaries (count-min sketches per bucket) to approximate counts with bounded memory, accepting probabilistic error.

EasyTechnical

38 practiced

Explain how Python's dict is implemented under the hood: hash table strategy, collision resolution, resizing policy, and the guarantee of insertion-order preservation (Python 3.7+). Discuss why hash collisions can be a security vector and what that implies for services that accept untrusted keys.

Unlock Full Question Bank

Get access to hundreds of Arrays and Hash Map Operations interview questions and detailed answers.

Join thousands of developers preparing for their dream job.