Tuning a Bloom filter
You store keys in a Bloom filter backed by MB of memory (exactly bits). Each key is inserted by setting the bits at independent uniform hash positions; a query reports 'present' if all of its bits are set. Choosing the integer that minimises the false-positive rate, what is that rate, in percent? (Use the standard approximation that bits are set independently.)
Show hints (3)+
- Write the probability that one particular bit is still 0 after all insertions.
- A false positive needs all probed bits set; minimise over .
- The optimum sits where about half the bits are set.
Answer
Reveal answer →Final answer
0.819 (± 0.01)
Create a free account to see the full worked solution and track your progress.
Interview format: Prop Trading, Systematic & Data-Driven Trading