Vibe Engines Learn
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
  1. For each item: h = hash32(item). Bucket = top p bits (h >> (32 - p)). The remaining 32 - p bits are w.
  2. 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.
  3. Raw estimate: alpha * m * m / Z where Z = Σ 2^(−register[j]) and alpha = 0.7213 / (1 + 1.079/m).
  4. 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

Explore the topic

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

Caching & Performance Real-time & Messaging