642. Design Search Autocomplete System
Asked at Pinterest
Difficulty
Hard
Time
Insert: O(L). Each keystroke: O(
Space
O(total characters in all senten
Pattern
String
Companies
1
Problem
Design the engine behind a search box with autocomplete. You are given a list of historical sentences and, for each one, how many times users typed it before. Then the user types characters one at a time.
After each typed character, return up to 3 historical sentences that start with the text typed so far. Rank them by hot degree (how many times that exact sentence was typed before), highest first. If two sentences have the same hot degree, the one that comes first in ASCII order wins. If fewer than 3 sentences match, return all of them.
The character # means the user finished the sentence. In that case return an empty list, and remember the typed sentence: increase its count by 1 and add it to the history if it is new. After #, the next character starts a fresh sentence.
Implement a class AutocompleteSystem with a constructor that takes sentences and times, and a method input(c) that takes one character and returns the list of matches described above.
What the search box must return
Constraints
- ●
n == sentences.length == times.length - ●
1 <= n <= 100 - ●
1 <= sentences[i].length <= 100 - ●
1 <= times[i] <= 50 - ●
c is a lowercase English letter, a space, or '#' - ●
Each tested sentence ends with '#' and has length in [1, 200] - ●
Words inside a sentence are separated by single spaces - ●
At most 5000 calls to input
Examples
AutocompleteSystem(["i love you", "island", "iroman", "i love leetcode"], [5, 3, 2, 2])
input('i')
input(' ')
input('a')
input('#')[null, ["i love you", "island", "i love leetcode"], ["i love you", "i love leetcode"], [], []]AutocompleteSystem(["abc", "abb"], [2, 2])
input('a')
input('b')
input('b')
input('#')[null, ["abb", "abc"], ["abb", "abc"], ["abb"], []]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Hard | View all Pinterest questions → |
How to Think About It
Scanning every sentence on every keystroke is O(total characters) per character typed. A trie lets you jump straight to the sentences that share the prefix.
Key insight: store, at each trie node, the set of sentences that pass through it. Keep counts in a separate map so a count update does not require touching every node.
Keep a pointer to the trie node for the current prefix. Each new character just follows one child pointer instead of re-walking from the root. If the child does not exist, the prefix has no matches until #.
Ranking: sort the candidates at the node by (-count, sentence) and take the first 3. (A heap of size 3 works too; sorting is simpler to explain.)
On #: increment the count of the typed sentence, insert it into the trie if it is new, reset the prefix to empty and the pointer to the root, and return an empty list.
Optimal Approach
State: trie root, counts map, current prefix, current node cur.
Constructor: for each (sentence, time), set counts[sentence] = time and insert the sentence into the trie, adding it to every node on its path.
input(c):
Step 1: If c == "#": counts[prefix] += 1, insert prefix into the trie, reset prefix = "" and cur = root, return [].
Step 2: prefix += c. If cur is null or has no child c, set cur = null and return [].
Step 3: cur = cur.children[c]. Sort cur.sentences by (-counts[s], s) and return the first 3.
Time: insert O(L); each keystroke O(m log m) where m is the number of sentences under the node. Space: O(total characters).
Trie with a moving pointer
What Trips People Up in Real Interviews
Re-walking the trie from the root on every keystroke. Keep a pointer to the current node — each character is one step.
Storing counts inside every trie node. Then recording a sentence means updating counts along its whole path; a single counts map is simpler.
Ranking ties incorrectly. Equal counts are broken by ASCII order, and space sorts before letters.
Forgetting that once the prefix has no match, later characters (before #) also have no match — but the characters still have to be appended to the prefix so # records the right sentence.
Not resetting state after #.
Solution Code
Insert: O(L). Each keystroke: O( timeclass TrieNode:
def __init__(self):
self.children = {}
self.sentences = set()
class AutocompleteSystem:
def __init__(self, sentences, times):
self.root = TrieNode()
self.counts = {}
for s, t in zip(sentences, times):
self.counts[s] = t
self._insert(s)
self.prefix = ''
self.cur = self.root
def _insert(self, s):
node = self.root
for ch in s:
node = node.children.setdefault(ch, TrieNode())
node.sentences.add(s)
def input(self, c):
if c == '#':
self.counts[self.prefix] = self.counts.get(self.prefix, 0) + 1
self._insert(self.prefix)
self.prefix = ''
self.cur = self.root
return []
self.prefix += c
if self.cur is None or c not in self.cur.children:
self.cur = None
return []
self.cur = self.cur.children[c]
ranked = sorted(self.cur.sentences, key=lambda s: (-self.counts[s], s))
return ranked[:3]Frequently Asked Questions
What is the Design Search Autocomplete System problem?
Design Search Autocomplete System asks you to build the engine behind a search box. It starts with historical sentences and their counts; as the user types one character at a time, it returns the top 3 historical sentences with the current prefix, ranked by count and then alphabetically. Typing `#` ends the sentence and records it. It is a trie design question with a ranking twist.
How do you solve Design Search Autocomplete System?
The optimal approach runs in Insert: O(L). Each keystroke: O( time and O(total characters in all senten space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Design Search Autocomplete System?
Design Search Autocomplete System is asked at Pinterest. It is a hard difficulty problem.
What are common mistakes on Design Search Autocomplete System?
- Re-walking the trie from the root on every keystroke. Keep a pointer to the current node — each character is one step.
- Storing counts inside every trie node. Then recording a sentence means updating counts along its whole path; a single `counts` map is simpler.
- Ranking ties incorrectly. Equal counts are broken by ASCII order, and space sorts before letters.
- Forgetting that once the prefix has no match, later characters (before `#`) also have no match — but the characters still have to be appended to the prefix so `#` records the right sentence.
- Not resetting state after `#`.