Design Typeahead: Autocomplete System Design Interview 2026

Autocomplete system design is the interview problem of returning the top few query completions for a typed prefix, usually within about 100 milliseconds end to end, for millions of users. The standard answer precomputes the top-k suggestions for every popular prefix offline, stores them in memory (as a trie or a flat prefix-to-list table), and serves them through a cached, replicated read path. A separate pipeline aggregates query logs and pushes fresh rankings, including trending queries, without touching the hot path.

This guide walks through the answer the way a strong candidate would present it in a 45-minute round, and adds the piece most write-ups skip: a direct comparison of the three storage approaches you can choose from, with the latency math behind each.

Key Takeaways

• Precompute everything. Ranking at request time cannot fit a 10 to 20 ms server budget at high QPS, so store the top-k list per prefix offline.
• A trie is the right whiteboard explanation, but a flat prefix-to-top-k key-value table is often the better production answer because it is simpler to shard, cache, and rebuild.
• Split freshness into two layers: a batch rebuild for the base index and a streaming overlay for trending queries, merged at read time.
• Most traffic comes from short, repeated prefixes. Client debouncing plus edge caching removes a large share of requests before they reach your servers.
• Shard by prefix range with traffic-aware split points, not by first letter, or you will build hot shards on day one.

What Are the Requirements for an Autocomplete System?

Start by pinning down scope, because "design Google search autocomplete" can mean anything from a 5-minute data structure question to a full ranking platform. Ask these questions out loud, and write the answers down.

Functional requirements:

• Return the top 5 to 10 completions for a prefix, ranked mostly by popularity.
• Support only prefix matching (not fuzzy or mid-word matching) unless the interviewer asks.
• Reflect new popular queries within hours, and breaking trends within minutes.
• Filter offensive, unsafe, or legally sensitive suggestions.
• Optional: personalization, multiple languages, and location-aware ranking.

Non-functional requirements:

• Very low latency, since suggestions must appear between keystrokes.
• High availability. A broken autocomplete degrades search but should never block it, so fail open to "no suggestions."
• Read-heavy traffic. Reads outnumber index writes by many orders of magnitude.
• Eventual consistency is fine. Nobody notices if a suggestion's rank is an hour stale.

Back-of-envelope estimates

Use round, stated assumptions. Interviewers care about the reasoning, not the exact figures.

The punchline: the whole index fits in RAM on a handful of large machines. That single fact shapes every later decision.

The latency budget

Suggestions feel instant at roughly 100 ms, a rule of thumb from usability research that interviewers expect you to know. Here is where that time goes:

Once you show this table, it becomes obvious why there is no room for a database query or a scoring pass over millions of rows per keystroke.

How Does a Trie Store Top-K Suggestions?

A trie (prefix tree) is a tree where each edge adds one character, so every node represents a prefix and every path from the root spells a query. Finding all completions of "goo" means walking three nodes and then exploring the subtree below them.

The naive version is too slow. Exploring the subtree for a short prefix like "s" touches millions of nodes. The fix is to cache the top-k completions directly on every node during the offline build, so a lookup is O(length of prefix) plus O(k) to read the list.

import heapq

class TrieNode:
    __slots__ = ("children", "top_k")

    def __init__(self):
        self.children = {}
        self.top_k = []

class AutocompleteTrie:
    def __init__(self, k=10):
        self.root = TrieNode()
        self.k = k

    def build(self, query_scores):
        for query, score in query_scores.items():
            node = self.root
            for ch in query:
                node = node.children.setdefault(ch, TrieNode())
                self._offer(node, query, score)

    def _offer(self, node, query, score):
        if len(node.top_k) < self.k:
            heapq.heappush(node.top_k, (score, query))
        elif score > node.top_k[0][0]:
            heapq.heapreplace(node.top_k, (score, query))

    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 sorted(node.top_k, reverse=True)]

Each node keeps a size-k min-heap during the build, so inserting a query costs O(L log k) for a query of length L. In an interview, mention the trade-off you just made: you spent memory (k entries per node) to buy constant-time reads. If the heap pattern is rusty, the coding interview patterns cheat sheet covers both tries and top-k heaps.

