Design Typeahead Autocomplete

Problem and scope

Typeahead (also called autocomplete or search suggestions) is the dropdown that appears while you type into a search box. Type "how to l" and you see "how to lose weight", "how to learn python", "how to link aadhaar with pan". It saves typing, fixes spelling before it happens, and steers people towards queries that return good results. Search engines, e-commerce sites, food delivery apps and video platforms all have one.

The problem looks small: "given a prefix, return the best few completions". What makes it a real design problem is latency. Suggestions must update between keystrokes, so each request has a budget of tens of milliseconds, end to end, at very high request rates, because every user sends several requests per search. A design that queries a database with LIKE 'how to l%' and sorts by popularity falls over long before you reach that scale.

Interviewers usually probe four things: the data structure (a trie, and why you precompute the top results at each node), how the data is built and refreshed from search logs, how you scale reads (sharding, replication, caching at the browser and CDN), and the product details: personalisation, trending queries and filtering offensive suggestions.

Clarifying questions

The most useful answer is about freshness. If daily rebuilds are acceptable, the suggestion data can be built offline and served read-only, which makes the serving path extremely simple and fast. Fresher signals become an add-on, not the core.

Functional and non-functional requirements

Functional:

• Given a prefix typed by the user, return up to 10 suggested completions, ranked.
• Rankings come mainly from how often queries are searched, weighted towards recent activity.
• Mix in the user's own recent searches when they match the prefix.
• Never show blocked terms.
• Record searches (the logs) so that the next build reflects them.

Non-functional:

• Very low latency: responses in tens of milliseconds; anything slower than the user's typing feels broken.
• High availability: if suggestions fail, search still works, so availability matters but this is not a hard dependency. Failing open (no dropdown) is acceptable.
• High read throughput: many requests per search.
• Eventual consistency is fine: a new popular query can appear in suggestions hours later.
• Read-heavy, write-light on the serving path: writes happen in bulk during builds, not per request.

Back-of-the-envelope estimates

Assumptions:

• 500 million searches per day.
• After the client waits for a short pause in typing (debouncing, explained in the API section), an average search triggers about 6 suggestion requests.
• Peak traffic is about 3 times the daily average.
• We keep suggestion data for the 10 million most popular queries, average length 20 characters.
• A response holds 10 suggestions, roughly 500 bytes with JSON overhead.

Request rate. 500,000,000 × 6 = 3 billion requests per day. 3,000,000,000 ÷ 86,400 ≈ 34,700 requests per second on average, and about 104,000 per second at peak.

Bandwidth. 104,000 × 500 bytes ≈ 52 MB per second at peak. Small; the challenge is the request count and latency, not bytes.

Size of the suggestion data. Each of the 10 million queries has at most 20 prefixes, so there are at most 10,000,000 × 20 = 200 million distinct prefixes. The real number is lower, because queries share prefixes ("how to l" is shared by thousands of queries). If each prefix entry costs about 100 bytes (the prefix itself, 10 suggestion ids of 4 bytes each, and overhead), the upper bound is 200,000,000 × 100 bytes = 20 GB. That fits in the memory of one large server, or comfortably across a few shards with replicas.

Short prefixes are few and hot. With 26 letters and 10 digits there are only 36 one-character prefixes and 36 × 36 = 1,296 two-character prefixes. Every search starts with one of them. These are perfect for caching at the CDN or even shipping to the client.

API design

GET /v1/suggest?q=how%20to%20l&limit=10&locale=en-IN
  headers: Authorization (optional, for personalisation)
  200 -> {
    "prefix": "how to l",
    "suggestions": [
      { "text": "how to lose weight",     "source": "global" },
      { "text": "how to learn python",    "source": "personal" },
      { "text": "how to link aadhaar with pan", "source": "global" }
    ]
  }
  Cache-Control: public, max-age=300   (for non-personal responses)

Client-side behaviour matters as much as the server:

