Design Search Autocomplete System
Asked at Pinterest
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.
Asked At
| 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).
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
class 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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 `#`.