Art of Codeartofcode
Lesson 14 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)

Sources

3 min read+10 XP

Source notes

  • Tries, prefix search and edge n-grams: see Chapter 19. Count-min sketch, top-K and HyperLogLog: see Chapter 20.
  • All traffic numbers, query counts, prefix ratios and pruning factors are interview assumptions agreed in Step 1, not figures for any real service. Arithmetic computed 2026-10-08.
  • Trie vs flat-table equivalence, top-K building, decayed trend blending and prefix-length traffic shares: tested 2026-10-08 (code/ch34_autocomplete.py, all checks pass; synthetic query log).