Two refinements show depth:

• Store query IDs, not strings, in the top-k lists. Strings live once in a dictionary, which cuts memory sharply.
• Cap indexed prefix length (for example 20 to 30 characters). Very long prefixes are rare and can fall back to a slower path.

Trie vs Precomputed Top-K Table vs Search Engine

This is the decision most top-ranking articles skip. There are three realistic ways to store and serve suggestions, and the right one depends on scale, team, and how flexible matching needs to be.

1. In-memory trie with cached top-k. A custom service loads a serialized trie into each server's memory. Lookups are pointer walks.

2. Precomputed prefix table. The offline job emits rows of prefix -> [top-k query IDs] and loads them into a key-value store or an in-process hash map. Conceptually this is the trie flattened: you keep only the nodes' cached lists and drop the tree structure.

3. Search engine suggester. Use a search engine's built-in completion feature. Elasticsearch's completion suggester, per Elastic's documentation, is backed by an in-memory data structure (a finite state transducer) built at index time for fast prefix lookups. An alternative is edge n-gram tokenization with a normal query.

Scored for a large consumer search box (5 = best):

These scores are a framework for discussion, not a benchmark. The recommended interview narrative: explain the trie first, because it shows you understand the structure, then say you would serve production traffic from the flattened prefix table, and reach for a search engine if the product needs typo tolerance or matching inside words, such as an e-commerce catalog.

How Does the Data Collection and Aggregation Pipeline Work?

Suggestions are only as good as the counts behind them. The pipeline turns raw search logs into a ranked, filtered, versioned index, entirely offline.

1. Log. Every completed search (not every keystroke) emits an event: normalized query, timestamp, locale, coarse location, and an anonymized user key.
2. Ingest. Events flow into a durable log such as Kafka, which decouples the search frontend from downstream jobs.
3. Aggregate. A batch job (Spark or similar) groups by normalized query and locale and computes a time-decayed score.
4. Filter. Drop queries below a minimum count, queries with personal data, and anything matching safety blocklists and classifiers.
5. Build. Generate prefix-to-top-k tables per locale, sorted and serialized.
6. Publish. Write the versioned artifact to object storage, then roll it out to serving nodes gradually.

The scoring function is where you show judgment. Raw all-time counts let stale queries dominate forever, so use exponential decay:

import math

def decayed_score(daily_counts, half_life_days=7.0):
    decay = math.log(2) / half_life_days
    return sum(count * math.exp(-decay * age_days)
               for age_days, count in daily_counts)

A 7-day half-life means last week's searches count half as much as today's. Tune it per product: news search wants a short half-life, while a developer docs site can use months.

The filtering step matters more than candidates expect. Google's help page on how autocomplete predictions work says its systems aim to block predictions that are violent, sexually explicit, hateful, disparaging, or dangerous, and that enforcement teams remove violations the automated systems miss. Naming a blocklist, a classifier, and a manual takedown path signals real-world awareness. You can read Google's description in How Google autocomplete predictions work.

Serving Layer and Caching

The read path is short by design: client, CDN or edge, load balancer, stateless suggestion servers holding the index in memory, then a response.

Client side. Debounce keystrokes (around 50 to 150 ms is common), skip requests for empty or one-character prefixes if product allows, cancel in-flight requests when the user keeps typing, and cache responses in the browser. If the user types "pyt" and the cached "py" response already contains only "python..." entries, the client can filter locally. Front-end specialists get grilled on exactly this; see the frontend engineer interview guide.

API design. Keep it a simple GET so it caches well:

GET /v1/suggest?q=syst&locale=en-US&limit=8

{
  "prefix": "syst",
  "version": "2026-10-01T06:00Z",
  "suggestions": ["system design interview", "system of a down", "systemctl restart"]
}

Returning the index version helps debugging and lets clients discard out-of-order responses.

Edge caching. Short prefixes are a tiny keyspace with enormous traffic. Caching non-personalized responses at the CDN with a time-to-live of a few minutes absorbs a large share of load. The distributed cache system design article covers eviction and invalidation trade-offs you can borrow here.

