1. Prompt
A logging system receives billions of user identifiers each day and must estimate the number of unique users for the day in real time. The memory budget is only a few KB, and a small error is acceptable. Design a streaming algorithm and explain its error, how to merge shards, and where it cannot replace exact deduplication.
2. Constraints and clarifications
- The input is an ongoing identifier stream; use one pass and fixed memory.
- The query asks for approximate cardinality (distinct count) over a time window.
- Assume a uniformly distributed hash and that every shard uses the same hash algorithm, register count, and encoding.
- Deletion is not required; sliding windows, expiry, and strongly consistent exact values need additional structures.
3. Core idea
HyperLogLog (HLL) splits a hash into a register index and remaining bits. With m = 2^p registers, the first p bits select a register; in the remaining bits, the number of leading zeroes plus one is rho. Each register stores only the largest rho it has observed.
The intuition is that a very long run of leading zeroes in a register is evidence that more distinct elements have appeared in the sample space. Estimate cardinality with a harmonic mean:
E = alpha_m * m^2 / sum(2^(-M[j]))
Here M[j] is register j and alpha_m is a correction constant based on the register count. Production implementations also use linear-counting correction for small cardinalities and a large-range correction near the hash-space limit.
4. Reference implementation
The pseudocode below shows update, estimation, and merge. A real implementation should use fixed-width integers, an explicit hash function, and a bound for rho.
init(p):
m = 1 << p
M = array(m, fill=0)
add(x):
h = hash64(x)
j = high_bits(h, p)
w = remaining_bits(h, p)
r = leading_zero_count(w) + 1
M[j] = max(M[j], r)
estimate():
z = sum over j of 2^(-M[j])
e = alpha(m) * m * m / z
if e <= small_range_threshold(m) and zero_registers(M) != 0:
e = m * log(m / zero_registers(M))
return large_range_correction_if_needed(e)
merge(other):
require same p, hash function, and register encoding
for j in 0..m-1:
M[j] = max(M[j], other.M[j])5. Complexity and correctness
Each element requires one hash and one register update, so the time complexity is O(1); space complexity is O(m), independent of the stream length. Standard HLL has relative standard error of about 1.04 / sqrt(m): for m = 16,384, that is about 0.81%. This is a probabilistic estimation error, not a promise that every query lies in a fixed interval.
Because updates take a maximum, adding the same element repeatedly does not keep changing the state, giving idempotence. Shards can be merged by taking a register-wise maximum, provided the hash function, p, and encoding are identical; otherwise their statistical distributions are incompatible.
6. Follow-ups and traps
- HLL returns an estimate; it cannot replace an exact set when the product needs an exact per-user list, audit trail, or billing quantity.
- Clearing registers represents a new window only. A sliding window needs time buckets, multiple HLLs, or a deletable variant, plus boundary and storage handling.
- Hash collisions and input bias affect the estimate. Choose a stable 64-bit or wider hash and standardize it across service boundaries.
- The raw harmonic estimator is biased for small cardinalities; linear counting uses the number of zero registers to reduce that bias.
7. Further reading
- Redis PFCOUNT and HyperLogLog data type documentation.
- Snowflake approximate cardinality documentation.
- Meta Engineering's overview of HyperLogLog in Presto.
8. Interview scoring points
Can explain the state
The candidate should explain the m = 2^p registers, the index, the origin of rho, and why each register keeps only a maximum.
Can derive error and corrections
They should give the 1.04 / sqrt(m) order of magnitude, explain small-range linear counting and large-range correction, and distinguish probabilistic error from an exact guarantee.
Can handle distributed merge
They should state that merge is a register-wise maximum and that every shard must share the hash function, precision, and encoding.
Can identify product boundaries
They should distinguish approximate analytics from exact lists, sliding windows, deletion, and billing, and explain why those requirements need extra design.