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 much memory to check a billion usernames?
How much off-heap RAM do a Cassandra node’s filters need?
Build-up · 5 steps
Add two keys, then check two
A 12-bit filter with k = 3 hashes. Two keys go in, then two keys that were never added are checked.
Step 1 of 5
12 bits, all zero
A Bloom filter is m bits plus k hash functions, here 12 and 3. It stores no keys, so a 4-byte ID and a 2 KB URL cost the same k bits.
4 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 4
Interviewer
“A sign-up page shows “✓ available” as you type. There are a billion handles averaging 16 bytes. How do you answer fast?”
Your move. Pick an approach:
Deep dive 2 of 4
Interviewer
“Keys in your set come and go all day, memory is tight, and you want about 1% error. How do you support deletes?”
Your move. Pick an approach:
Deep dive 3 of 4
Interviewer
“One CDN cluster’s logs show about 74% of objects were requested only once. How do you keep them off the disks?”
Your move. Pick an approach:
Deep dive 4 of 4
Interviewer
“Your filter was sized for a million keys at 1%. Sign-ups will double that this year. What do you do?”
Your move. Pick an approach: