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

Variations to practise

3 min read+10 XP

Chapters used

Approach (1), Estimation (2), Caching (12, 13), Search and tries (19), Probabilistic counting and top-K (20), Message queues and streams (22), Rate limiting (25), CDNs (26).

Try these variations

Each is a common follow-up. Answer in two minutes, then check the sketch.

  1. "Personalise it." → Keep the shared table for the base list; on the client (or a small per-user store), merge in the user's own recent searches that match the prefix.
  2. "Support Hindi and Tamil." → Normalise per script, build separate tables per language, and pick by the user's language or the script being typed.
  3. "Fix typos." → Fall back to fuzzy matching (edit distance 1-2) on a smaller set of popular queries when an exact prefix has no suggestions.
  4. "100× traffic." → More CDN caching and longer TTLs for short prefixes, more replicas of the prefix store, and push the top 1,000 prefixes into the app bundle itself.