Design a Bloom Filter

Implementation: bit array + multiple hash functions

class BloomFilter {
    BitSet bits;
    int size; // m: bit array size
    int hashCount; // k: number of hash functions

    BloomFilter(int size, int hashCount) { this.bits = new BitSet(size); this.size = size; this.hashCount = hashCount; }

    void add(String item) {
        for (int i = 0; i < hashCount; i++) {
            bits.set(hash(item, i) % size); // set k bits, one per hash function
        }
    }

    boolean mightContain(String item) {
        for (int i = 0; i < hashCount; i++) {
            if (!bits.get(hash(item, i) % size)) return false; // ANY unset bit means DEFINITELY not present
        }
        return true; // all k bits set -> POSSIBLY present (or a false positive)
    }

    private int hash(String item, int seed) { /* a family of k independent-enough hash functions */ }
}

Adding an item sets k bits (one per hash function); checking membership verifies ALL k corresponding bits are set. This is the entire mechanism — no actual items are ever stored, only bit positions, which is what makes a Bloom filter dramatically more space-efficient than storing the actual items in a HashSet.

Why false negatives are structurally impossible

If an item was actually added, EVERY one of its k bits was explicitly set at that time — those bits can only ever be set (never cleared, in a basic Bloom filter), so a later check for that same item will always find all k bits still set, and mightContain will correctly return true. A false positive happens when a DIFFERENT combination of other items' bit-settings happens to have set ALL of a given item's k positions anyway, even though that specific item was never added — this is the only kind of error a Bloom filter can produce; "definitely not present" (any single bit unset) is always a mathematically guaranteed CORRECT answer.

Tuning the false-positive rate

Optimal hash function count:  k = (m/n) * ln(2)
  where m = bit array size, n = expected number of elements to be added

More bits (larger m relative to expected element count n) lowers the false-positive rate but costs more memory; more hash functions (k) up to the optimal point ALSO lowers the false-positive rate (spreading each item across more positions makes accidental full-overlap less likely), but too many hash functions past the optimum actually starts INCREASING the false-positive rate again (the bit array fills up faster, making collisions more likely) — this formula gives the sweet spot for a given size/expected-count combination, and an interviewer asking you to REASON about this trade-off (more bits = fewer false positives, at a real memory cost) matters more than memorizing the exact formula.

Real production uses

• Web crawler deduplication (Web Crawler): before crawling a URL, check a Bloom filter of already-seen URLs — a false positive means occasionally SKIPPING a URL that was actually new (a minor, acceptable cost), while the massive space savings versus storing every full URL in a HashSet is the entire point.
• Cache miss avoidance: checking a Bloom filter BEFORE an expensive cache/database lookup for a key that might not exist — if the filter says "definitely not present," skip the expensive lookup entirely; only a possible-positive triggers the real, more expensive check.
• Cassandra/HBase SSTables: each on-disk SSTable file keeps a Bloom filter of the keys it contains — before reading a file from DISK to check for a key, the database first checks the (in-memory) Bloom filter, avoiding an unnecessary, slow disk read for keys that provably aren't in that particular file.

Follow-up questions this topic invites — and their answers

Q: Can a standard Bloom filter support removing an item? A: No — clearing a bit to 'remove' an item could incorrectly cause a DIFFERENT item (that happens to share that bit position) to suddenly report as absent, violating the no-false-negatives guarantee; a Counting Bloom Filter variant (using small counters instead of single bits, incremented/decremented rather than just set) supports removal at the cost of more memory per position.

Q: Why not just use a HashSet if you have enough memory for it? A: At sufficient scale, a HashSet storing actual keys/URLs can require orders of magnitude more memory than a Bloom filter's compact bit array — a Bloom filter trades a small, tunable false-positive RATE for a dramatic memory reduction, which is exactly the right trade for use cases (crawler dedup, cache-miss avoidance) where an occasional false positive costs almost nothing.

Q: How would you decide the expected element count (n) for sizing the filter, if you don't know it in advance? A: Either over-provision based on a reasonable upper-bound estimate (accepting some wasted space if actual count comes in lower), or use a SCALABLE Bloom filter variant that adds additional filter layers as the actual element count grows past initial sizing — a genuine practical concern when the true element count is hard to predict upfront.

Q: Is a Bloom filter's k-independent-hash-functions requirement hard to satisfy in practice? A: In practice, a single good hash function combined with a technique like double hashing (deriving k effectively-independent hash values from just two base hash computations) is commonly used instead of implementing k truly separate hash functions from scratch — a practical engineering shortcut that achieves close to the same statistical behavior with much less implementation complexity.