CODING CHALLENGE · N°48

HyperLogLog Cardinality Estimator

Hard ProbabilisticStreamingHashing

Count how many <i>distinct</i> items a stream contained — billions of them — using a few kilobytes, not a giant set. HyperLogLog turns "the longest run of leading zeros I saw" into a cardinality estimate. It powers COUNT(DISTINCT) in Redis, Presto and BigQuery. A provided hash keeps Python and TypeScript in sync. Hidden tests.

The problem

Implement hll_estimate(items, p): estimate the number of distinct values in items using HyperLogLog with 2^p registers. For each item, hash it (use the provided hash32); the top p bits pick a register, and the register keeps the maximum "rank" seen — the position of the leftmost 1-bit in the remaining bits (leading-zeros + 1). Combine the registers with the HLL formula and return the estimated cardinality as an integer.

EXAMPLE 1

Input hll_estimate(['a','b','c',...] (1000 distinct), p = 8)

Output ≈ 1000

a few hundred bytes of registers estimate the count within a couple percent

CONSTRAINTS

Use the provided hash32. There are m = 2^p registers, all starting at 0.
Rank = leading-zeros-plus-one of the non-bucket bits: if the leftmost bits are 0, the rank is higher (rare, so a high rank hints at many distinct items).
Estimate E = alpha · m² / Σ 2^(−register). Apply the small-range correction: if E ≤ 2.5m and some registers are still 0 (count V), use E = m · ln(m / V). Return int(E).
It is an estimate — expected error is a few percent, not exact. That is the trade for tiny memory.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement hll_estimate(items, p): build m = 2^p registers of max ranks, then apply the HLL estimator with the small-range correction. The provided hash32 gives the bits; the top p select the register, the rest give the rank.

HINTS — 4 IDEAS

For each item: h = hash32(item). Bucket = top p bits (h >> (32 - p)). The remaining 32 - p bits are w.
Rank = 1 + number of leading zeros of w within its 32 - p bits (if w is all zeros, the rank is (32 - p) + 1). Keep the max rank per register.
Raw estimate: alpha * m * m / Z where Z = Σ 2^(−register[j]) and alpha = 0.7213 / (1 + 1.079/m).
Small-range correction: if the estimate ≤ 2.5·m and V registers are still zero, return m * ln(m / V) instead. Truncate to an int.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

Hash each element and look at the number of leading zeros in the hash — seeing k leading zeros suggests you have observed on the order of 2ᵏ distinct values. Split into many buckets (by a hash prefix), track the max leading-zero count per bucket, and combine the buckets with a harmonic mean to sharply cut the variance. The result estimates the distinct count in tiny, fixed memory.

Complexity

Time O(1) per add; O(buckets) to estimate; memory is fixed (kilobytes) regardless of how many items you count.

Common mistakes

Exact counting with a set — that defeats the purpose; HLL trades a small error for O(1) memory.
Too few buckets, so the estimate has high variance.
Skipping the small-range bias correction, which HLL needs at low cardinalities.

Where this shows up

HyperLogLog counts unique users, IPs, or search queries at massive scale in kilobytes — it is the engine behind Redis PFCOUNT and BigQuery’s APPROX_COUNT_DISTINCT. Trading roughly 2% error for counting billions of distinct items in a fixed buffer is one of the great space-for-accuracy deals in systems.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Caching & Performance Real-time & Messaging