Design Search Autocomplete System — Trie with Frequency Ranking

Problem Statement#

Design an autocomplete system for a search engine. Given a list of historical sentences and their hit counts, return the top 3 matching sentences (by frequency descending, then lexicographically ascending) as the user types each character. Typing # saves the current sentence and resets input.

Constraints:

• 1 <= sentences.length <= 100
• 1 <= sentences[i].length <= 100
• 1 <= times[i] <= 50
• input is called at most 5000 times
• Input characters are lowercase English letters, spaces, or #

Input:  sentences=["i love you","island","iroman"], times=[5,3,2], input("i")
Output: ["i love you","island","iroman"]

Input:  ... input("i"), input(" "), input("a"), input("#")
Output: ["i love you","island","iroman"], ["i love you"], [], []

Why This Problem Matters#

Autocomplete is one of the most visible features in search engines. Google processes over 8.5 billion searches per day, and autocomplete suggestions load within 100 ms. The underlying mechanism—prefix matching with frequency ranking—uses data structures like Tries and sorted frequency maps. This problem appears in FAANG interviews because it tests your ability to combine multiple structures to meet latency constraints.

At Google and Bing, autocomplete pipelines also account for personalisation, geographic signals, and recency decay. The LeetCode version simplifies this to pure frequency ranking, but the core Trie-based lookup principle is identical.

This is a hard-level design problem that evaluates both your data structure knowledge and your ability to handle state across multiple input calls—key skills for senior engineering roles.

The Core Insight#

Two approaches work here. The simpler one stores all sentences in a frequency map and, on each input, filters by prefix and returns the top 3 with a heap. This is O(M) per character where M is the total number of stored sentences.

The Trie approach is more scalable: each Trie node stores a {sentence: frequency} map for all sentences passing through that prefix. Traversal follows the current character path, and lookup is O(P + K log K) where P is prefix length and K is candidates at that node. The Trie avoids re-scanning all sentences on every character.

The state (current Trie node) must persist across input calls for the Trie approach—resetting to root on #.

Visual Dry Run#

Solution (Optimal)#

from collections import defaultdict
import heapq
 
class AutocompleteSystem:
    def __init__(self, sentences, times):
        self.freq = defaultdict(int)
        for s, t in zip(sentences, times):
            self.freq[s] += t
        self.curr = []
 
    def input(self, c: str):
        if c == '#':
            self.freq[''.join(self.curr)] += 1
            self.curr = []
            return []
        self.curr.append(c)
        prefix = ''.join(self.curr)
        heap = []
        for s, f in self.freq.items():
            if s.startswith(prefix):
                heapq.heappush(heap, (-f, s))
        res = []
        while heap and len(res) < 3:
            res.append(heapq.heappop(heap)[1])
        return res

class AutocompleteSystem {
    constructor(sentences, times) {
        this.freq = new Map();
        this.curr = "";
        for (let i = 0; i < sentences.length; i++) {
            this.freq.set(sentences[i], (this.freq.get(sentences[i]) || 0) + times[i]);
        }
    }
 
    input(c) {
        if (c === '#') {
            this.freq.set(this.curr, (this.freq.get(this.curr) || 0) + 1);
            this.curr = "";
            return [];
        }
        this.curr += c;
        return [...this.freq.entries()]
            .filter(([s]) => s.startsWith(this.curr))
            .sort((a, b) => b[1] - a[1] || a[0].localeCompare(b[0]))
            .slice(0, 3)
            .map(x => x[0]);
    }
}

Time: O(M) per input call for the hashmap approach, O(P + K log K) for the Trie approach
Space: O(M * L) — M sentences of average length L stored in the frequency map or Trie

Common Mistakes#

• Forgetting to reset curr to an empty list/string after #
• Not updating frequency on #: the typed sentence must be added or incremented
• Using >= instead of > in frequency comparison, breaking lexicographic tie-breaking
• Returning more than 3 results by accident when multiple sentences have equal frequency
• In the Trie approach, not handling the case where curr_node is None after a missing character

Interview Tips#

• Always discuss both approaches (hashmap vs Trie) and their trade-offs before coding
• The hashmap approach is easier to implement correctly and should be your starting point
• Mention that the Trie is better when the sentence dictionary is large and static; the hashmap wins when it is small or frequently updated
• For the ranking comparison, use a tuple (-freq, sentence) in the heap to handle both dimensions in one push
• State explicitly that # both saves the sentence AND resets state—two actions from one character

Follow-up Questions#

• How would you handle a trillion historical queries efficiently? (Offline preprocessing, distributed Trie across shards)
• How would you add personalisation—weight queries by the current user's history? (Per-user frequency overlay on global Trie)
• How would you handle real-time updates from millions of concurrent users? (Approximate counters with eventual consistency)
• Can you add a recency decay so older queries matter less? (Exponential moving average on frequency)
• How does this extend to multi-word prefix matching with typo tolerance? (Edit distance on Trie nodes, BK-tree)

Key Takeaways#

• The hashmap approach is O(M) per character; the Trie approach is O(P + K log K) per character
• Ranking uses frequency descending then lexicographic ascending—implement with a (-freq, sentence) min-heap
• The # character triggers two actions: increment the frequency of the current sentence, then reset input state
• Trie nodes store per-node frequency maps so prefix lookup avoids scanning all sentences
• This problem tests stateful design: the current prefix and current Trie node must persist across calls
• Real autocomplete systems also use personalization, recency, and geographic signals on top of this foundation
• LeetCode 642 is the canonical version; Google and Bing interviews use variants with additional ranking signals