Skip to the code
cf.
+10 XP

#697 Seen Usernames Filter

easy

A sign-up form wants to warn "this username may be taken" without downloading every username. The server sends a Bloom filter instead. Write a class UsernameFilter that builds the same filter:

  • new UsernameFilter(size, seeds) creates size bits, all 0, and one hash function per number in seeds.
  • add(name) sets the bit at hash(name, seed) to 1 for every seed.
  • mightContain(name) returns true if all of those bits are 1, and false if any is 0.

The hash function is exact: hash(text, seed) starts with h = 0, and for each character c of text in order sets h = (h * seed + c.charCodeAt(0)) % size. The result is a bit index from 0 to size - 1.

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

Example 1

Input: ["UsernameFilter","add","add","mightContain","mightContain","mightContain"]
[[10,[31,37]],["cat"],["dog"],["cat"],["fox"],["pig"]]
Output: [null,null,null,true,false,true]

cat sets bits 2 and 6 and dog sets bits 4 and 0. fox needs bits 3 and 5, which are 0. pig needs bits 0 and 6, which are both 1: a false positive.

Example 2

Input: ["UsernameFilter","mightContain"]
[[16,[7]],["anyone"]]
Output: [null,false]

Nothing was added, so every bit is 0.

Constraints

  • 1 <= size <= 10^4
  • 1 <= seeds.length <= 5
  • 2 <= seeds[i] <= 1000
  • Names are 1 to 20 lowercase letters or digits.
  • 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).