Question Bank
Trie Essentials
Difficulty: Medium
Prompts on the prefix-tree shape, insert and lookup costs, and the autocomplete pattern. Builds the model before tackling KMP-like or word-search problems.
Trie Essentials
Prompts on the prefix-tree shape, insert and lookup costs, and the autocomplete pattern. Builds the model before tackling KMP-like or word-search problems.
431 views
6
Implement a Trie class with insert(word) and search(word) returning whether the exact word was inserted. Use a dictionary at each node.
Examples
Example 1:
Input: insert('cat'), insert('car'); then search('cat'), search('ca'), search('cars')
Output: True, False, False
Explanation: Each node has a children dict plus an is_end flag. search returns is_end at the destination; 'ca' lands on an internal node so is_end is False, and 'cars' falls off the trie at 's'.Add startsWith(prefix) to the Trie above, returning True iff any inserted word starts with prefix. Justify why this is the trie's natural strength.
Examples
Example 1:
Input: insert('apple'); then starts_with('app'), starts_with('apz')
Output: True, False
Explanation: starts_with walks the trie like search but does NOT require is_end at the destination; reaching the prefix node is enough. 'apz' fails because no edge from the 'p' node matches 'z'.Given the words ["car", "care", "cart", "dog"], sketch the trie shape: list each non-root node by its accumulated prefix and mark which nodes have is_end = True.
Compare a Trie and a HashSet for membership testing on n words of average length m. State time and space complexity, and one scenario where each clearly wins.