Bloom Filters

Question 1

Which of the following is true about a standard Bloom Filter?

Accepted Answer

False positives are possible — Bloom Filters can return false positives (saying an item exists when it doesn't due to hash collisions), but they will never return a false negative.

Question 2

A Bloom filter is a space-efficient probabilistic data structure for testing…

Accepted Answer

Set membership — It answers membership queries using little memory, accepting a small false-positive rate in exchange for space efficiency.

Question 3

A Bloom filter can return false ___ but never false ___.

Accepted Answer

Positives; negatives — If it says 'not present', the element is definitely absent (no false negatives); if it says 'present', the element MIGHT be absent (false positive possible).

Question 4

A Bloom filter stores elements using…

Accepted Answer

A bit array via hashing — It never stores the items themselves — just bits flipped by k hash functions, which is why it's so compact.

Question 5

To ADD an element, a Bloom filter…

Accepted Answer

Hashes it, sets k bits to 1 — Each of the k hash functions maps the element to a position; all k bits are set to 1.

Question 6

To QUERY membership, the filter checks whether…

Accepted Answer

All k hashed bits are set — If any of the k bits is 0, the element is definitely absent. If all are 1, it's probably present (could be a false positive from other insertions).

Question 7

Why are false positives possible?

Accepted Answer

Other elements can set those same bit positions first — Bits set by other elements can collectively make a non-member's k bits all 1, producing a false positive.

Question 8

Why are false negatives IMPOSSIBLE in a standard Bloom filter?

Accepted Answer

Set bits are never cleared, so prior inserts persist — Adding only sets bits and never clears them, so a previously inserted element's bits remain 1 — it can never be reported absent.

Question 9

A standard Bloom filter does NOT support…

Accepted Answer

Deletion of elements — Clearing bits could create false negatives (a bit may be shared), so deletion isn't supported — a Counting Bloom Filter is needed for that.

Question 10

A Counting Bloom Filter enables deletion by…

Accepted Answer

Using an integer counter per slot rather than a single bit — Counters track how many elements set each position, so deletion decrements them safely — at the cost of more memory than plain bits.

Can a Bloom filter do this?

Test your knowledge

Which of the following is true about a standard Bloom Filter?

Interview Questions

References & Further Reading

Related topics

Love this visualization?