• Debouncing: the client waits for a short pause after a keystroke (for example 100 to 150 ms) before sending a request, so a fast typist does not fire a request per character.
• Cancel stale requests: if the user types another character, the client cancels or ignores the response for the old prefix. Otherwise a slow response for "how to" might overwrite a fast one for "how to l".
• Local cache: the client keeps responses it has already fetched. Backspacing from "how to l" to "how to" should not call the server again.
• Normalise before sending: lowercase, trim and collapse spaces, so "How To L" and "how to l" share cache entries.

Logging is a separate path. When the user actually submits a search, the search service logs it; suggestion requests themselves are not counted as searches (otherwise partially typed prefixes would pollute the data).

Data model and storage choice

The key decision: the serving index is immutable. Each build produces a new snapshot; serving nodes load it, then switch to it in one step. Nothing on the serving path writes, so there are no locks, no consistency questions and no write amplification.

High-level design

                    ONLINE (serving)
 +----------+    +----------+    +----------------+
 | Client   |--->| CDN      |--->| Suggest API    |
 | debounce,|    | (short   |    | merge global,  |
 | cache    |    | prefixes)|    | personal,      |
 +----+-----+    +----------+    | trending;      |
      |                          | filter         |
      | submit search            +--+-----+----+--+
      v                             |     |    |
 +----------+     +---------+<------+     |    |
 | Search   |     | User    |             |    |
 | service  |     | history |  +----------+    |
 +----+-----+     +---------+  v               v
      | log           +----------+    +----------------+
      v               | Trending |    | Suggest servers|
 +----------+ stream  | overlay  |    | in-memory index|
 | Kafka:   |-------->+----------+    | sharded and    |
 | search   |                         | replicated     |
 | logs     |                         +-------^--------+
 +----+-----+                                 | load
      |            OFFLINE (daily build)      | snapshot
      v                                       |
 +----------+    +---------------+    +-------+--------+
 | Object   |--->| Batch job:    |--->| Snapshot files |
 | store    |    | count, decay, |    | per shard      |
 | (logs)   |    | filter, top-k |    +----------------+
 +----------+    +---------------+

Main components:

• Client: debounces, caches, cancels stale requests.
• CDN: caches responses for short, non-personal prefixes.
• Suggest API: a stateless layer that routes the prefix to the right shard, merges global, personal and trending suggestions, and applies a final filter.
• Suggest servers: hold the in-memory index for their shard and answer "top-k for this prefix" in microseconds.
• Search logs pipeline: search events go to Kafka, are stored in object storage, and feed both the daily batch build and a streaming trending job.
• Batch builder: turns logs into ranked, filtered prefix-to-top-k snapshots.

Request flows step by step

Flow 1: the user types "how to l"

1. The client waits for a pause in typing, normalises the prefix to how to l, and checks its local cache. Miss.
2. It calls GET /v1/suggest?q=how%20to%20l. If the user is signed out, the request is cacheable and the CDN may answer it directly.
3. On a CDN miss, the suggest API finds the shard that owns how to l, and calls a replica of it.
4. The suggest server looks up the prefix in its index and returns the precomputed top 10, in microseconds.
5. In parallel, the API fetches the user's recent searches starting with how to l and the trending overlay's entries for that prefix.
6. It merges the lists (deep dive 4), removes duplicates and anything on the blocklist, and returns up to 10 suggestions.
7. The client renders them and caches the response under how to l.

Flow 2: the user submits a search

1. The user picks "how to learn python" or presses Enter.
2. The search service runs the search and writes a log event: query text, timestamp, user or session id, locale.
3. The event lands in Kafka. The streaming job updates trending counts within minutes; the daily build counts it in tomorrow's snapshot.
4. The user's recent searches are updated for personalisation.

Flow 3: the daily build

