Probabilistic Data Structures & Hashing Questions

Covers probabilistic data structures (e.g., Bloom filters, Count-Min Sketch, HyperLogLog, Cuckoo filters) and hashing techniques, including space-time trade-offs, false positive rates, distinct element estimation, and practical applications in databases, caches, streaming analytics, and network systems.

MediumTechnical

39 practiced

Implement a thread-safe Count-Min Sketch in Java or Scala with API: constructor(width int, depth int), add(String key, long count), estimate(String key): long, merge(CountMinSketch other), serialize()/deserialize(). Describe your choice of hashing per row and concurrency primitives to allow high update throughput in multi-threaded environments.

Sample Answer

Approach: implement Count-Min Sketch with depth independent rows each using an AtomicLongArray for counters. Use MurmurHash3 (128-bit) seeded per row to produce uniform, independent hashes; map to column by (hash & 0x7fffffff) % width. For concurrency, AtomicLongArray.addAndGet provides lock-free increments with high throughput; estimate reads use atomic gets (no locking). merge() performs element-wise atomic adds; serialize() writes primitive fields + per-row counts and seeds; deserialize() reconstructs arrays.

java

// Java 11
import java.io.*;
import java.nio.ByteBuffer;
import java.util.concurrent.atomic.AtomicLongArray;
import java.util.concurrent.ThreadLocalRandom;
import com.google.common.hash.Hashing; // or implement Murmur3 yourself

public class CountMinSketch implements Serializable {
  private final int width, depth;
  private final AtomicLongArray[] table;
  private final int[] seeds;

  public CountMinSketch(int width, int depth){
    this.width = width; this.depth = depth;
    this.table = new AtomicLongArray[depth];
    this.seeds = new int[depth];
    for(int i=0;i<depth;i++){
      table[i] = new AtomicLongArray(width);
      seeds[i] = ThreadLocalRandom.current().nextInt();
    }
  }

  public void add(String key, long count){
    byte[] k = key.getBytes();
    for(int row=0; row<depth; row++){
      int hash = Hashing.murmur3_32(seeds[row]).hashBytes(k).asInt();
      int col = (hash & 0x7fffffff) % width;
      table[row].addAndGet(col, count); // atomic increment
    }
  }

  public long estimate(String key){
    byte[] k = key.getBytes();
    long min = Long.MAX_VALUE;
    for(int row=0; row<depth; row++){
      int hash = Hashing.murmur3_32(seeds[row]).hashBytes(k).asInt();
      int col = (hash & 0x7fffffff) % width;
      long v = table[row].get(col);
      if(v < min) min = v;
    }
    return min == Long.MAX_VALUE ? 0L : min;
  }

  public void merge(CountMinSketch other){
    if(other.width != width || other.depth != depth) throw new IllegalArgumentException("dims mismatch");
    for(int r=0;r<depth;r++){
      AtomicLongArray src = other.table[r];
      AtomicLongArray dst = this.table[r];
      for(int c=0;c<width;c++){
        long v = src.get(c);
        if(v!=0) dst.addAndGet(c, v);
      }
    }
  }

  public byte[] serialize() throws IOException {
    ByteArrayOutputStream baos = new ByteArrayOutputStream();
    DataOutputStream out = new DataOutputStream(baos);
    out.writeInt(width); out.writeInt(depth);
    for(int s: seeds) out.writeInt(s);
    for(int r=0;r<depth;r++) for(int c=0;c<width;c++) out.writeLong(table[r].get(c));
    out.flush(); return baos.toByteArray();
  }

  public static CountMinSketch deserialize(byte[] bytes) throws IOException {
    DataInputStream in = new DataInputStream(new ByteArrayInputStream(bytes));
    int w = in.readInt(), d = in.readInt();
    CountMinSketch cms = new CountMinSketch(w,d);
    for(int i=0;i<d;i++) cms.seeds[i] = in.readInt();
    for(int r=0;r<d;r++) for(int c=0;c<w;c++) cms.table[r].set(c, in.readLong());
    return cms;
  }
}

