Loading LLD design...
Design a thread-safe Bloom filter — a space-efficient probabilistic data structure for set membership testing that guarantees no false negatives but allows a controllable false positive rate (FPR).
Implement three variants: (1) Standard Bloom Filter with optimal parameter calculation (m = −(n·ln p)/(ln 2)², k = (m/n)·ln 2), double hashing via Kirschner-Mitzenmacher optimisation (h_i(x) = h1(x) + i·h2(x) mod m), thread safety via ReadWrite lock (shared reads, exclusive writes), and support for merge (bitwise OR union), fill ratio, and runtime FPR estimation; (2) Counting Bloom Filter using counter arrays instead of bits, enabling deletion (decrement) with overflow protection (4-bit cap at 15), at 4× the memory cost; (3) Scalable Bloom Filter with dynamic layer growth — each new layer has tighter FPR (p_i = p₀·r^i) so the combined FPR across all layers stays within the target.
add() — insert element
Hash item with k hash functions; set the corresponding k bit positions to 1
mightContain() — membership test
Returns DEFINITELY NOT (if any bit is 0) or POSSIBLY YES (if all k bits are 1); false positives possible, false negatives impossible
Optimal parameter calculation
Compute optimal bit array size m = −(n·ln p)/(ln 2)² and hash count k = (m/n)·ln 2 from expected items n and target FPR p
Double hashing (Kirschner-Mitzenmacher)
Generate k hash values from two base hashes: h_i(x) = (h1(x) + i·h2(x)) mod m — avoids computing k independent hash functions
Thread safety via RW lock
mightContain() acquires shared/read lock (concurrent reads); add() acquires exclusive/write lock
Counting Bloom Filter — deletion support
Replace each bit with a counter (4-bit/int); add increments, remove decrements; enables deletion at 4× memory cost
Scalable Bloom Filter — dynamic growth
Stack of Bloom filter layers; when current layer is full, add a new layer with tighter FPR (p_i = p₀·r^i) to maintain overall target
Merge (union) of filters
Bitwise OR of two Bloom filters with same m and k produces a filter representing the union of both sets
Estimated FPR and fill ratio
Runtime FPR estimation: (1 − e^(−kn/m))^k; fill ratio = bits set / total bits — monitor saturation
Before diving into code, clarify the use cases and edge cases. Understanding the problem deeply leads to better class design.
Identify the primary actions users will perform. For a parking lot: park vehicle, exit vehicle, check availability. Each becomes a method.
Who interacts with the system? Customers, admins, automated systems? Each actor type may need different interfaces.
What are the limits? Max vehicles, supported vehicle types, payment methods. Constraints drive your data structures.
What happens on overflow? Concurrent access? Payment failures? Thinking about edge cases reveals hidden complexity.