1. A batch job reads the last day's logs and counts searches per normalised query.
2. It merges today's counts into the running decayed scores (deep dive 2).
3. It drops rare queries, blocked terms and queries with personal data.
4. It generates, for each prefix, the top 10 queries, and writes one snapshot file per shard.
5. Serving nodes download the new snapshot, load it into memory beside the old one, run sanity checks, then swap. The old one is released.

Deep dive 1: the trie with top-k cached per node

A trie (pronounced "try", from retrieval) is a tree where each edge is a character and each node represents the prefix spelled by the path from the root. All queries that start with "car" live under the node for "car". To find completions of a prefix, you walk down one node per character: the walk costs O(p) for a prefix of length p, no matter how many queries exist.

The slow version

A plain trie marks the nodes where a complete query ends, with its score. To answer "top 3 completions of ca", you walk to the ca node, then visit every node below it to collect complete queries, then sort them. Under a short prefix like s there could be millions of queries. That is far too slow per keystroke.

The fast version: store the answer at every node

Since suggestions only change at build time, precompute the top-k list at every node. Answering becomes "walk p characters, return the stored list". No subtree search, no sorting at query time.

The cost is memory: each node stores up to k entries. To keep it small, store references (ids into a query table, or pointers) rather than full strings, and limit the depth: suggestions for prefixes longer than about 20 to 30 characters add little.

Worked example

Eight queries with their scores:

With k = 3, work out the stored lists by hand:

• Node c: every query except "dog" is below it. Sorted by score: cat 60, car 50, career 40, cart 30, cats 25, care 20, catalog 10. Keep the top 3: cat, car, career.
• Node ca: the same seven queries, so the same list: cat, car, career.
• Node car: car 50, career 40, cart 30, care 20. Top 3: car, career, cart.
• Node care: career 40, care 20. Only two exist: career, care.
• Node cat: cat 60, cats 25, catalog 10: cat, cats, catalog.
• Node d: dog.

(root)
 +-- c   [cat, car, career]
 |   +-- a   [cat, car, career]
 |       +-- r   [car, career, cart]        "car" ends here
 |       |   +-- t   [cart]
 |       |   +-- e   [career, care]         "care" ends here
 |       |       +-- e -- r [career]
 |       +-- t   [cat, cats, catalog]       "cat" ends here
 |           +-- s [cats]
 |           +-- a -- l -- o -- g [catalog]
 +-- d   [dog]
     +-- o -- g [dog]

Here is a runnable Python version. The build offers each query to every node on its path, then trims each node's list to the best k:

import heapq


class Node:
    __slots__ = ("children", "top")

    def __init__(self):
        self.children = {}
        self.top = []          # up to K (query, score) pairs, best first


class Trie:
    def __init__(self, k):
        self.k = k
        self.root = Node()

    def build(self, scores):
        """scores: dict query -> weight. Built offline, then read-only."""
        for query, score in scores.items():
            node = self.root
            for ch in query:
                node = node.children.setdefault(ch, Node())
                node.top.append((query, score))
        self._trim(self.root)

    def _trim(self, node):
        # keep only the K best; ties broken alphabetically for stable output
        node.top = heapq.nsmallest(self.k, node.top, key=lambda p: (-p[1], p[0]))
        for child in node.children.values():
            self._trim(child)

    def suggest(self, prefix):
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return []
        return [q for q, _ in node.top]


scores = {"car": 50, "cart": 30, "care": 20, "career": 40,
          "cat": 60, "cats": 25, "catalog": 10, "dog": 70}
trie = Trie(k=3)
trie.build(scores)
for p in ["c", "ca", "car", "care", "cat", "d", "x"]:
    print(f"{p!r:8} -> {trie.suggest(p)}")

Output, matching the hand calculation:

'c'      -> ['cat', 'car', 'career']
'ca'     -> ['cat', 'car', 'career']
'car'    -> ['car', 'career', 'cart']
'care'   -> ['career', 'care']
'cat'    -> ['cat', 'cats', 'catalog']
'd'      -> ['dog']
'x'      -> []