Key choices / reasoning:- Hashing: Murmur3 with different per-row seeds approximates pairwise independence and is fast.- Concurrency: AtomicLongArray.addAndGet is lock-free per cell — excellent for many concurrent writers; reads are simple atomic gets.- Merge: element-wise atomic adds avoid global locks; caller must ensure semantics if concurrent merges/updates occur.Complexity: add and estimate O(depth). Space O(width * depth). Edge cases: negative counts (reject), dimension mismatch on merge, and potential overflow (use long, check for overflow on add). Alternatives: use LongAdder per cell for better contended counters (higher memory), or striped locking for very large width to reduce atomic array memory overhead.

EasyTechnical

30 practiced

Explain Locality-Sensitive Hashing (LSH). Describe concrete LSH families used for cosine similarity (SimHash) and Jaccard similarity (MinHash), how banding or buckets work, and give a data-engineering example where LSH would be applied in a streaming pipeline to find near-duplicates.

Sample Answer

Locality-Sensitive Hashing (LSH) is a family of hashing techniques that map similar items to the same buckets with high probability, enabling sub-linear approximate nearest-neighbor or near-duplicate search in high-dimensional data.

SimHash (for cosine similarity / angular distance)- Idea: project a high-dimensional vector onto multiple random hyperplanes. For each hyperplane, a bit = 1 if projection ≥ 0 else 0. The resulting bit-string (fingerprint) has Hamming distance proportional to angle between vectors, so similar vectors collide frequently.- Practical: use 64–256 bits. Compare by Hamming distance or use buckets built from bit-prefixes.

MinHash (for Jaccard similarity)- Idea: treat sets (e.g., shingled documents). Apply many independent random permutations (or hash functions) and record the minimal hashed element per permutation. The probability two sets have the same min-hash equals their Jaccard similarity.- Practical: use 100–200 permutations to estimate similarity accurately.

Banding / Bucketing- To amplify true positives and reduce false positives, split a long fingerprint/signature into b bands of r rows (so br = signature length). Hash each band to a bucket; items that share a bucket in any band are candidate pairs. Banding trades recall vs precision: more bands (smaller r) increases recall, fewer bands (larger r) increases precision.

Streaming pipeline example (data-engineer)- Use LSH to detect near-duplicate news articles in real time: - Ingest articles via Kafka, generate shingles and compute MinHash signatures with a streaming library (Spark Streaming / Flink). - Apply banding: for each band compute a bucket key, write (bucket_key, doc_id, signature) to a fast KV store (Redis, RocksDB) or stateful operator keyed by bucket. - When a new doc hashes to an existing bucket, emit candidate pairs for final verification (exact Jaccard on shingles). If duplicate, mark or dedupe downstream (drop, merge metadata). - Scale: keep only recent buckets / use TTLs, partition buckets by hash prefix, and batch signature computations for throughput. This reduces expensive pairwise comparisons and fits low-latency streaming deduplication needs.

EasyTechnical

36 practiced

Implement a BloomFilter class in Python with the following API: BloomFilter(m: int, k: int), add(item: bytes), might_contain(item: bytes)->bool. Use double hashing to derive k indices: h1 = murmur3_64(item, seed=0), h2 = murmur3_64(item, seed=1), and index_i = (h1 + i * h2) % m. Use Python's bytearray or built-in types for bit storage and document time/space complexity.

Sample Answer

We can implement a simple Bloom filter using double hashing with murmur3 64-bit (via the mmh3 library). We'll store bits in a bytearray and compute k indices as index_i = (h1 + i*h2) % m (taking unsigned modulo). Time for add / query is O(k); space is O(m) bits.

python

import mmh3

class BloomFilter:
    def __init__(self, m: int, k: int):
        """
        m: number of bits in the filter
        k: number of hash functions (using double hashing)
        """
        if m <= 0 or k <= 0:
            raise ValueError("m and k must be positive")
        self.m = m
        self.k = k
        self.bitarray = bytearray((m + 7) // 8)  # compact bit storage

    def _set_bit(self, idx: int):
        byte_idx = idx // 8
        bit = idx % 8
        self.bitarray[byte_idx] |= (1 << bit)

    def _get_bit(self, idx: int) -> bool:
        byte_idx = idx // 8
        bit = idx % 8
        return (self.bitarray[byte_idx] >> bit) & 1 == 1

    def _indices(self, item: bytes):
        # mmh3.hash64 returns signed ints; convert to unsigned 64-bit
        h1, h2 = mmh3.hash64(item, seed=0)[0], mmh3.hash64(item, seed=1)[0]
        # ensure positive by masking to 64-bit unsigned
        h1 &= 0xFFFFFFFFFFFFFFFF
        h2 &= 0xFFFFFFFFFFFFFFFF
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, item: bytes):
        for idx in self._indices(item):
            self._set_bit(idx)

    def might_contain(self, item: bytes) -> bool:
        for idx in self._indices(item):
            if not self._get_bit(idx):
                return False
        return True

