Whenever you start typing your search on Google, you get a list of recommendations, and the more letters you type, the more accurate the recommendations get. If you’re like me, you’ve always wondered how this works — is the inverted index being stored, or is it something else?
The data structure that would be apt here is a Trie.