Index swaps. Servers load a new index version into memory alongside the old one, run health checks, then flip a pointer atomically. Roll out to a canary slice first and compare click-through on suggestions before going wide. Keep the previous version on disk for instant rollback.

Protection. A suggest endpoint is cheap per call but extremely high volume, which makes it an abuse target for scrapers. Per-client limits, discussed in the rate limiter system design guide, keep one bad actor from eating your capacity.

Personalization and Trending Queries

Both features add freshness or context on top of the base index. Treat them as overlays merged at read time rather than separate systems, so the hot path stays a single in-memory lookup plus a small merge.

Trending queries

A daily batch rebuild cannot react to a breaking news event. Add a streaming layer:

1. A stream processor such as Flink reads the same search event log.
2. It counts queries in short tumbling windows (for example 5 minutes) per locale.
3. A query is "trending" when its recent rate exceeds its historical baseline by a large ratio and passes a minimum volume threshold.
4. Trending entries pass through the same safety filters, then publish to a small overlay store (thousands of entries, not millions).
5. At request time, the server fetches base top-k for the prefix, pulls any overlay entries that match the prefix, and merges by score with a trending boost.

The trending layer is also the riskiest, because unverified rumors spike fastest. Google's help page also describes holding back predictions in fast-moving situations where reliable content is scarce. A stricter safety threshold for trending entries than for base entries is a sensible answer.

Personalization

Personalization is a re-ranking step. Fetch the global candidates plus a handful from the user's recent searches that match the prefix, then re-score with signals such as history, language, and location. Two consequences worth stating:

• Personalized responses cannot be cached at the shared edge, so personalize only after the first few characters, or merge history on the client.
• Store per-user history in a low-latency key-value store with a strict retention window, and let users clear it.

How Do You Shard and Scale Autocomplete?

If the index fits in one machine's memory, the simplest design is full replication: every server holds the entire index, and you scale reads by adding replicas behind the load balancer. Say this first. Many candidates jump to sharding when it is not needed.

When the index outgrows one node (many locales, long-tail queries, larger k), shard it:

• By first character: easy to explain, but traffic is badly skewed across letters, so some shards run hot.
• By prefix range with traffic-aware split points: the build job measures request volume per prefix range and picks boundaries so each shard gets similar load. A routing table maps prefix ranges to shards.
• By hash of the full prefix: spreads load evenly, and since each prefix's top-k list is self-contained, lookups still touch exactly one shard.

Hash-by-prefix pairs naturally with the flat table approach, which is one more reason it often wins in production. Shard by locale first if you serve many languages, since each locale's index is independent.

For multi-region deployment, ship the same versioned artifact to every region and serve locally. There are no cross-region writes on the hot path, so this is one of the easier systems to run globally.

Follow-Up Questions Interviewers Ask

Expect two or three of these after the core design. Short, structured answers work best.

• Typo tolerance? Add an edit-distance or FST-based fuzzy layer, or move to a search engine suggester. Note the latency cost.
• Infix matching ("design" matching "system design")? Index each word position as an extra entry pointing to the full query, or use n-gram analysis in a search engine.
• Multiple languages and scripts? Normalize with Unicode rules, build per-locale indexes, and handle input methods where the typed characters are not the final script.
• How do you measure quality? Suggestion click-through rate, keystrokes saved, and the share of searches that started from a suggestion. Run A/B tests on ranking changes.
• Cold start for a new product? Seed from a curated list, document titles, or product catalog names until real query logs accumulate.
• What if the suggest service fails? Fail open: the search box works without suggestions, and clients time out quickly.

Similar read-heavy, precompute-first thinking shows up in the news feed system design problem, and the logging pipeline resembles the one in the web crawler system design walkthrough. For pacing the 45 minutes, follow the framework in how to ace the system design interview, and rehearse this exact prompt with the drills in how to practice system design interviews. If you are targeting Google specifically, typeahead is a natural fit for its loop, covered in the Google technical interview process.

A 45-Minute Answer Plan

Use this time split so you reach the interesting trade-offs before the clock runs out:

Practice saying the comparison between the three storage approaches in under two minutes. It is the moment that most clearly separates a memorized answer from an engineer who has thought about running the system.