Design Search Autocomplete System
Hard · Tries · String · Depth-First Search · Design · Trie · Sorting · Heap (Priority Queue) · Data Stream
Problem
Design a search autocomplete system. A user types a sentence one character at a time, and a sentence always ends when the user types the special character '#'.
The history is given as two arrays: sentences[i] has been typed times[i] times. The number of times a sentence has been typed is its hot degree. Implement AutocompleteSystem:
- AutocompleteSystem(sentences, times) loads the history.
- input(c) processes the next character:
- If c == '#', the sentence typed so far is complete. Record it in the history (adding 1 to its hot degree, or adding it with degree 1), reset the current input, and return an empty list.
- Otherwise, append c to the current input and return the top 3 sentences in the history that start with the current input, by hot degree (higher first); ties are broken by character order (smaller first, so a space comes before any letter). Return fewer than 3 if fewer match.
Tests replay a call sequence: the first entry names the class and its constructor arguments, each later entry is a method with its arguments, and calls returning nothing report None.
Examples
Input: ops = ["AutocompleteSystem","input","input","input","input","input"], args = [[["dog park","dog","door","cat"],[3,2,2,1]],["d"],["o"],["o"],["#"],["d"]] Output: [null,["dog park","dog","door"],["dog park","dog","door"],["door"],[],["dog park","dog","door"]]
"dog" and "door" tie on 2 and are ordered by character. After '#', "doo" is stored with degree 1, too low to enter the top 3.
Input: ops = ["AutocompleteSystem","input","input","input","input"], args = [[["ab","ac"],[1,1]],["a"],["c"],["#"],["a"]] Output: [null,["ab","ac"],["ac"],[],["ac","ab"]]
Typing "ac#" raises "ac" to degree 2, so it now ranks above "ab".
Constraints
- 1 <= len(sentences) == len(times) <= 100
- 1 <= len(sentences[i]) <= 100
- 1 <= times[i] <= 50
- c is a lowercase English letter, a space or '#'
- each typed sentence has 1 to 200 characters before its '#'
- at most 5000 calls to input
Approaches
- Scan every sentence on every keystroke — time O(n · L + n log n) per character, space O(total length)
Follow-up
With millions of sentences, ranking every match on every keystroke is too slow. Cache the top three at each trie node: a lookup is then O(1) after the step, and recording a sentence updates the caches of the O(L) nodes on its path (re-rank that node’s three plus the changed sentence). Real systems also precompute these lists offline and shard the trie by first letters.
Related problems
Start free on Cariara · Coding problems · System design studio
