Is the flower filter inverse? possible?

Question

From the interview question:

"Determine whether the word is in the saved list. The list does not fit into memory. Allowed access to the disk is not available, only for search, access to memory. No false positives are allowed, false negatives are in order."

Bloom filters do the exact opposite: false positives are allowed, false negatives are acceptable.

My thoughts: we can’t use the hash function, as we may have collisions that violate the requirement “no false positives”. Even if you use a flowering count filter, a collision will still result in a false positive. I.E. two lines lead to the same hashes, therefore, when the first is “inserted” and we look at the second, it will show it there, although it is not there.

I think the answer is a bit array, since we cannot have false positives. Does this sound right?

Answer 1

I think the LRU cache will do. Because when we ask if there is a word in the list, we either want “definitely yes” or “maybe not” or otherwise said that false positives are not allowed, but false negatives are fine; then it’s OK to say “maybe not on the list” even there (maybe not), and if this word is in the LRU cache, then it will always say “definitely yes”