Layer 3 · Go deeper · 8 min
Go deeper
Size it, build it, then make the calls an interviewer will push you on.
Back of the envelope
Size it up
Tap through each step of the arithmetic.
How big is a count-min sketch for a billion searches a day?
Can HyperLogLog count users active on both Monday and Tuesday?
Build-up · 6 steps
Count hashtags with a count-min sketch
Three rows of eight counters and a short stream of hashtags. Watch why the smallest counter is the answer, and why it is never too low.
Step 1 of 6
An empty d × w table
A count-min sketch is d rows of w counters, all zero, with one hash function per row. Its memory is fixed by d and w, which you pick from the error you can accept.
3 interview moments
You’re the candidate
The interviewer pushes on the hard parts. Pick an approach and see how it holds up.
Deep dive 1 of 3
Interviewer
“Hashtag events land on any of three workers. How do you publish the global top 10 every minute?”
Each worker keeps a count-min sketch and a heap of candidates per minute.
Your move. Pick an approach:
Deep dive 2 of 3
Interviewer
“Product wants unique users per page per hour now, and per day, week and country later. What do you store?”
Your move. Pick an approach:
Deep dive 3 of 3
Interviewer
“The ads team wants unique reach on dashboards and clicks billed to advertisers. Where do sketches belong?”
Your move. Pick an approach:
Build-up · 6 steps
Add one user to a HyperLogLog
Follow user u9812 into a HyperLogLog with p = 14, the size Redis uses, then see how all the registers become one estimate.
Step 1 of 6
Hash the user
Hash every user ID to 64 bits that look random. The same user always hashes to the same bits, so repeats can never change anything.