Problem 63 · Strings & Tries

Search Autocomplete System (Top-3 by Frequency)

HardClassic DSA & systems

01Problem

Design an autocomplete system initialized with historical sentences and counts. input(c) appends c to the current query and returns the top 3 historical sentences with that prefix, ranked by count desc then lexicographically; '#' ends the query, records it, and returns [].

02Key insight

Keep a trie whose nodes cache the top-k sentences for their prefix; on each record, update the cache along the sentence path. Track the current node across keystrokes so each character is O(1) navigation plus a k-sized read.

03Solution

solution.pypython44 lines

from __future__ import annotations


class _Node:
    __slots__ = ("children", "top")

    def __init__(self) -> None:
        self.children: dict[str, _Node] = {}
        self.top: list[str] = []  # cached top-k sentences under this prefix


class AutocompleteSystem:
    K = 3

    def __init__(self, sentences: list[str], times: list[int]) -> None:
        self.root = _Node()
        self.counts: dict[str, int] = {}
        for s, t in zip(sentences, times):
            self._record(s, t)
        self.query: list[str] = []
        self.cursor: _Node | None = self.root

    def _rank(self, s: str) -> tuple[int, str]:
        return (-self.counts[s], s)

    def _record(self, sentence: str, delta: int) -> None:
        self.counts[sentence] = self.counts.get(sentence, 0) + delta
        node = self.root
        for ch in sentence:
            node = node.children.setdefault(ch, _Node())
            if sentence not in node.top:
                node.top.append(sentence)
            node.top.sort(key=self._rank)
            del node.top[self.K:]

    def input(self, c: str) -> list[str]:
        if c == "#":
            self._record("".join(self.query), 1)
            self.query, self.cursor = [], self.root
            return []
        self.query.append(c)
        if self.cursor is not None:
            self.cursor = self.cursor.children.get(c)
        return list(self.cursor.top) if self.cursor else []

Try it first.

TimeO(L * k log k) record, O(1) per keystroke

SpaceO(total chars * k)

tests.py · 6 passing

tests.pypython8 lines

ac = AutocompleteSystem(["i love you", "island", "ironman", "i love leetcode"], [5, 3, 2, 2])
assert ac.input("i") == ["i love you", "island", "i love leetcode"]
assert ac.input(" ") == ["i love you", "i love leetcode"]
assert ac.input("a") == []
assert ac.input("#") == []
assert ac.input("i") == ["i love you", "island", "i love leetcode"]
for ch in " a#": ac.input(ch)       # "i a" now has count 2, ties broken lexicographically
assert ac.input("i") == ["i love you", "island", "i a"]

04Staff-level follow-up

At web scale? Precompute top-k per prefix offline (MapReduce over query logs), shard by prefix, serve from cache/CDN, and blend in a small real-time trending layer with decayed counts.