Topic 11.1
Beginner Questions
In one line
The definitions every interviewer expects instantly: what a Bloom filter is, why false positives happen and false negatives don't, why standard filters can't delete, and where they're used.
Think of it like this
A driving test theory round. You must answer the basics without hesitation before the examiner lets you on the road.
Key ideas
- 01
Answer in two layers: one sentence of definition, then one sentence of mechanism (bits and hashes). Interviewers look for both.
- 02
Always say the direction of error: "no" is definite, "maybe" must be verified.
- 03
Close with the use case: what expensive work the filter avoids.
Code & diagrams
A Bloom filter is a bit array plus k hash functions that answers set membership
with "definitely not present" or "possibly present". Insert sets k bits; lookup
checks k bits. Any zero bit means absent for sure. All ones may be a coincidence
(false positive), so the caller verifies against the source of truth.
It saves memory (about 9.6 bits per item at 1%) and avoids expensive lookups
for items that don't exist.Explain it without notes
What is a Bloom filter?
What is a false positive?
What is a false negative?
Can a standard Bloom filter have false negatives?
Why does a Bloom filter use multiple hash functions?
Can you delete from a standard Bloom filter?
What does a Bloom filter store?
Why is it memory efficient?
Where are Bloom filters used?
What is the lookup time complexity?
What happens as more items are added?
Why use a Bloom filter before a database lookup?
Practice
Give the one-minute answer to "What is a Bloom filter?" out loud, including the error direction and a use case.
Trade-offs
- ↔
Memory and speed are bought with a controlled false positive rate and no deletes.
Done when you can
I can answer all twelve beginner questions without notes.