Skip to content
Tutorials Center
My learning

Topics

Lesson 209 of 225 ยท Projects

Project: Autocomplete Engine

Build a search-box autocomplete engine in stages. Start with brute force, move to a trie, cache top suggestions per node, learn from clicks, and test it.

Type "pro" into a search box and a list of suggestions appears before you finish the word: program, project, protocol. Behind that small feature is a classic data structure problem. The engine holds a large vocabulary with a popularity count for each word, and for every keystroke it must return the best few words that start with what you typed, fast enough that the user never notices.

In this project you will build that engine in stages. You will begin with the obvious brute-force solution, find out exactly why it does not scale, replace it with a trie, speed it up again by caching the best suggestions inside the trie, teach it to learn from what users choose, and finally test it against the brute-force version. Along the way you will use heaps, sorting with keys and top-k thinking.

The specification

Before writing code, pin down the behavior. Our engine supports three operations:

  • add(word, count) registers a word with a popularity count.
  • suggest(prefix, k) returns the k most popular words starting with prefix, most popular first. Ties are broken alphabetically so results are deterministic.
  • select(word) records that a user picked word, which increases its count by one so it ranks higher next time.

Everything is lowercase ASCII to keep the focus on the algorithms. Real systems also normalize case, strip accents and handle multi-word queries, but those are layers on top of the same core.

Stage 1: brute force

The simplest correct solution keeps all words in a dictionary. To answer a query, check every word, keep those starting with the prefix and pick the best k:

Python Stage 1: scan every word

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Negating the count lets heapq.nsmallest pick the biggest counts while sorting equal counts alphabetically (tuples compare element by element). This is correct, and nsmallest(k, ...) is cheaper than sorting everything, but notice the cost: every query examines every word. With n words of average length L, a query costs O(n * L) just for the startswith checks, even when the prefix is zebra and nothing matches. A real vocabulary has millions of entries, and queries arrive on every keystroke. We need to avoid looking at words that cannot match.

A trie stores words along paths of letters, so all words sharing a prefix share a path. To answer a query you walk down the prefix once, which costs O(L) regardless of vocabulary size, and then only the words in that subtree can match:

TEXT
root
 โ”œโ”€ c โ”€ a โ”€ r*(120) โ”€ d*(80)
 โ”‚          โ”‚        โ”œโ”€ e*(95) โ”€ f โ”€ u โ”€ l*(30)
 โ”‚          โ”‚        โ””โ”€ t*(60)
 โ”‚          โ””โ”€ t*(150) โ”€ a โ”€ l โ”€ o โ”€ g*(40)
 โ””โ”€ p โ”€ r โ”€ o โ”€ g โ”€ r โ”€ a โ”€ m*(200) ...
 (* marks the end of a word, with its count)

Each node is a dictionary from letter to child, plus an optional count. To suggest, we find the node for the prefix and then run a depth-first search over its subtree to collect every word, then pick the top k:

Python Stage 2: a trie and a subtree search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A query for zebra now touches nothing at all, and dog visits a single node. But look at ca and pro: the search still visits every node under the prefix. For the prefix a in a dictionary of a million words, that subtree is huge, and short prefixes are exactly what users type first. The trie fixed the "nothing matches" case but not the "too many matches" case.

Stage 3: remember the best suggestions at every node

The fix is a classic trade of memory for time. Instead of searching the subtree at query time, store at each node the top k words in its subtree, already ranked. A query then walks down the prefix and returns the list found at the last node: no subtree search, so O(L + k) time.

When we build the trie, each inserted word is pushed into the "best list" of every node along its path, and each list keeps only its k best entries:

Python Stage 3: top-k lists stored in the nodes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Even the empty prefix (the root) answers instantly with the three most popular words overall. The price is memory: each node holds up to k entries, so total space grows from O(total letters) to O(total letters * k). Insertion also costs O(L * k log k) per word because every node on the path updates its list. This is the usual shape of an index: pay at write time to make reads cheap, which is the right deal when reads vastly outnumber writes.

Tip: if k is small (5 to 10 in real search boxes), the per-node list is tiny and sorting it is effectively constant time. Storing a pointer to the best word's node instead of its text saves memory when the vocabulary is large.

