Skip to content
expert

Challenge: a bloom filter that says maybe

Implement this from the stub. Hidden tests grade the behaviour you write, not the comments you leave.

Challenge: A Bloom Filter That Says Maybe

/** Deterministic seeded 32-bit hash — given, not the exercise. */
export function hashAt(seed: number, text: string): number {
  let hash = 0x811c9dc5 ^ Math.imul(seed + 1, 0x9e3779b1)
  for (let i = 0; i < text.length; i++) {
    hash ^= text.charCodeAt(i)
    hash = Math.imul(hash, 0x01000193)
  }
  return hash >>> 0
}

export interface BloomFilterOptions {
  /** Number of bits in the filter. */
  size: number
  /** Hash functions per value. */
  hashCount: number
}

export class BloomFilter {
  constructor(options: BloomFilterOptions) {
    // Your implementation here
  }

  insert(value: string): void {
    // Your implementation here
  }

  mightContain(value: string): boolean {
    // Your implementation here
  }
}
challenge — implement from scratchCtrl+↵ submits · Ctrl+Shift+↵ runsstarter code