Art of Codeartofcode
Lesson 8 of 15

34. Design Search Autocomplete (Typeahead)

1
The interview prompt
2
34.1 What do you ask first?
3
34.2 How big is this, really?
4
34.3 What are the doors?
5
34.4 What do we store?
6
34.5 What does the whole system look like?
7
34.6 Trie or prefix index?
8
34.7 How do you compute top-K per prefix?
9
34.8 How do suggestions follow trends?
10
34.9 How do you cache suggestions?
11
34.10 What would you say in the last five minutes?
12
Score yourself
13
Variations to practise
14
Sources
15
Code lab
34. Design Search Autocomplete (Typeahead)

34.7 How do you compute top-K per prefix?

3 min read+10 XP

The offline job:

  1. Count queries over a window (say the last 28 days), from the search log.
  2. Normalise (lowercase, trim spaces), and filter: drop queries below a minimum count, blocked terms, and obvious spam.
  3. For each query and each of its prefixes, emit (prefix, query, score).
  4. Group by prefix and keep the top 5 by score, using a small heap per prefix.
  5. Publish the table as a new version.

At 50 million distinct queries, this is a batch job (MapReduce, Spark, or SQL in a warehouse): the "emit every prefix" step is large but simple and parallel. Use count-min sketch and top-K (Chapter 20) if you need the counts from a stream without storing every query.

Two refinements interviewers like:

  • Limit prefix length (say 20 characters): beyond that, users rarely need help, and it cuts storage.
  • Mix in new titles: a just-published book has no search history yet; add it with a boost so it can appear before anyone has searched for it.

Memory code: "Count, filter, explode into prefixes, keep the best five."