Two practical notes. First, this build appends every query to every prefix node before trimming, which is simple but memory-hungry; at real scale the same idea runs as a distributed batch job (below). Second, the tie-break rule matters: without a deterministic one, two builds of the same data could order equal scores differently, and caches would churn for no reason.

From trie to prefix table

Notice what the serving path actually needs: prefix in, list out. Once the lists are precomputed, the tree structure is only a way to find them. You can equally store a flat hash map from prefix string to top-k list:

"c"    -> [cat, car, career]
"ca"   -> [cat, car, career]
"car"  -> [car, career, cart]
...

This is a little more memory (each prefix string is stored in full rather than shared along tree edges) but it has big advantages: one hash lookup per request, any key-value store can serve it, and each prefix is independent, which makes sharding trivial (deep dive 3). Many production systems serve exactly this, sometimes in a compact form such as a sorted array or a finite-state transducer (a compressed structure that shares both prefixes and suffixes). In an interview, explain the trie first, then say you would serve a precomputed prefix table.

Deep dive 2: building the index offline from query logs

The batch pipeline

raw search logs (yesterday)
   |
   | 1. normalise: lowercase, trim, collapse spaces,
   |    drop junk (very long, only symbols, obvious bots)
   v
(query, count, distinct_users) per day
   |
   | 2. merge into decayed running scores
   v
(query, score)
   |
   | 3. filter: min distinct users, blocklist,
   |    personal data patterns
   v
(query, score)  -- the candidate set, e.g. top 10 million
   |
   | 4. explode: emit (prefix, query, score) for every
   |    prefix of every query, up to max length
   v
group by prefix, keep top k
   |
   | 5. write snapshot files, one per shard
   v
serving nodes load and swap

Step 4 is where the trie build becomes a distributed job: a map step emits (prefix, query, score) for every prefix, a shuffle groups by prefix, and a reduce step keeps the top k with a small heap. Each group is independent, so it parallelises across as many machines as you like.

Why count distinct users, not just searches? A single bot or a determined prankster can search the same phrase thousands of times. Requiring that a query be searched by at least some number of distinct users before it can be suggested blocks most manipulation, and also stops one person's private search (for example their own name and address) from appearing for others.

Weighting with time decay

Raw all-time counts favour old queries. A query that was huge last year ("ipl 2025 schedule") would beat this week's interest forever. Time decay gives recent searches more weight. A common choice is exponential decay with a half-life H: a search that happened a days ago counts as 0.5^(a / H) of a search today.

score(query) = sum over days d of  count_d x 0.5^(age_d / H)

Worked example with H = 7 days.

• Query A had 1,000 searches 14 days ago and 100 today. 14 days is two half-lives, so the old searches count as 1,000 × 0.25 = 250. Score = 250 + 100 = 350.
• Query B had 400 searches today and none before. Score = 400.

By raw totals, A (1,100) beats B (400). With decay, B ranks above A, which matches what users care about now.

You do not need to rescan old logs every day. Exponential decay can be updated incrementally:

new_score = old_score x 0.5^(1/H) + today_count

With H = 7, the daily multiplier is 0.5^(1/7) ≈ 0.9057. So each day, multiply every stored score by about 0.906 and add today's count. As a check, a query with 100 searches every day for 7 days ends at about 530, not 700, because the earlier days have already decayed. Scores that decay below a threshold are dropped, which also keeps the candidate set bounded.

The half-life is a product choice. A short half-life (a day or two) makes suggestions react quickly but jump around; a long one (weeks) is stable but slow to notice change. Some systems blend both: a long-term score for stability plus the trending overlay for speed.

Rolling out a new snapshot

A bad build (a bug, a missing day of logs, a filter that failed) could replace every suggestion with garbage at once. Protect against it:

• Sanity checks before publishing: total entries within a few percent of yesterday's, top suggestions for a fixed list of test prefixes still present, blocklist test cases absent.
• Versioned snapshots kept for several days, so rolling back is loading yesterday's file.
• Gradual rollout: load on a few replicas first, compare metrics such as suggestion click rate, then the rest.

