Probabilistic Data Structures

Bloom Filters: Approximate Set Membership

A Bloom filter answers is X in the set with two possible responses: definitely not, or probably yes. It is a bit array of m bits with k independent hash functions; to add an element, hash it k ways and set those k bits; to query, check the k bits, and if any is zero the element was definitely never added (no false negatives), while all ones means probably present (false positives possible, because other elements may have set those bits). The math is friendly: about 9.6 bits per element gives a 1 percent false positive rate regardless of element size, so 100 million URLs fit in roughly 115MB versus many gigabytes for the strings themselves. Optimal k is around (m/n) ln 2, typically 7 hashes for that 1 percent target.

The canonical uses exploit the one-sided error. LSM-tree databases (Cassandra, RocksDB, HBase, LevelDB) keep a Bloom filter per SSTable so a read for a missing key skips the disk entirely: definitely not here means no I/O, and the occasional false positive just costs one wasted read. Content and cache systems use them to avoid caching one-hit wonders (Akamai found roughly 75 percent of URLs were requested exactly once, so they cache only on second request, using a Bloom filter to remember first sightings). Browsers historically used them for malware URL prescreening, and databases use them for distributed joins (ship a Bloom filter of join keys instead of the keys themselves).

Limits to volunteer: a standard Bloom filter supports no deletion (clearing bits would create false negatives; counting Bloom filters fix this at 4x space) and no enumeration, and the false positive rate degrades as it fills beyond its design capacity, so you size it for expected n up front or use scalable variants. The design question it answers in interviews is always the same shape: an expensive lookup (disk, network, database) dominated by misses, and a tiny in-memory filter that eliminates most of them.

Count-Min Sketch: Approximate Frequencies

A count-min sketch estimates how many times each item has appeared in a stream using fixed memory, regardless of how many distinct items exist. It is a 2D array of counters with d rows (one hash function each) and w columns; to record an item, hash it once per row and increment the d chosen counters; to query, take the minimum of the d counters. Collisions only inflate counters, so the estimate never undercounts, it only overcounts, with error bounded by epsilon times the total stream size with probability 1 minus delta, where w = e/epsilon and d = ln(1/delta). Concretely, a sketch of a few kilobytes (say 5 rows by 2,000 columns of 4-byte counters, about 40KB) tracks frequencies over streams of billions of events.

Because the guarantee is one-sided overcounting that hurts rare items proportionally more, the sketch shines for heavy hitters: which items are hot, not the exact count of a cold one. That is exactly the shape of real problems: top-K trending hashtags or searches, hot keys in a cache or shard (detecting the celebrity whose key needs special handling), per-IP request counting for approximate rate limiting or DDoS detection, and finding heavy flows in network switches. Pair it with a small heap of the current top K candidates and you get the standard streaming top-K design.

When an interviewer asks for trending topics over the last hour across millions of events per second, the expected answer combines a count-min sketch (frequencies in bounded memory), a min-heap of the K best, and a windowing scheme (per-minute sketches that are summed or rotated, since sketches merge by element-wise addition, which also makes them shard-friendly: each server sketches locally, a coordinator merges).

HyperLogLog: Counting Distinct Elements

HyperLogLog (HLL) estimates the number of distinct elements in a stream using about 12KB of memory for cardinalities into the billions, with a standard error of roughly 0.81 percent at the common 2^14-register configuration. The intuition: hash every element uniformly, and observe the maximum number of leading zero bits seen; seeing a hash starting with k zeros is a 2^-k event, so witnessing many leading zeros implies many distinct elements were hashed. One maximum is far too noisy, so HLL splits elements into 16,384 buckets by their first 14 hash bits, tracks the max leading-zero count per bucket, and combines the bucket values with a harmonic mean plus bias corrections. Duplicates hash identically, so they cannot move any maximum, which is precisely why the structure counts distinct elements.

The exact problem it solves is brutal at scale: distinct requires remembering every element seen, so counting unique visitors among a billion events needs gigabytes per counter, times every (page, day, country) combination you want. HLL makes each counter 12KB and, critically, mergeable: the union of two HLLs is the element-wise max of their registers, so per-hour or per-server sketches roll up losslessly into daily or global counts, which is exactly what pre-aggregated analytics needs. Redis ships it natively (PFADD, PFCOUNT, PFMERGE), Google's systems process HLL++ at scale (BigQuery's APPROX_COUNT_DISTINCT), and Reddit famously used HLL to serve live unique-view counts on posts.

