Search Autocomplete

Typeahead suggestions from a prefix tree

Design the object behind a search box that shows the most searched queries starting with what the user has typed so far, and learns from every search.

Overview

As a user types into a search box, the box shows a short list of complete queries that start with the letters typed so far, most popular first. Every submitted search is recorded, so tomorrow's suggestions reflect today's searches. The low level design version asks for one class with two operations: suggest(prefix) returns the top k queries for a prefix, and record_search(query) counts a search.

The problem tests three things. First, whether you pick a data structure whose lookup cost depends on the prefix, not on how many queries are stored: a trie (prefix tree), where each node is one character and the path from the root spells a prefix. Second, whether you see that walking every word under a short prefix like 'a' on every keystroke is too slow, and store each node's top k answers on the node instead. Third, whether you keep the stored lists correct as counts change, and safe when searches are recorded while other users read.

A strong answer names the trie in the first minute, says 'precompute the top k per node', explains why that list stays correct when counts only go up, and says what breaks when they can go down (recency decay).

Scoping the problem

How many suggestions? — Sets k, the length of each node's list — 3 in the demo; 5 to 10 in real boxes
Ranked by what? — Count only keeps lists simple; recency or personalization changes the update rule — Search count, ties alphabetical
Case and spaces? — 'Car ' and 'car' must be one query — Trim, collapse spaces, lowercase
When does a search count: every keystroke, or on submit? — Keystrokes are not searches — On submit only
Must a new search show up at once? — Online update versus a nightly rebuild — At once in the class; rebuild is a follow-up
Many users at the same time? — Reads and writes need a lock or snapshots — Yes
Can queries be deleted (abuse, legal removal)? — Removal lowers a count, which breaks the simple update rule — Follow-up

Core entities

The count table holds the truth: how many times each full query was searched. The top tuples on the nodes are a cache derived from it, kept up to date on every write so that reads never have to walk the subtree.

The trie with top k on every node

The diagram shows the trie after the demo's first searches, with k = 3. Every node on the path of a query holds that query in its list if it is among the three best below that node.

suggest(prefix of length L) — walk L nodes, then visit every word below and sort — walk L nodes, copy k items: O(L + k)
record_search(query of length L) — O(L) — O(L × k log k): re-sort a short list on each node of the path
Memory — one node per distinct character path — the same, plus k references per node

Reads happen on every keystroke and writes only on submit, so moving the work to the write is the right trade.

Why the stored lists stay correct

Counts only go up in this design. A query can enter a node's top k only when its own count rises, and that is exactly when record_search visits every node on its path and re-ranks the list there. A query that is not being searched never needs to move. That argument is the heart of the answer, and it is also the reason decay and deletion are hard (see the questions below).

The trace below is the demo in the implementation, with k = 3.

Seed searches — car rental 5, cart 3, cat videos 3, carbon 1, dog 2 — car rental, cart, cat videos (the 3-3 tie breaks alphabetically)
Three more searches for 'Carbon' — carbon 4 — car rental, carbon, cart
8 threads record 'cab' 200 times each — cab 1600 — cab first under 'c'

Normalization and ranking

Stored queries and typed prefixes go through the same normalize function, so ' CAR ' finds 'car rental'. Ranking is a small policy object with one method, key(query, count), which returns a sort key. The default sorts by count, highest first, and breaks ties alphabetically so results never flicker between two equal queries.

ByCount (the code) — (-count, query) — No: counts only rise
Count with time decay — (-count × decay(age), query) — Yes: scores fall without a write
Personalized — global score plus a boost from the user's history — Per user; merge at read time instead of storing

What you will be able to do

Explain why a trie makes lookup cost depend on the prefix length, and why storing the top k on each node makes a keystroke O(L + k).
Write record_search that re-ranks each node on the path, and argue why that keeps every list correct while counts only rise.
Normalize input once and break ties deterministically.
Say what breaks with decay, deletion or personalization, and how a periodic rebuild or a read-time merge fixes it.
Place the lock and explain the read-heavy alternative: build a new trie and swap one reference.

Functional requirements

suggest(prefix) returns up to k stored queries that start with the prefix, most searched first
Ties in count break alphabetically so results are stable
record_search(query) counts a submitted search and updates the suggestions at once
Input is trimmed, inner spaces collapsed and lowercased, for both stored queries and prefixes
An empty prefix or a prefix with no match returns an empty list
The ranking rule is a replaceable policy object

Non-functional requirements

suggest is O(L + k) for a prefix of length L, independent of how many queries are stored
record_search is O(L × k log k)
Safe with many readers and writers at once: no lost counts, no list that disagrees with the counts
Deterministic: same searches, same suggestions

Interview questions

Why not just run a LIKE prefix query against the database?
Recent searches should count more than old ones. What changes?
How do you remove a query, for example an offensive one?
Where is the lock, and what would you do if reads vastly outnumber writes?
How does this scale past one machine?