Design Search Autocomplete System — Trie with Frequency Ranking

Problem

Design an autocomplete system for a search engine:

Constructor: given list of sentences and their historical frequencies
input(c): type character c. If c == '#', save current sentence and reset. Otherwise, return top 3 matching sentences (by frequency desc, then lexicographic asc).

Key Insight — Trie + Per-Node Top-K

Approach 1 (Simple): Store all (sentence, freq) pairs. On each input, filter by prefix and return top 3.

Approach 2 (Trie): Each Trie node stores a map of sentence → frequency for all sentences passing through it. input(c) looks up the current prefix node and returns top 3 from its map.

Solutions

Python — HashMap Approach

import heapq
from collections import defaultdict

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

Python — Trie Approach

from collections import defaultdict
import heapq

class TrieNode:
    def __init__(self):
        self.children = {}
        self.freq = defaultdict(int)

class AutocompleteSystem:
    def __init__(self, sentences, times):
        self.root = TrieNode()
        self.curr = []
        self.node = self.root
        for s, t in zip(sentences, times):
            self._insert(s, t)

    def _insert(self, s, freq):
        node = self.root
        for c in s:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
            node.freq[s] += freq

    def input(self, c: str):
        if c == '#':
            sentence = ''.join(self.curr)
            self._insert(sentence, 1)
            self.curr = []
            self.node = self.root
            return []
        self.curr.append(c)
        if self.node and c in self.node.children:
            self.node = self.node.children[c]
            items = sorted(self.node.freq.items(), key=lambda x: (-x[1], x[0]))
            return [s for s, _ in items[:3]]
        else:
            self.node = None
            return []

JavaScript

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]);
    }
}

Java

import java.util.*;
class AutocompleteSystem {
    Map<String, Integer> freq = new HashMap<>();
    StringBuilder curr = new StringBuilder();
    public AutocompleteSystem(String[] sentences, int[] times) {
        for (int i = 0; i < sentences.length; i++)
            freq.merge(sentences[i], times[i], Integer::sum);
    }
    public List<String> input(char c) {
        if (c == '#') { freq.merge(curr.toString(), 1, Integer::sum); curr = new StringBuilder(); return new ArrayList<>(); }
        curr.append(c);
        String p = curr.toString();
        return freq.entrySet().stream()
            .filter(e -> e.getKey().startsWith(p))
            .sorted((a,b) -> !a.getValue().equals(b.getValue()) ? b.getValue()-a.getValue() : a.getKey().compareTo(b.getKey()))
            .limit(3).map(Map.Entry::getKey).toList();
    }
}

C++

#include <unordered_map>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class AutocompleteSystem {
    unordered_map<string,int> freq;
    string curr;
public:
    AutocompleteSystem(vector<string>& sentences, vector<int>& times) {
        for (int i = 0; i < (int)sentences.size(); i++) freq[sentences[i]] += times[i];
    }
    vector<string> input(char c) {
        if (c == '#') { freq[curr]++; curr = ""; return {}; }
        curr += c;
        vector<pair<int,string>> matches;
        for (auto& [s, f] : freq)
            if (s.substr(0, curr.size()) == curr) matches.push_back({-f, s});
        sort(matches.begin(), matches.end());
        vector<string> res;
        for (int i = 0; i < min(3, (int)matches.size()); i++) res.push_back(matches[i].second);
        return res;
    }
};

C

/* C: linear scan of sentence array + qsort with frequency comparator */