1,000+ ASIC Interview Questions: SystemVerilog, UVM & RTL

DescriptionQ255

Page ↗

Q255ArchFWASIC interview problem

Counting Bloom Filter

TechniquesFWArchDVBloom filterHashingApproximation

DifficultyHard

TopicProbabilistic Structures

LanguageSystemVerilog

Requirements4 checkpoints

Problem

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

Class declarationSystemVerilog

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

Example input and output

Use this case to check your interpretation

Input

insert(16'hD0A0); insert(16'hD0A0); remove(16'hD0A0); might_contain(16'hD0A0)

Output

1 (might be present)

Explanation

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.

Requirements (4)

Use K independently seeded hash projections into M counters.
A query may return a false positive but must not return a false negative while the API preconditions hold.
Detect counter overflow and underflow; never silently wrap or claim the guarantee after saturation.
State the precondition required for safe deletion.