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

bookChallenge: Implement a Bloom Filter

Taak

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

Oplossing

Was alles duidelijk?

Hoe kunnen we het verbeteren?

Bedankt voor je feedback!

Sectie 3. Hoofdstuk 5
single

single

Vraag AI

expand

Vraag AI

ChatGPT

Vraag wat u wilt of probeer een van de voorgestelde vragen om onze chat te starten.

close

bookChallenge: Implement a Bloom Filter

Veeg om het menu te tonen

Taak

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

Oplossing

Switch to desktopSchakel over naar desktop voor praktijkervaringGa verder vanaf waar je bent met een van de onderstaande opties
Was alles duidelijk?

Hoe kunnen we het verbeteren?

Bedankt voor je feedback!

Sectie 3. Hoofdstuk 5
single

single

some-alt