Skip to the code
cf.
+25 XP

#698 Count Filter False Alarms

medium

Before shipping a Bloom filter to the browser, a team measures how often it raises false alarms. The filter has size bits and one hash function per seed in seeds, where hash(text, seed) starts with h = 0 and for each character c sets h = (h * seed + c.charCodeAt(0)) % size. Adding a word sets the bit at hash(word, seed) for every seed; a check says "maybe" when all of those bits are set.

Write falseAlarms(size, seeds, added, checks): add every word in added to an empty filter, then return how many entries of checks get "maybe" even though that word is not in added. Count every such entry, including repeats.

Example 1

Input: size = 10, seeds = [31,37], added = ["cat","dog"], checks = ["cat","fox","pig","bee"]
Output: 2

cat was really added. fox is a clear no. pig (bits 0 and 6) and bee (bit 0 twice) are false alarms: 2.

Example 2

Input: size = 10, seeds = [31,37], added = [], checks = ["cat","dog"]
Output: 0

An empty filter says no to everything.

Constraints

  • 1 <= size <= 10^4
  • 1 <= seeds.length <= 5
  • 0 <= added.length, checks.length <= 1000
  • Words are 1 to 10 lowercase letters.
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).