Implement Bloom Filter with streaming input

Question

Implement a Bloom Filter that can efficiently handle streaming input, allowing for the insertion of elements and checking for membership with a specified false positive rate. Your implementation should support the addition of elements and querying for their existence in O(1) time complexity, with appropriate handling of hash functions and bit arrays.

Codemia · Accepted Answer

A Bloom Filter is a space-efficient probabilistic data structure that can determine whether an element is a member of a set. It allows for false positives but not false negatives. In this problem, we need to implement a Bloom Filter that can handle streaming input, which requires us to efficiently insert elements and check for their existence in O(1) time complexity.

The problem suggests using multiple hash functions to map input elements to a bit array. This approach fits the Bloom Filter model, where we can use a fixed-size bit array and multiple hash functions to manage the trade-off between space efficiency and the probability of false positives.

1. **Initialize a Bit Array**: Create a bit array of a defined size (e.g., 1000 bits) initialized to 0.
2. **Define Hash Functions**: Use multiple hash functions (e.g., 3 functions) that map input elements to indices in the bit array. These can be created using different hashing techniques (e.g., SHA-256, MD5, etc.).
3. **Insertion Method**: When inserting an element:
   - Compute the hash values for the element using all hash functions.
   - Set the corresponding indices in the bit array to 1.
4. **Membership Check Method**: When checking if an element exists:
   - Compute the hash values for the element.
   - If any of the corresponding bits are 0, return false (the element is definitely not in the set).
   - If all are 1, return true (the element might be in the set, allowing for false positives).

**Example**: If inserting 'apple', say hash functions give us indices 100, 200, and 300. We set bits at these positions to 1. For checking 'apple', we check those same bits; if they are all 1, we conclude it might exist.

```python
import hashlib

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

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

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

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

The time complexity for both the `insert` and `contains` methods is O(k), where k is the number of hash functions used. Given that k is a constant (e.g., 3), we can consider this O(1) for practical purposes. The space complexity is O(m), where m is the size of the bit array (e.g., 1000 bits), which also remains constant and manageable.

1. **Empty Input**: If we initialize the Bloom Filter but do not insert any elements, the `contains` method should return false for any query.
2. **Single Element**: If we insert a single element and check for it immediately after, it should return true. However, checking for a different element should return false. This tests both insertion and query functionality.
3. **High Collision**: If the number of elements inserted approaches the bit array size, the false positive rate will increase. It's important to discuss how to choose the size of the bit array and the number of hash functions to balance performance and false positive rates.

Implement Bloom Filter with streaming input

Snapchat

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

Snapchat 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