Stage 4: learn from the user

A static ranking gets stale. When a user types pro and picks proxy, that is evidence that proxy deserves a higher rank. The select operation must add one to a word's count and update every best list on its path. Because counts only ever increase, the update is simple: take the word out of each list on its path (if present) and offer it again with its new count. A word that was not in a list can enter it, one that was can only move up, and nobody else changes, so each list stays the correct top k.

Here is the complete engine with add, suggest and select:

Python Stage 4: the complete autocomplete engine

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After 40 selections proxy has count 85, which still loses to project (160), program (200) and programming (180) but beats promise (75) and protocol (55). After 120 more (160 in total) it reaches 205 and becomes the top suggestion. Notice that select is just add(word, 1): one code path, less to get wrong.

Stage 5: test against the brute force

How do you know the clever version is correct? Compare it with the stage-1 solution, which is simple enough to trust, on lots of inputs. This technique, differential testing, is one of the best ways to verify any optimized algorithm. We generate random words from a small alphabet (so prefixes collide a lot), random counts, random selections, and compare after every step:

Python Stage 5: differential test against brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If you break the engine on purpose (for example, forget to remove the old entry before re-adding a word), this test fails within a few steps and the assertion message tells you the step and prefix, so you can reproduce it. Writing tests this way is covered in How to solve algorithm problems.

Complexity summary

Let n be the number of words, L the length of a word or prefix, and k the number of suggestions.

Version suggest time Extra space Update cost
Brute force (stage 1) O(n * L) O(1) O(1)
Plain trie (stage 2) O(L + subtree size) O(total letters) O(L)
Trie with cached top-k (stages 3-4) O(L + k) O(total letters * k) O(L * k log k)

Ideas to extend it

  • Typos. Combine the trie with edit distance to suggest corrections (the spell checker project goes this way).
  • Recency. Multiply counts by a decay factor or keep separate "recent" and "all-time" counts.
  • Compression. Real tries compress chains of single-child nodes into one edge labeled with a string (a radix tree).
  • Mid-word matches. For queries like ram matching program, index all suffixes with a suffix structure.
  • Scale. Shard by first letters, and keep the top-k lists for short prefixes in a cache.

Common mistakes

  • Forgetting the tie-break. Without a deterministic order for equal counts, results flicker between runs and tests become flaky.
  • Never removing the old entry. If you only append to the cached list, the same word appears twice.
  • Using a mutable default or shared list for children. Each node needs its own dictionary and list.
  • Rebuilding the trie per query. The structure is only worth it if you build it once and reuse it.
  • Assuming counts can decrease. The simple update here relies on counts only growing. Decay or deletions need a rebuild of the affected lists from child lists.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is the brute-force autocomplete slow for a large vocabulary?

    A scan with startswith costs O(n * L) per query. A trie lets you skip every word that does not share the prefix.
  2. 2. What does storing the top k words in every trie node achieve?

    The answer is already stored at the node the prefix leads to. The price is more memory and slower updates, because every node on a word's path must be refreshed.
  3. 3. When a word is selected, why can we simply remove it from each list on its path and offer it again?

    If a word's count only grows, no other word can enter or leave a list because of it. The word can enter the list or move up, so the top k stays correct.
  4. 4. What does the key (-count, word) achieve in nsmallest?

    Negating the count turns "largest count" into "smallest key", and tuples compare the word second, so equal counts are ordered A to Z.
  5. 5. What is differential testing?

    A simple brute-force version is easy to trust, so any disagreement with the optimized version points to a bug in the optimized one.

Summary

  • Autocomplete = rank the words that share a prefix; brute force scans every word, so each query costs O(n * L).
  • A trie finds the prefix in O(L) but still needs a subtree search for short prefixes.
  • Caching the top-k list in every node makes queries O(L + k) at the cost of memory and slower writes: pay at write time, read cheaply.
  • A selection increments a count and refreshes the lists along one path; this works because counts only grow.
  • Differential testing against the brute-force version is the quickest way to trust the fast one.

Next: Project: Route Planner