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

bookChallenge: Implement a Bloom Filter

Oppgave

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

Løsning

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 3. Kapittel 5
single

single

Spør AI

expand

Spør AI

ChatGPT

Spør om hva du vil, eller prøv ett av de foreslåtte spørsmålene for å starte chatten vår

close

bookChallenge: Implement a Bloom Filter

Sveip for å vise menyen

Oppgave

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

Løsning

Switch to desktopBytt til skrivebordet for virkelighetspraksisFortsett der du er med et av alternativene nedenfor
Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 3. Kapittel 5
single

single

some-alt