Why these structures show up in interviews
Some systems need to process absolutely massive amounts of data. These problems disproportionately show up in system design interviews as a way to stress-test the depth of your knowledge. For these problems, simple scaling and adding more machines may be insufficient — you'll need to lean on specialized data structures to solve the problem.
But most system design interviews don't actually require you to implement data structures on the fly and aren't focused at this low level, so why bother? In many cases utilizing a specialized data structure will actually change the shape of the solution and make the surrounding system fundamentally different. Understanding these differences is a superpower and can help you design systems that are more efficient, scalable, and performant.
Membership · maybe vs definitely not.
Frequency upper bounds.
Unique count (cardinality).
Percentiles without storing all values.
- Expand your arsenal of potential approaches.
- Highlight specific scenarios where these structures are commonly used.
- Point out common pitfalls and places where you might over-engineer.
Bloom filter
Our first data structure is probably the most well-known. A bloom filter is a probabilistic data structure analogous to a set — you insert elements and check membership.
A hash table gives O(1) insert and lookup, but you need memory for each element. That is infeasible for trillions of IDs. Bloom filters trade exactness for space:
- Maybe in set — with configurable false-positive probability.
- Definitely not in set — when any required bit is zero.
Intuition — villager stamps
Pretend we have a village with 1,000 people, each with a unique stamp. We want to track who attended a meeting but only have one pad of paper. Everyone stamps the same sheet. To check attendance, look at whether each person's stamp grooves are fully covered by ink.
- Albert's diagonal stamp grooves present → probably attended.
- Bryan's left-column grooves present → probably attended.
- Christina's square missing → definitely did not attend.
If the paper becomes saturated — every groove filled by overlapping stamps — we can't prove anything about anyone. Same as a bloom filter with all bits set to 1.
How it works
Instead of stamps, use k hash functions. For each insert, hash the value k times and set those bit positions to 1 (bitwise OR into a bit array of size m).
Size the filter by choosing m (bits) and k (hash functions) for your target false-positive rate. The math is straightforward — see Wikipedia for formulas. One surprise in interviews: bloom filters are not orders of magnitude smaller than hash tables. Storing 1B 4-byte elements at 1% false-positive rate needs ~1GB for the bloom filter vs ~5GB for a well-optimized hash table — meaningful (80%) savings, not magic.
Bloom filter — use cases and pitfalls
A bloom filter fits when all three hold:
- You query membership in a set.
- You are space constrained (otherwise use a hash table).
- You can tolerate false positives.
In practice, (1) is common, (2) is rarer as a hard constraint, and (3) is difficult to design around. Interview overlap is strongest with caching and deduplication.
Web crawling
Crawlers traverse a gigantic URL graph. You must avoid re-crawling the same page, but storing every visited URL in a hash table is expensive — URLs are long and the set is huge. A centralized bloom filter answers "we've probably seen this URL" without storing the URL itself. Missing a page occasionally may be acceptable.
Cache guard
Cache-aside: check Redis, on miss run the expensive operation. Every request pays cache lookup latency C; misses pay C + E. A bloom filter in front can skip the cache when the key is definitely absent, saving C on those misses.
Count-Min Sketch
Bloom filters answer "is it in the set?" Many problems need counts. Count-Min Sketch (CMS) estimates how many times an item appeared in a stream — more precisely, it returns an upper bound on the true count.
Intuition — marbles in holes
Instead of stamping paper, dig numbered holes. Each villager is assigned several holes. When they attend a meeting, they drop one marble in each assigned hole. To estimate Albert's attendance, look at the marble counts in his holes and take the minimum — collisions from other villagers only inflate counts, never deflate them.
- Albert's holes show 3 and 2 marbles → attended at most 2 meetings.
- Bryan's holes show 3 and 1 → attended at most 1.
- Christina's holes show 0 and 1 → min is 0 → definitely zero.
One hole for everyone is useless (everyone shares the same upper bound). One hole per person is exact but uses as much space as a hash table — also useless. CMS wins when holes ≪ unique IDs.
How it works
The sketch is a d × w grid of counters. Each row uses a different hash function. On increment, add 1 to the w columns selected by each hash. On query, read those d counters and return the minimum.
- Width w — fewer hash collisions → better accuracy.
- Depth d — more hash rows → higher confidence.
- Error bounds are a function of w and d — not exact counts.
Count-Min Sketch — use cases and pitfalls
CMS fits when:
- You query counts for known item IDs.
- You are space constrained.
- An upper-bound approximation is acceptable.
The sketch does not tell you which items exist — you must already have the ID you are querying.
Top K / trending
Billions of video views — maintain a top-K heap. On each view, increment the video ID in CMS; if the estimated count exceeds the heap minimum, update the heap. Approximate trending with far less memory than a full hash table of all video IDs.
LFU cache hints
LFU eviction needs popularity counts. CMS can track approximate hit frequency and feed a heap of hot keys. Pitfall: if the rest of the system needs exact counts, CMS may not be worth the complexity — Redis uses 16-bit pseudo-counters per key combining recency and frequency instead.
HyperLogLog
Often you need how many unique items, not how many total events — daily active users, distinct search terms, unique IPs. A HashSet grows linearly with unique elements. HyperLogLog (HLL) estimates cardinality in remarkably little memory.
Intuition — longest tail streak
Flip coins until heads. The longest run of tails you've seen correlates with how many flips you've done. In binary hashes, longer leading-zero runs suggest more unique values observed — rare patterns imply a larger set.
How it works
Hash each element. Use the first b bits as a bucket index (2^b buckets). In that bucket, store the maximum leading-zero count (+1) seen so far from the remaining hash bits. Final estimate: harmonic mean of bucket registers, with bias corrections for small/large cardinalities.
HyperLogLog — use cases and pitfalls
HLL fits when you need unique counts at scale, memory is limited, and small estimation error is OK.
- Don't use HLL for exact counts — it won't give them.
- Don't use HLL for tiny sets — overhead with no benefit; use a hash set.
Analytics and metrics
DAU/MAU, unique visitors per page, distinct search terms, unique IPs — update HLL registers in streaming fashion or scan batches offline. Same sketch merges across shards with PFMERGE-style union.
Security / anti-scraping
Block IPs by request volume alone and you hit corporate NATs. A stronger signal: distinct URLs per IP. Real users revisit popular pages; scrapers chase net-new URLs. HLL estimates distinct URL cardinality per IP without storing every URL.
Cache sizing
How many unique keys are accessed? What's the turnover rate? Should the cache partition? HLL answers working-set questions without a giant key set in memory.
Approximate quantiles (histogram buckets)
Percentile questions — "What's p95 latency?" — appear constantly. Exact quantiles require storing and sorting all values. At millions of events per day that's impossible. Histogram bucket algorithms group values into ranges and count per bucket.
Intuition
Track response-time buckets instead of every sample:
| Bucket | Count |
|---|---|
| 0–10ms | 1,000 |
| 10–50ms | 8,000 |
| 50–100ms | 800 |
| 100–500ms | 180 |
| 500ms+ | 20 |
With 10,000 requests: ~98% under 100ms; p95 falls in the 100–500ms bucket; median in 10–50ms — useful distribution insight without storing every measurement.
How it works
On each value: find its bucket, increment that counter. For a quantile, sum counters until you cross the target percentage. Variants:
- Fixed-width buckets — equal ranges; fine when values are uniform.
- Exponential buckets — each range is a multiple of the previous (1–2ms, 2–4ms, 4–8ms…); better for latency power-law tails.
- Dynamic histograms — rebalance boundaries; more accurate, much more complex — rarely worth it in interviews.
Some systems store cumulative counts per bucket (more writes, easier reads). Quantile error is bounded by bucket width — a 10ms-wide bucket means p95 could be off by up to 10ms.
Quantile buckets — use cases and pitfalls
Bucket algorithms fit when you need percentiles over huge streams with bounded memory and can tolerate approximation.
Performance monitoring
APM tools, infra metrics, DB query latency — Prometheus histograms are bucket algorithms. Aggregate histograms across pods without centralizing every sample.
SLOs
"99% of requests complete within 100ms" — compute p99 from histogram buckets, compare to threshold. Cheap continuous compliance checks.
Auto-scaling
Scale on p95 CPU or p99 latency rather than averages — buckets make percentile-driven policies feasible at fleet scale.
In your interview
Decision cheat sheet
| Question | Structure | When not to use it |
|---|---|---|
| Is X in the set? | Bloom filter | Need exact membership or deletes |
| How many times did X occur? | Count-Min Sketch | Exact counts or unknown IDs |
| How many unique X? | HyperLogLog | Small sets or exact cardinality |
| What's p95 of X? | Histogram buckets | Need exact order statistics |
What to say out loud
"Before I reach for a probabilistic structure, I'd check whether a hash table or Redis counter fits in memory — these save space but don't delete and only approximate. For a crawler dedup set at billions of URLs, I'd use a bloom filter and accept occasional false positives. For DAU I'd use HyperLogLog in Redis — merge sketches per shard. For p99 SLOs I'd emit Prometheus histograms with exponential buckets, not store every latency sample."
- State the three preconditions (query type, space pressure, tolerance for error).
- Name the false positive / upper-bound / estimation caveat for your pick.
- Keep the rest of the design boring — load balancers, caches, queues still matter more.
- Red flag: bloom filter when a hash table easily fits — interviewers notice over-engineering.
Structure picker
Error budgets
Bloom false positive 1% may be fine for cache; billing unique counts with HLL need disclosed error (±2%). Always state the error bar.
Failure modes to mention
Call out at least one dependency failure (DB down, cache stampede, queue lag, region outage) and your mitigation (timeouts, retries with jitter, degraded mode, circuit breaker).
Cost and performance levers
Interview Q&A by level
Practice saying these out loud for specialized data structures. Interviewers grade clarity and judgment more than buzzwords.
Match depth to the bar: define → trade off → operate. Don't dump principal answers in an entry-level screen.
Wrapping up
If you need membership, frequency, cardinality, or quantiles at a scale where exact structures won't fit — and you can tolerate error — these data structures dramatically increase what your design can handle. Knowing when to use them (and when not) shows depth without turning every interview into a algorithms exam.
Continue with Caching strategies, Redis, Database indexing, Time-series databases (Bloom filters on SSTables), Spark, and Common patterns.