System Design (50 Qs)•Part 2: Real-World High-Scale Architecture Problems (11 - 25)
Design a Typeahead / Autocomplete Search System (Trie & Top-K Ranking).
In Simple Words: Provide real-time query suggestions as the user types each keystroke into a search bar within 30ms latency, handling 50,000 keystrokes per second.
Data Structure: Serialized Prefix Trie with Cached Top-K Suggestions:
- In a naive Trie, finding matching prefixes requires traversing all child subtrees and sorting results, taking $O(K log K)$ per keystroke.
- Optimization: Store the pre-computed Top-5 most frequent query completions directly inside every Trie node! Searching a prefix becomes an instantaneous $O(L)$ operation where $L$ is query length (rarely $> 20$ chars).
typescript
export class AutocompleteTrieNode {
public children = new Map<string, AutocompleteTrieNode>();
public topSuggestions: { query: string; score: number }[] = [];
public insert(query: string, score: number): void {
let curr: AutocompleteTrieNode = this;
for (const char of query.toLowerCase()) {
if (!curr.children.has(char)) {
curr.children.set(char, new AutocompleteTrieNode());
}
curr = curr.children.get(char)!;
curr.updateTopSuggestions(query, score);
}
}
private updateTopSuggestions(query: string, score: number): void {
const existing = this.topSuggestions.find(s => s.query === query);
if (existing) {
existing.score = score;
} else {
this.topSuggestions.push({ query, score });
}
this.topSuggestions.sort((a, b) => b.score - a.score);
if (this.topSuggestions.length > 5) {
this.topSuggestions.pop();
}
}
}