Algorithms and Data Structures · Senior · Question 59 of 75
Which structure would you use for an autocomplete that ranks suggestions by popularity?
- ✓Correct answer: A trie with the top suggestions cached at each node
- 2A hash map from full words to their counts only
- 3A sorted array scanned from the start
Explanation
The trie finds the prefix node in O(length of the prefix); caching the top k per node avoids walking the whole subtree on each keystroke. A plain map can't list words by prefix efficiently.