Deep dive 3: scaling reads with sharding, replication and caching

Do we even need to shard?

Our estimate put the index at at most about 20 GB. That fits in memory on a single large server, so the honest answer is: replicate for throughput first, shard only if the index outgrows one machine (more languages, more queries, larger k, or extra metadata per suggestion). Each replica holds the full index and answers lookups in microseconds; 104,000 requests per second spread across, say, 20 replicas is about 5,200 per replica, which is comfortable.

When you shard, how?

Range sharding by first characters. Shard 1 holds prefixes starting a to c, shard 2 d to f, and so on. It is intuitive and keeps a whole subtree on one shard (useful if you serve a real trie). The problem is skew: far more English queries start with s, c or p than with x or z, so equal-sized letter ranges give very uneven shards. The fix is to choose split points from the data: measure the size and traffic of each prefix range and cut where each shard gets a similar share, for example a, b, ca–ce, cf–cz, and so on.

naive by letter         data-driven split points
+----------+            +----------+
| a - h    | heavy      | a - b    |
+----------+            +----------+
| i - p    | heavy      | c        |
+----------+            +----------+
| q - z    | light      | d - h    |
+----------+            +----------+
                        | i - p    |
                        +----------+
                        | q - s    |
                        +----------+
                        | t - z    |
                        +----------+

Hash sharding on the full prefix. If you serve a prefix table, every prefix is independent, so you can place hash(prefix) mod N (or better, consistent hashing) on each shard. Load spreads evenly without hand-tuned split points. You lose the subtree locality, but the serving path never needs it: one request is one lookup for one prefix.

Hot prefixes. The shortest prefixes get the most traffic: every search passes through a one- or two-character prefix. They also make the worst suggestions (one letter says little about intent). Handle them by caching, not sharding: there are only 36 one-character and 1,296 two-character prefixes, so the API can hold them in local memory and the CDN can cache them almost permanently. Some products do not even call the server until two or three characters are typed.

Caching layers

Cache invalidation is easy here because the data only changes when a new snapshot is published. Include the snapshot version in the cache key, or simply let short time-to-lives expire. A suggestion that is a few minutes behind is harmless.

Personalised responses must not be cached publicly. If the response includes the user's own history, mark it Cache-Control: private (or better, fetch the personal part separately, from the client or from a different endpoint, and keep the global part fully cacheable). This split keeps the CDN hit rate high and avoids leaking one user's searches to another.

Deep dive 4: freshness, personalisation and filtering

Trending queries

A daily build misses a cricket score, an exam result or a news event that started an hour ago. To catch these, run a streaming job on the search log in Kafka: count queries over a sliding window (say, the last 30 minutes), compare with their usual rate, and flag queries whose rate jumped sharply. These go into a small trending overlay: a little prefix-to-queries map holding perhaps a few thousand entries, rebuilt every few minutes and pushed to the API servers.

At request time, the API merges the overlay with the main list. A simple merge rule: allow at most one or two trending items in the top 10, inserted at a position based on their strength. Trending candidates must pass the same filters as everything else, and often a stricter threshold, because fast-rising queries are exactly where hoaxes and abuse appear.

Personalisation

Your own recent searches are often the best suggestions for you. Two places to keep them:

• On the device: the app stores your last few dozen searches locally. Privacy-friendly and free, but not shared across devices.
• On the server: a small list per user in a key-value store. Works across devices, but it is personal data, so it must be deletable and never used for other users' suggestions.

A simple, explainable merge:

1. Take the user's recent searches that start with the prefix, most recent first, at most 2 or 3.
2. Fill the rest from the global list, skipping duplicates.
3. Mark personal items in the response ("source": "personal") so the client can show a clock icon and a "remove" option.

