Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Learn Challenge: Implement a Bloom Filter | Probabilistic & Streaming Data Structures
Data Structures and Algorithms for Scalable Systems

bookChallenge: Implement a Bloom Filter

Task

Swipe to start coding

Implement a BloomFilter class that performs probabilistic membership testing using a bit array and multiple hash functions.

Your implementation must follow these rules:

  • The filter uses a bit array of length size, initialized with zeros.
  • The filter uses exactly hash_count hash functions for each inserted item.
  • The private method _hashes(item) must produce a list of hash_count integer indices, each in the range [0, size).
  • The add(item) method must set all corresponding bits for the item’s hash indices.
  • The contains(item) method returns:
    • True if all bits for the item’s hash indices are set
    • False otherwise
  • The filter may have false positives, but must never produce false negatives (i.e., must never return False for an item that was previously added).

Solution

Everything was clear?

How can we improve it?

Thanks for your feedback!

SectionΒ 3. ChapterΒ 5
single

single

Ask AI

expand

Ask AI

ChatGPT

Ask anything or try one of the suggested questions to begin our chat

close

bookChallenge: Implement a Bloom Filter

Swipe to show menu

Task

Swipe to start coding

Implement a BloomFilter class that performs probabilistic membership testing using a bit array and multiple hash functions.

Your implementation must follow these rules:

  • The filter uses a bit array of length size, initialized with zeros.
  • The filter uses exactly hash_count hash functions for each inserted item.
  • The private method _hashes(item) must produce a list of hash_count integer indices, each in the range [0, size).
  • The add(item) method must set all corresponding bits for the item’s hash indices.
  • The contains(item) method returns:
    • True if all bits for the item’s hash indices are set
    • False otherwise
  • The filter may have false positives, but must never produce false negatives (i.e., must never return False for an item that was previously added).

Solution

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

SectionΒ 3. ChapterΒ 5
single

single

some-alt