Skip to the code
cf.
+25 XP

#699 Counting Filter With Removal

medium

A plain Bloom filter can't forget a word, because clearing its bits could erase other words. A counting filter keeps a small counter in each slot instead of a bit. Write a class CountingFilter:

  • new CountingFilter(size, seeds) creates size counters, all 0.
  • add(word) adds 1 to the counter at hash(word, seed) for every seed.
  • remove(word) subtracts 1 from those same counters. It is only called for a word that was added and not yet removed.
  • mightContain(word) returns true if every one of the word's counters is above 0.

hash(text, seed) starts with h = 0 and for each character c sets h = (h * seed + c.charCodeAt(0)) % size. If two seeds give the same position, that counter changes twice.

Each example lists the calls in order, then each call's arguments. The first call creates the object with new CountingFilter(…); the output lists what each call returns (null for the constructor and for methods that return nothing).

Example 1

Input: ["CountingFilter","add","add","mightContain","remove","mightContain","mightContain"]
[[10,[31,37]],["cat"],["elk"],["cat"],["cat"],["cat"],["elk"]]
Output: [null,null,null,true,null,true,true]

cat and elk use the same two slots (2 and 6), so each counter is 2. Removing cat leaves 1s, so both checks still say true.

Example 2

Input: ["CountingFilter","add","remove","mightContain"]
[[10,[31,37]],["dog"],["dog"],["dog"]]
Output: [null,null,null,false]

After removing the only word, every counter is back to 0.

Constraints

  • 1 <= size <= 10^4
  • 1 <= seeds.length <= 5
  • Words are 1 to 10 lowercase letters.
  • At most 1000 calls.
Saved in this browser

Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.

Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).