Skip to question
ASIC.FYI

Q255FreeFirmware

Counting Bloom Filter

Difficulty
Hard
Topic
Probabilistic Structures
Language
SV
Interview prompt

Question

Create a bounded-memory approximate membership structure that supports insertion, query, and deletion by using small counters instead of single bits.

Starting point

Question code

class CountingBloom #(int M = 1024, int K = 4, int CW = 4);
  void insert(int key);
  bit might_contain(int key);
  void remove(int key);
  void clear();
endclass
Reviewed example

Trace one case

Input
insert(16'hD0A0); insert(16'hD0A0); remove(16'hD0A0); might_contain(16'hD0A0)
Expected output
1 (might be present)

Counters remain nonzero after one of two insertions is removed; unlike a bit-only Bloom filter, this avoids an immediate false negative for the remaining instance.

What to cover

Requirements

  1. Use K independently seeded hash projections into M counters.
  2. A query may return a false positive but must not return a false negative while the API preconditions hold.
  3. Detect counter overflow and underflow; never silently wrap or claim the guarantee after saturation.
  4. State the precondition required for safe deletion.
Continue practicing
Q168 · Data StructuresEstimate stream frequencies with a Count-Min SketchQ268 · Performance ControlToken-Bucket Rate-Limit MonitorQ237 · AlgorithmsDynamic Connectivity with Disjoint Sets