Implement Bloom Filter with without recursion

Question

Implement a Bloom Filter, a space-efficient probabilistic data structure, that supports the operations of adding elements and checking for membership without using recursion. Your implementation should handle a specified number of hash functions and allow for a configurable size of the bit array. The output should indicate whether an element is possibly in the set or definitely not in the set, with false positives allowed but no false negatives.

Codemia · Accepted Answer

A Bloom Filter is a space-efficient data structure that allows for the testing of set membership with a possibility of false positives. The operations we need to implement are `add` and `check` without recursion. The specific patterns applicable here are: 1. **Bit Array**: We'll use a fixed-size bit array to represent the membership of elements. 2. **Multiple Hash Functions**: To reduce the probability of collision and false positives, we'll employ multiple independent hash functions. Each function will map an input element to one or more indices in the bit array. Since we require a probabilistic structure with no false negatives, if an element has been added, its membership test will always return `True`. However, it can return `True` for elements that were not added, hence the allowance for false positives.

1. **Initialize the Bloom Filter**: Create a bit array of size `m` initialized to `0` and define `k` hash functions. 2. **Hash Functions**: Define `k` hash functions. These can be implemented using a combination of modulo operations and different seed values to ensure they map to different indices. 3. **Add Function**: For each element to be added, compute the indices for all `k` hash functions and set the corresponding bits in the bit array to `1`. 4. **Check Function**: For each element to be checked, compute the indices using the same `k` hash functions. If all corresponding bits in the bit array are `1`, return `True`, indicating a possible membership. If any bit is `0`, return `False`, indicating the element is definitely not in the set. 5. **Example**: If we have a bit array of size 10 and two hash functions, adding 'hello' might set bits at indices 2 and 5. Checking for 'hello' would check those bits and return `True`. Checking for 'world' might return `False` if the bits at its computed indices are `0`.

```python
import hashlib

class BloomFilter:
    def __init__(self, size: int, num_hashes: int):
        self.size = size
        self.bit_array = [0] * size
        self.num_hashes = num_hashes

def _hashes(self, item):
        result = []
        for i in range(self.num_hashes):
            hash_result = int(hashlib.md5((str(item) + str(i)).encode()).hexdigest(), 16) % self.size)
            result.append(hash_result)
        return result

def add(self, item):
        for index in self._hashes(item):
            self.bit_array[index] = 1

def check(self, item):
        return all(self.bit_array[index] for index in self._hashes(item))
```

The time complexity for both the `add` and `check` operations is O(k), where `k` is the number of hash functions. This is because we compute `k` indices for both operations. The space complexity is O(m), where `m` is the size of the bit array. Given that `k` is typically a small constant in practical scenarios, the operations remain very efficient. This design meets the requirements of handling a configurable size of the bit array and a specified number of hash functions.

1. **Empty Filter**: If no elements have been added, all checks should return `False`. 2. **All Bits Set**: If we continually add elements, eventually all bits may be set to `1`, leading to increased false positives. 3. **Hash Collision**: If two distinct items hash to the same indices due to poor hash function design or insufficient bit array size, this can increase false positives. 4. **Large Number of Additions**: If we add more elements than the bit array can handle, the likelihood of false positives increases significantly. We must ensure we choose an appropriate size for `m` relative to the expected number of elements to maintain effectiveness.

Implement Bloom Filter with without recursion

Brex

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Brex Machine Learning Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string