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

bookChallenge: Implement a Bloom Filter

Tâche

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

Tout était clair ?

Comment pouvons-nous l'améliorer ?

Merci pour vos commentaires !

Section 3. Chapitre 5
single

single

Demandez à l'IA

expand

Demandez à l'IA

ChatGPT

Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion

close

bookChallenge: Implement a Bloom Filter

Glissez pour afficher le menu

Tâche

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 desktopPassez à un bureau pour une pratique réelleContinuez d'où vous êtes en utilisant l'une des options ci-dessous
Tout était clair ?

Comment pouvons-nous l'améliorer ?

Merci pour vos commentaires !

Section 3. Chapitre 5
single

single

some-alt