Key points:- Uses double hashing to derive k indices from two 64-bit hashes (saves cost of k independent hashes).- Space: O(m) bits (~m/8 bytes). Time: O(k) per add/query.Edge cases:- Non-bytes input: caller should pass bytes (use item.encode()).- mmh3 must be installed (pip install mmh3). If unavailable, implement or substitute a stable 64-bit hash.- Beware signed/unsigned conversion when using Python wrappers for murmur.

EasyTechnical

37 practiced

Explain HyperLogLog (HLL) at a high level: what quantity it estimates, how it uses stochastic averaging and leading-zero counts, the role of the precision parameter p (number of registers = 2^p), typical space complexity and approximate error as a function of p. Provide two practical cases where HLL is preferable to exact counting in a data engineering stack.

HardTechnical

37 practiced

Compare MinHash (for Jaccard similarity) and SimHash (random projection for cosine similarity): explain how each constructs a compact sketch, the types of similarity they approximate, expected sketch sizes for a target error, and recommend which to use for near-duplicate document detection in a streaming ETL pipeline that uses shingling.

Sample Answer

Brief answer: MinHash builds compact sketches by hashing set elements and keeping k minimum hash values; it unbiasedly estimates Jaccard similarity. SimHash (random projections) hashes weighted feature vectors with d random hyperplanes and stores d bits (signs); bitwise Hamming similarity estimates cosine similarity (collision prob = 1 - θ/π where θ is angle).

How sketches are constructed and updated in a stream:- MinHash: choose k independent hash functions; for each incoming shingle, compute k hashes and update each sketch position = min(current, hash). One-pass, mergeable (component-wise min), good for set-based shingling.- SimHash: choose d random vectors; for each token add its weight times the random vector to an accumulator; final sketch = sign of accumulators (d bits). In streaming you incrementally update accumulators; mergeable by summing accumulators.

Similarity approximated:- MinHash ≈ Jaccard(S1,S2) with unbiased estimator = fraction of equal min-hashes.- SimHash ≈ 1 - θ/π; for sparse TF-IDF vectors this approximates cosine similarity.

Expected sketch sizes / error:- Both estimators have standard error ~ O(1/√m) where m=k (MinHash) or d (SimHash). To get error ε (std), need m ≈ 1/ε². Practical rules: for ±0.05 error, m≈400; for ±0.1, m≈100.- In bits: MinHash stores k hashes (e.g., 64-bit) → 64k bits; SimHash stores d bits (e.g., 64–256 bits). So SimHash is much smaller for same m if MinHash uses full 64-bit hashes; MinHash can compress hashes (e.g., 32-bit) or use permutation hashes.

Trade-offs and practical recommendation for streaming ETL with shingling:- Use MinHash when you explicitly use shingle sets and care about Jaccard (near-duplicate documents based on shingles). It aligns exactly with shingling, supports easy LSH banding for candidate generation, and merges trivially across partitions—important for distributed ETL (Spark, streaming).- Use SimHash if you must minimize memory aggressively, need super-fast bit operations, or care about cosine on weighted TF vectors rather than set overlap. SimHash is sensitive to token weighting; collisions less interpretable for Jaccard.- For near-duplicate detection on shingled documents in a streaming ETL pipeline, I recommend MinHash (k in 128–512 range depending on desired error), combined with MinHash LSH (banding) for blocking. Use 32-bit hashes to reduce footprint, keep k≈200 for ~0.07 std error, and implement mergeable MinHash sketches in your streaming/partitioned pipeline. If memory is ultra-constrained, fallback to 64–128-bit SimHash but validate false-positive/negative trade-offs on your data.

Unlock Full Question Bank

Get access to hundreds of Probabilistic Data Structures & Hashing interview questions and detailed answers.

Join thousands of developers preparing for their dream job.