HardPro challengePythonJavaScriptTypeScript

Bloom Filter

Node.jsAlgorithmsHashing

Implement a basic Bloom filter using two FNV-1a-derived hashes (h1, h1+h2*i).

solve(size, k, adds, queries):

  • size: bit array length.
  • k: number of hash functions.
  • adds: strings to insert.
  • queries: strings to check.

Returns array of booleans (true = "maybe present"). False = definitely absent.

Use these helpers:

function fnv1a(s, seed) { let h = seed >>> 0; for (const c of s) { h ^= c.charCodeAt(0); h = Math.imul(h, 0x01000193); } return h >>> 0; }

With seeds 0x811c9dc5 (h1) and 0xcbf29ce4 (h2). Index = (h1 + i * h2) % size.

Sample tests

Test #1Inserted item found
Input: [100,3,["apple"],["apple"]]
Output: [true]
Test #2Not inserted likely absent
Input: [100,3,["apple"],["banana"]]
Output: [false]
Test #3Empty filter
Input: [100,3,[],["apple"]]
Output: [false]
Test #4Multiple inserts
Input: [100,3,["x","y","z"],["x","y","z"]]
Output: [true,true,true]
Test #5Mixed queries
Input: [50,2,["hello"],["hello","world"]]
Output: [true,false]