Topic 12 of 20
Prefix trees for autocomplete, dictionary search and bitwise XOR tricks.
A trie (prefix tree) stores strings character by character, so all words that share a prefix share a path from the root. Inserting or searching a word of length L costs O(L), no matter how many words are stored, and "does any word start with this prefix?" is answered by simply walking down the tree. That makes tries the natural structure for autocomplete, spell-checking and dictionary problems.
Each node typically holds a map (or a fixed array of 26) of children plus an isEnd flag. Beyond basic insert and search, the interview patterns are: wildcard search (DFS over all children when you see a '.'), trie + backtracking (search a whole board for many words at once, pruning as soon as a prefix is missing), and the bitwise trie, which stores numbers bit by bit to find the maximum XOR pair in O(n · 32).
This is a short topic, but tries show up regularly at Google, Amazon and Microsoft, often as the optimisation that turns a timed-out brute force into an accepted solution.
Build the data structure from scratch; asked verbatim in interviews.
Wildcard search with DFS over children.
Building words one letter at a time through the trie.
Storing aggregate values on trie nodes.
DFS that allows exactly one mismatch.
Autocomplete, the textbook trie application.
The bitwise trie for greedy XOR maximisation.
Trie-pruned grid backtracking; a top Hard at Google and Amazon.
Prefix and suffix reasoning across a word list.