MediumPrefix Tree
Trie
A trie stores strings by shared prefixes and supports fast prefix lookup, autocomplete, and word search.
Intuition
Each edge is a character; each path is a prefix. Shared prefixes avoid repeated work across words.
Complexity Analysis
Insert/search are O(L) for word length L. Space can be large because each node may hold many child pointers.
Common Mistakes
- Jumping to code before naming the invariant or state being maintained
- Forgetting edge cases such as empty input, one element, duplicates, and negative values
- Using a brute-force approach without explaining how the pattern improves it
Interview Notes
- State the brute force first, then explain the bottleneck and the optimization
- Say the time and space complexity before the interviewer asks
- Walk through one small example and one edge case
Best Practices
- Keep variable names tied to the invariant: left, right, seen, window, slow, fast
- Prefer simple control flow over clever one-liners in interviews
- Write tests for boundary cases after the main solution
Example Problems
- Implement Trie
- Word Search II
- Design Add and Search Words