Richer personalisation (location, language, past categories) usually works by re-ranking a larger global candidate list, for example the top 50 for the prefix, with a lightweight model. Location is a common signal: "weather" completes to different cities in Chennai and Delhi. Doing that by keeping separate indexes per region or language is simpler than per-user models, and still cacheable per region.

Filtering offensive and harmful suggestions

An autocomplete suggests things nobody typed to this user, so the company is responsible for what appears. Filtering happens at several points:

1. At build time: remove queries matching a blocklist of offensive terms, slurs, adult terms (for general audiences), and queries that look like personal data (phone numbers, emails, ID-like numbers). Blocked queries never enter the snapshot.
2. Rules on combinations: a term may be fine alone but harmful next to a person's name or a group. Classifiers and rule lists catch patterns such as "[person] is [insult]".
3. At serve time: a final check against the latest blocklist, so a newly added term disappears in minutes, without waiting for the next build.
4. Thresholds: the minimum distinct-users rule from deep dive 2 stops coordinated attempts to push a phrase into suggestions.
5. Reporting: a "report inappropriate prediction" link feeds a review queue; reviewed terms go into the blocklist.

build:  logs --> normalise --> min users --> blocklist --> PII check
                                                      |
                                                      v
                                                  snapshot
serve:  snapshot + overlay + personal --> merge
                                           |
                                           v
                   client <-- latest blocklist check

Filtering does not change what the user may search for. If they type the full query and press Enter, search runs normally. Filtering only controls what we volunteer.

Scaling and bottlenecks

Latency budget. If the target is under 100 ms as seen by the user, most of that is network: the request travels from the phone to the nearest edge and on to a region. Lookup time inside the server is microseconds. That is why region placement and CDN caching move the needle far more than optimising the trie.

Failure handling

• A suggest replica dies: the load balancer stops sending it traffic; other replicas hold the same data.
• A whole shard is unavailable: return what other sources have (personal history, trending, cached), or an empty list. Search itself still works; the dropdown is a convenience.
• The daily build fails: keep serving yesterday's snapshot. Suggestions are a little stale, which is acceptable. Alert the owning team.
• A bad snapshot passes checks: roll back by loading the previous version; this is why snapshots are versioned and kept.
• The streaming job lags: trending overlay goes stale; the core suggestions are unaffected. Expire overlay entries automatically if not refreshed, so a stuck overlay cannot show yesterday's "trending" forever.
• Slow response arrives late: the client ignores responses for prefixes the user has already moved past.
• Offensive suggestion goes live: add it to the serve-time blocklist, which takes effect in minutes, then fix it at build time.

Trade-offs and alternatives

What interviewers probe

"Why not use a database index with LIKE 'prefix%'?" A B-tree index can find rows with a given prefix, but you then need the top 10 by score among possibly millions of matches, on every keystroke, at 100,000 requests per second. Precomputing the answer per prefix removes all of that work from the request path.

"How would you handle typos?" Add fuzzy matching as a separate step: when the exact prefix has few results, look up prefixes within a small edit distance (one insertion, deletion or substitution), or use a spelling-correction service that maps common misspellings to their intended query. Rank fuzzy matches below exact ones.

"How would you support matching words in the middle, such as 'python' matching 'learn python'?" Index each query under the prefixes of every word, not only the first, or use an inverted index of word prefixes. This multiplies the index size, so it is often limited to the most popular queries.

"How do you test whether a change improved suggestions?" A/B test. Compare metrics such as how often users pick a suggestion, how many characters they type before searching, and whether they reformulate. Changes to decay, filters or personalisation go through the same experiment process.

"What about non-English scripts?" The trie works on any characters, but normalisation matters: Unicode normalisation, case folding where it applies, and transliteration (users may type Hindi words in Latin script). Separate indexes per language or locale keep each one smaller and more relevant.

"How is this related to the search query cache?" Both serve popular queries from memory. The search query cache stores results for full queries; typeahead stores completions for prefixes. They share the same log pipeline.

Interview questions

