Algorithms and Data Structures · Senior · Question 43 of 75
Which approach answers "is this word in the dictionary?" for millions of words with the least memory, if rare false positives are fine?
- 1A trie of all words
- 2A sorted array with binary search
- ✓Correct answer: A Bloom filter
Explanation
A Bloom filter needs about 10 bits per word for a 1% false positive rate, regardless of word length. A trie or a sorted array stores the words themselves, which takes far more memory.