Optimal Bloom Bits per Item

Problem

Return the total number of bits needed for a Bloom filter to reach a target false positive rate over num_items items.

The optimal size is ceil(-n * ln(p) / (ln 2) ** 2) bits in total. Return 0 for rates outside the open interval (0, 1) or a negative item count.

Hint

About 9.6 bits per item buy a one percent false positive rate.

case 1

in: [0.01,1000]

expected: 9586

case 2

in: [0.1,100]

expected: 480

case 3

in: [0.5,1]

expected: 2

case 4

in: [1,10]

expected: 0

case 5

in: [0.01,0]

expected: 0

Starter codePython

import math


def optimal_bloom_bits_per_item(false_positive_rate, num_items):
    # Your code here
    pass

5 test cases · run your code against them in the editor