Art of Codeartofcode
Lesson 9 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.8 How do suggestions follow trends?

3 min read+10 XP

A daily job can't react to something that started this morning: a new book launch, an author in the news, an exam result. Blend two signals:

  • Long-term score: counts over weeks, from the batch job.
  • Recent score: counts from a stream (Chapter 22), with exponential decay: each hour's count weighs half as much every 2 hours, so yesterday fades fast.
  • score = long-term + w × recent, with w chosen so a real surge can beat a steady favourite.

a steady old favourite vs a new launch; with batch-only scores the launch appears tomorrow, with a trending blend it appears now.

Figure: blend slow, stable popularity with fast, decaying recency.

In the chapter's code: an old favourite searched 1,000 times an hour for two days vs a new launch with 3,000 then 6,000 in its first two hours. The long-term score keeps the old favourite far ahead (about 43,600 vs 9,000). Blending with 10 × recent puts the launch ahead (about 90,000 vs 78,000), so it appears in suggestions within the hour.

Guard the trending path more carefully than the batch path: it's the easiest place for manipulation (bots searching a phrase to push it into suggestions) and for offensive suggestions to slip in. Filter it, rate-limit per user (Chapter 25), and count unique users rather than raw searches (HyperLogLog, Chapter 20).

Memory code: "Popular for weeks plus rising right now, with a filter on the fast lane."