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

bookChallenge: Implement a Bloom Filter

Tarefa

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).

Solução

Tudo estava claro?

Como podemos melhorá-lo?

Obrigado pelo seu feedback!

Seção 3. Capítulo 5
single

single

Pergunte à IA

expand

Pergunte à IA

ChatGPT

Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo

close

bookChallenge: Implement a Bloom Filter

Deslize para mostrar o menu

Tarefa

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).

Solução

Switch to desktopMude para o desktop para praticar no mundo realContinue de onde você está usando uma das opções abaixo
Tudo estava claro?

Como podemos melhorá-lo?

Obrigado pelo seu feedback!

Seção 3. Capítulo 5
single

single

some-alt