Tries
Prefix trees for search, autocomplete and max XOR.
4 notes · 20 min total
Questions0 of 19 done
Warm up with these before Phase 1.
Patterns
- 1Standard Trie (and When Not to Use One)Build a prefix tree for O(L) insert, search and prefix checks, store markers in nodes, and know when a hash set is the better tool.5 min
- 2Wildcard and Grid Search with a TrieUse a trie to guide a DFS: branch over every child for a wildcard, and prune grid backtracking the moment no word can match.5 min
- 3Autocomplete Payloads & Reverse/Combined KeysStore ready-made answers such as top suggestions in trie nodes, and change what you insert to answer suffix and stream queries.6 min
- 4Bitwise Trie for Max XORStore numbers bit by bit in a two-child trie and greedily take the opposite bit to find the largest XOR.4 min