1. Bloom filters

Picture a product-page service with 200 million real product IDs (identifiers) like p-1001, a cache in front of the product database, and a crawler bot requesting IDs that were never created. Every one of those requests misses the cache, because there is nothing to cache, and falls through to the database.

You want to turn those requests away early, but a complete list of valid IDs costs gigabytes per server. A Bloom filter is the small structure that fixes this. It answers "might this ID exist?" in a few hundred megabytes, and its answers are one-sided: a "no" is always right, while a "yes" only means "maybe" and still has to be checked. That makes it the right tool when most lookups are for keys that don't exist and a trusted "no" saves an expensive read.

In interviews this is a follow-up, not a headline. It usually shows up for two to five minutes, when an interviewer asks how you keep missing keys away from the database, or when a storage or crawler design has lots of lookups for things that are not there. At mid-level, explain what the filter answers and where it sits. Senior candidates are expected to size it, handle growth, and say when it is the wrong tool.

By the end you'll be able to walk an insert and a lookup on a bit array by hand, explain why the filter can be wrong in only one direction, place the filter in a design or turn it down, and estimate memory for a target error rate.