Bloom Filters

Question 1

What is a Bloom filter?

Answer 1

A space-efficient probabilistic data structure used to test whether an element is in a set.

Question 2

Can Bloom filters return false positives?

Answer 2

Yes, they may return false positives.

Question 3

Can Bloom filters return false negatives?

Answer 3

No, they never return false negatives.

Question 4

What is a false positive in a Bloom filter?

Answer 4

When the filter says an element is in the set but it is not.

Question 5

What are the main components of a Bloom filter?

Answer 5

A bit array and multiple independent hash functions.

Question 6

What is the time complexity of adding an element to a Bloom filter?

Answer 6

O(k), where k is the number of hash functions.

Question 7

What is the time complexity of checking membership in a Bloom filter?

Answer 7

O(k)

Question 8

What happens when you insert an element into a Bloom filter?

Answer 8

Each hash function sets a bit in the bit array.

Question 9

What happens when you query a Bloom filter?

Answer 9

Each hash function checks a bit; if all are 1, the element may be in the set.

Question 10

How do you reduce false positive rates in a Bloom filter?

Answer 10

Increase the size of the bit array or use more hash functions.

Question 11

What is the space complexity of a Bloom filter?

Answer 11

O(m), where m is the size of the bit array.

Question 12

What are common use cases for Bloom filters?

Answer 12

Databases, web caching, spell checkers, and network systems.

Question 13

What is the tradeoff in Bloom filters?

Answer 13

Smaller size increases false positives; larger size uses more memory.

Question 14

What is the optimal number of hash functions?

Answer 14

k = (m/n) * ln(2), where m is bit array size and n is number of elements.

Question 15

What is the false positive probability of a Bloom filter?

Answer 15

Approximately (1 - e^(-kn/m))^k.

Question 16

What happens if you insert the same element multiple times?

Answer 16

No change; bits are already set.

Question 17

Are Bloom filters good for small datasets?

Answer 17

Not typically; the overhead may outweigh the benefits.

Question 18

Are Bloom filters deterministic?

Answer 18

No, they are probabilistic.

Question 19

Can Bloom filters support deletion?

Answer 19

Standard Bloom filters cannot support deletion.

Question 20

What is a counting Bloom filter?

Answer 20

A variant that allows deletion by using counters instead of bits.

Question 21

What kind of hash functions are used in Bloom filters?

Answer 21

Fast, independent hash functions that produce uniform output.

Question 22

Can Bloom filters be used in distributed systems?

Answer 22

Yes, especially for quick duplicate detection.

Question 23

What is the initialization cost of a Bloom filter?

Answer 23

O(m), to set all bits to 0.

Question 24

Can you resize a Bloom filter?

Answer 24

Not easily; resizing affects hash function outputs.

Question 25

What is the difference between a Bloom filter and a hash set?

Answer 25

A Bloom filter is space-efficient but allows false positives; a hash set does not.

Question 26

Is a Bloom filter faster than a hash set?

Answer 26

Yes, for large datasets and membership checks.

Question 27

What is the role of a Bloom filter in databases?

Answer 27

To quickly check if a key might exist before performing a full lookup.

Question 28

How is a Bloom filter used in spell checking?

Answer 28

To rule out non-existent words quickly.

Question 29

How is a Bloom filter used in web caching?

Answer 29

To avoid redundant fetches for known non-cached items.

Question 30

What is the bit array in a Bloom filter?

Answer 30

A binary array used to track possible presence of elements.

Question 31

Can Bloom filters be combined?

Answer 31

Yes, via bitwise OR if they use the same parameters.

Question 32

Can Bloom filters be used for exact membership?

Answer 32

No, they are approximate structures.

Question 33

What is the advantage of Bloom filters over hash sets?

Answer 33

Much lower memory usage.

Question 34

What is the disadvantage of Bloom filters?

Answer 34

They have a non-zero probability of false positives.

Question 35

How is the size of the bit array chosen?

Answer 35

Based on the desired false positive rate and expected number of elements.

Question 36

How is the number of hash functions chosen?

Answer 36

To minimize the false positive rate given the bit array size.

Question 37

How do you implement multiple hash functions efficiently?

Answer 37

Use a base hash and derive others from it.

Question 38

What is a real-world system that uses Bloom filters?

Answer 38

Apache HBase, Apache Cassandra, and Google Bigtable.

Question 39

What is the purpose of the ln(2) in the hash function formula?

Answer 39

It optimizes the false positive rate.

Question 40

Can Bloom filters be serialized?

Answer 40

Yes, they can be stored and transmitted.

Question 41

Are Bloom filters secure?

Answer 41

No, they are not cryptographically secure.

Question 42

Can Bloom filters be used for counting frequencies?

Answer 42

No, standard Bloom filters cannot count.

Question 43

What is a scalable Bloom filter?

Answer 43

A dynamic Bloom filter that grows as more elements are added.

Question 44

What is a compressed Bloom filter?

Answer 44

A smaller version optimized for transmission/storage.

Question 45

What is the effect of too many hash functions?

Answer 45

Increased time complexity and more false positives.

Question 46

What is the effect of too few hash functions?

Answer 46

Higher false positive probability.

Question 47

Can Bloom filters store values?

Answer 47

No, they only track membership of keys.