A Bloom filter answers 'have I seen this?' with no false negatives and some false positives, using m bits and k hash functions. Use hash_i(x) = (x * (i + 1) + i * 7) % m for i in 0..k-1. Insert every value in adds (set the k bits), then answer each query: true only if all k bits are set. Return the answers. Cassandra, Chrome and CDNs use this to skip disk reads or lookups for keys that cannot be present.
Patterns: hashing, bit-manipulation, design. Difficulty: medium.