Art of Codeartofcode
Lesson 5 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.4 What do we store?

3 min read+10 XP
prefix_suggestions (serving store: in-memory KV / Redis, sharded by prefix) key: "dat" value: ["data science", "database internals", ...] (top 5, already ranked) version: 2026-10-08T06:00 (which build produced it) query_counts (offline: warehouse / batch storage) query, day, count trending_counts (streaming: decayed counts for the last few hours) query, decayed_count, updated_at

Interviewer pushback:

  • "Why store the top 5 for every prefix instead of a trie you walk?" → Walking a subtree to find the top 5 at request time is slow for short prefixes, which have the biggest subtrees and the most traffic. Storing the answer per prefix makes every request a single key lookup (34.6).

Memory code: "The prefix is the key; the answer is already sorted."