---
title: 'Why System Design Interviews Ask You to Count Billions of Users Without a HashSet'
source: 'https://youtube.com/watch?v=4p9PY-4YboA'
video_id: '4p9PY-4YboA'
date: 2026-08-04
duration_sec: 77
---

# Why System Design Interviews Ask You to Count Billions of Users Without a HashSet

> Source: [Why System Design Interviews Ask You to Count Billions of Users Without a HashSet](https://youtube.com/watch?v=4p9PY-4YboA)

## Summary

This video explains how to count unique items at massive scale, a common system design interview question. It introduces HyperLogLog, a probabilistic algorithm that estimates cardinality using only about 12 kilobytes of memory, regardless of the number of items. The video contrasts this with the naive approach of using a hash set, which would consume a terabyte of RAM for a hundred billion requests.

### Key Points

- **The naive approach: hash set** [00:01] — Counting unique requests by storing IDs in a hash set works for small data, but fails at scale. For a hundred billion requests, a hash set would consume a terabyte of RAM.
- **HyperLogLog: a memory-efficient alternative** [00:16] — HyperLogLog estimates cardinality using a probabilistic algorithm that requires only about 12 kilobytes of memory, regardless of input size. It works for billions or even tens of billions of IDs.
- **How HyperLogLog works** [00:29] — It counts the number of leading zeros in a hash. 50% of items have one leading zero, 25% have two, and so on. The maximum number of leading zeros observed is used to estimate the total number of unique items.
- **Robustness and error bounds** [00:58] — By applying tricks for robustness, HyperLogLog provides estimates with guaranteed error bounds, making it reliable for approximate counting.
- **When to use HyperLogLog** [01:11] — Use HyperLogLog when you need to count uniques and don't need a precise value. It's faster and uses far less memory than a gigantic hash table.

### Conclusion

HyperLogLog is a powerful tool for counting unique items at scale, offering a massive memory reduction compared to a hash set. It's a key concept for system design interviews and real-world applications where approximate counts are acceptable.

## Transcript

how many unique requests your site had today? You think, easy, I'll throw their IDs in a hash set. Done. Then your interviewer says, it's a hundred billion requests. Your hash set just consumed a terabyte of RAM. You could shard it and
turn this into an expensive, but solvable problem, but there's a much better approach called HyperLogLog. HyperLogLog estimates cardinality like the number of uniques using a probabilistic algorithm that needs about
12 kilobytes of memory regardless of input size. A billion IDs or 10 billion, you don't need more memory. The way it works is by counting the number of leading zeros in a hash. 50% of items will have only one leading zero. 25%
will have two. The more items you're counting, the more likely you are to have a rare streak where a hash has a lot of leading zeros. If we keep track of the maximum number of leading zeros and apply some tricks for robustness, we
can estimate the number of uniques with guaranteed error bounds. So, remember, if you need to count uniques and don't need a precise value, HyperLogLog will do it faster and with way less memory than a gigantic hash table. Follow us
than a gigantic hash table. Follow us for more system design.