Caveats: HLL supports union beautifully but not deletion, and intersections only indirectly via inclusion-exclusion with compounding error. The interview trigger phrase is count unique X at scale where a small error is acceptable: unique visitors, distinct search queries, distinct IPs hitting an endpoint.

Geohashing and Quadtrees: Indexing Space

Geospatial queries (find drivers within 2km) defeat ordinary B-tree indexes because two-dimensional proximity does not map to one-dimensional order: an index on latitude alone returns a planet-wide band. Geohash solves this by interleaving the bits of latitude and longitude and encoding the result in base32, producing strings where a shared prefix implies spatial proximity: each added character subdivides the cell, with 5 characters being roughly 4.9 x 4.9 km and 6 characters roughly 1.2 x 0.6 km. Proximity search becomes a string prefix query any database can do, and cell IDs become natural shard keys and pub/sub channels. The classic gotcha to volunteer: prefix similarity is one-directional (shared prefix implies near, but near does not imply shared prefix), because cells on opposite sides of a boundary, or at the equator or antimeridian, are adjacent yet share no prefix; correct search therefore queries the cell plus its 8 neighbors.

A quadtree attacks the same problem adaptively: recursively split the plane into four quadrants, but only subdivide nodes that exceed a capacity threshold (say 100 points), so dense downtown areas get deep fine-grained cells while empty ocean stays coarse. This adaptivity is its advantage over fixed geohash grids, which either over-divide sparse areas or under-divide dense ones; the cost is an in-memory tree structure that must be built, rebalanced as points move, and is harder to distribute than a flat key space. Range and k-nearest-neighbor searches descend only the intersecting quadrants, giving logarithmic behavior on realistic distributions.

Real systems mix these with a third option, Google's S2 (hierarchical cells on a sphere via a space-filling curve, avoiding projection distortion and pole/antimeridian pathologies). Uber has used geohash-style cell indexing (and later its own hexagonal H3 grid, whose uniform neighbor distances suit ride-dispatch and surge-pricing math), Redis implements GEOADD and GEOSEARCH on geohash-encoded sorted sets, and Yext/Lyft-scale nearby searches commonly run on quadtree or S2 indexes. In a design-a-proximity-service interview (Yelp, Uber, Find my friends), the expected move is: choose a cell scheme (geohash for simplicity on top of existing key-value infrastructure, quadtree for adaptive density, S2/H3 for global correctness and uniformity), index entities by cell ID, query the covering cells plus neighbors, then exact-distance filter the candidates.

Where They Show Up in Real Systems

The unifying pattern: when the exact answer requires memory or I/O proportional to the data, and the business question tolerates approximately 1 percent error, a probabilistic structure collapses the cost by orders of magnitude. Web-scale companies wire these in everywhere: Cassandra and RocksDB consult Bloom filters before every SSTable read; CDNs use Bloom filters for cache-on-second-hit admission; Redis exposes HyperLogLog as a first-class type and geohash under its geo commands; stream processors like Flink and Druid use sketches (the Apache DataSketches library, born at Yahoo, standardizes HLL, theta sketches, and quantile sketches) for real-time dashboards; network and security gear uses count-min sketches for heavy-hitter and DDoS detection.

A senior candidate also knows the boundaries. These structures are approximate, mostly non-deletable, and their guarantees are one-sided in specific directions (Bloom: false positives only; CMS: overcount only; HLL: small symmetric error), so they belong on the fast path with an exact system of record behind them: the Bloom filter avoids the disk read, but the SSTable is still the truth; the HLL powers the live dashboard, but billing runs an exact batch count. Stating which side the error falls on, and confirming the product can tolerate it, is the difference between name-dropping and engineering.

A quick decision table for interviews: have I seen this before means Bloom filter; how often does each item occur or top K means count-min sketch plus heap; how many distinct means HyperLogLog; what is nearby means geohash, quadtree, or S2/H3 cells. Each answer should come with its memory figure (10 bits per element, tens of KB, 12KB, and cell-indexed rows respectively) because the numbers are the argument.

Tradeoffs