Q1. What is a trie and why is it a good fit for autocomplete?

A trie is a tree where each edge is a character and each node represents a prefix. All completions of a prefix live in one subtree, so finding the prefix's node takes time proportional to the prefix length, regardless of how many queries exist. That maps directly onto "given what the user typed, find completions".

Q2. Why store the top-k suggestions at every node?

Without it, answering a short prefix means visiting and sorting a huge subtree on every keystroke. Because suggestions only change at build time, you can compute each node's top-k once, offline. Then a request is just a walk of p nodes plus returning k items.

Q3. Using scores cat 60, car 50, career 40, cart 30, what are the top 2 suggestions for "car"?

Under "car" the queries are car 50, career 40 and cart 30 ("cat" is not under "car"). The top 2 are car and career.

Q4. How do you build the suggestion data from logs?

Normalise and count submitted searches per query per day, merge counts into decayed scores, filter out rare, blocked and personal queries, then for each query emit every prefix with its score. Group by prefix and keep the top k. Write the result as versioned snapshot files that serving nodes load and swap in.

Q5. Why use time decay, and how does a half-life work?

Decay favours recent interest so old spikes fade. With a half-life of 7 days, a search from 7 days ago counts half as much as one today, and from 14 days ago a quarter. It can be updated incrementally by multiplying yesterday's scores by 0.5^(1/7), about 0.906, and adding today's counts.

Q6. How would you shard the index?

First check whether sharding is needed: our estimate fits in one machine's memory, so replication handles throughput. If sharding is needed, a flat prefix table can be hash-sharded on the full prefix for even load. If serving a real trie, use range shards with split points chosen from data to avoid skew towards popular letters.

Q7. Which caching layers would you use?

Client caching and debouncing to cut requests; a CDN for non-personal responses, especially short prefixes; an in-process cache of the hottest prefixes in the API; and the in-memory index itself. Because the index changes only at snapshot time, invalidation is simple.

Q8. How do you keep suggestions fresh for breaking news?

Run a streaming job over the search log that detects queries with a sudden rise in rate over the last few minutes. Put them in a small trending overlay that the API merges with the daily index, limited to a couple of slots and filtered strictly.

Q9. How would you personalise suggestions?

Merge the user's recent matching searches (from the device or a per-user store) at the top, then fill from the global list without duplicates. Use regional or language-specific indexes for broader context. Keep personal responses out of shared caches.

Q10. How do you prevent offensive suggestions?

Filter at build time with blocklists, combination rules and personal-data checks; require a minimum number of distinct users; apply a serve-time blocklist so new removals take effect in minutes; and let users report bad predictions. Filtering only affects what is suggested, not what can be searched.

Q11. What happens if the daily build fails or produces bad data?

Keep serving the previous snapshot, which is only slightly stale. Sanity checks before publishing catch most bad builds, and versioned snapshots allow instant rollback if one gets through.

Q12. Where does the latency go in a typeahead request?

Mostly into the network between the user and the server. The in-memory lookup takes microseconds. So the biggest wins are debouncing, client caching, CDN caching and serving from regions close to users.

Key takeaways

• Typeahead is latency-bound and read-heavy: about 100,000 requests per second, but an index of at most about 20 GB in our estimate.
• A trie organises completions by prefix; storing the top-k at every node makes lookups O(p + k).
• In practice you serve a flat, precomputed prefix-to-top-k table, which is easy to shard and cache.
• Build offline from submitted searches: normalise, count, decay, filter, explode to prefixes, keep top k, publish versioned snapshots.
• Exponential decay with a half-life keeps rankings current and can be updated incrementally.
• Replicate first; shard by hashing prefixes, or by data-driven ranges to avoid letter skew.
• Cache on the client, the CDN and the API; immutable snapshots make invalidation trivial.
• Add freshness with a trending overlay, personalisation by merging recent history, and filter at both build and serve time.

Next lesson

Review the interview playbook and practise these designs against the clock.