Design Search Autocomplete / Typeahead (Google Search Suggestions)

Search autocomplete looks like a data-structures question ("use a trie") wrapped in a system design question. The interviewer wants both halves. If you only say "trie", you have not designed a system; if you only draw boxes, you have not answered how suggestions are computed in a few milliseconds. The trick that connects them is precomputation: do all the expensive ranking offline, so the online path is a single memory lookup.

The same design powers Google search suggestions, Amazon and Flipkart product search boxes, YouTube search, and even the "search for a station" box on IRCTC. I will design the Google-style version and note where e-commerce differs.

Requirements

Functional

• As the user types, return up to 10 suggested completions for the current prefix, ranked by popularity (and later, relevance to the user).
• Suggestions reflect recent trends within minutes for breaking topics, and within a day for everything else.
• No offensive, illegal or personally identifying suggestions.
• Support multiple languages and scripts, including transliterated Hinglish queries.

Non-functional

• Latency: server p99 around 10–20 ms; suggestions should feel instant (the user types every 100–200 ms).
• Availability: high, but autocomplete is an enhancement. If it fails, search still works, so degrade silently.
• Consistency: eventual. Different users seeing slightly different suggestion freshness is fine.

Out of scope: the search results page itself (ranking documents is a different system; see inverted indexes and full-text search), spell correction (mentioned as an extension).

Capacity Estimation

Interview assumptions for a large search engine:

Index size as a prefix → top-k map: 1B prefixes × (10 suggestion IDs × 8 bytes + ~30 bytes key/overhead) ≈ 110 GB, plus a 100M-entry query-string table at ~40 bytes each ≈ 4 GB. Around 120 GB total. That fits in RAM on a handful of large machines, or across ~10 shards of 16 GB. If we cap prefix length at, say, 20 characters (longer prefixes are rare and can be answered from their 20-char ancestor), size drops further.

Serving fleet: an in-memory lookup is a few microseconds of CPU; a single server can handle tens of thousands of requests per second including network overhead. 1M/s ÷ ~25K/s per server ≈ 40 servers at peak, so ~80 with headroom and multiple regions. Small, because the design pushed the work offline.

The Latency Budget

Autocomplete is one of the few designs where you should allocate latency explicitly. On Indian mobile networks, round trip time to the nearest data centre is often 30–80 ms. That leaves very little for the server.

Client-side tricks

• Debounce keystrokes, and cancel in-flight requests for stale prefixes so responses never arrive out of order.
• Cache per prefix in the browser/app. Backspacing from "iphone 16" to "iphone 1" costs nothing.
• Local filtering: if the response for "ipho" had 10 results that all start with "iphon", the client can answer "iphon" locally while it fetches in the background.
• HTTP caching: responses for non-personalised prefixes carry Cache-Control: max-age=300, so browsers and CDNs absorb repeats.

API Design

GET /v1/suggest?q=ipho&lang=en&loc=IN-KA&limit=8
Headers: Cookie / Authorization (optional, for personalisation)

200 OK
Cache-Control: private, max-age=60
{
  "prefix": "ipho",
  "suggestions": [
    { "text": "iphone 16",          "type": "query" },
    { "text": "iphone 16 pro max",  "type": "query" },
    { "text": "iphone 15 price in india", "type": "query" },
    { "text": "iphone 16 pro",      "type": "query" }
  ]
}

Keep the response small (a few hundred bytes). Normalise the prefix on the server the same way the index was built: lowercase, trim, collapse spaces, Unicode NFC normalisation, so "iPhone " and "iphone" hit the same entry.

Deep Dive 1: The Trie with Top-K at Each Node

A plain trie answers "which strings start with this prefix?" but finding the most popular ones requires visiting the whole subtree: for the prefix "a" that is millions of nodes. The fix is to store, at every node, the top-k completions of its subtree, computed at build time. A lookup then walks L characters and returns a ready list.

Memory cost: k entries per node. With k = 10 and pointer-sized entries, this dominates the index size, which is why the estimate above was all about prefixes × k.

import heapq

class TrieNode:
    __slots__ = ("children", "top")
    def __init__(self):
        self.children = {}
        self.top = []            # list of (count, query), best first, len <= K

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

    def build(self, counts):
        """counts: dict query -> frequency (already aggregated offline)."""
        for query, freq in counts.items():
            node = self.root
            for ch in query:
                node = node.children.setdefault(ch, TrieNode())
                self._offer(node, freq, query)

    def _offer(self, node, freq, query):
        # keep the k best (count, query); ties broken alphabetically
        node.top.append((freq, query))
        node.top = heapq.nlargest(self.k, node.top, key=lambda t: (t[0], [-ord(c) for c in t[1]]))

    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]

counts = {"iphone 16": 900, "iphone 15": 700, "ipl score": 1200,
          "ipl 2026 schedule": 800, "ippb login": 300, "iphone 16 pro": 650}
t = AutocompleteTrie(k=3)
t.build(counts)
print(t.suggest("ip"))      # ['ipl score', 'iphone 16', 'ipl 2026 schedule']
print(t.suggest("iph"))     # ['iphone 16', 'iphone 15', 'iphone 16 pro']

Dry run for "ip": every query passes through nodes "i" and "ip", so the "ip" node sees all six. Sorted by count: ipl score (1200), iphone 16 (900), ipl 2026 schedule (800), iphone 15 (700)… With k = 3, it keeps the first three. For "iph" only the three iPhone queries pass through, ordered 900, 700, 650. The lookup touched three nodes; no subtree scan.

import java.util.*;

public final class AutocompleteTrie {
    private static final class Node {
        final Map<Character, Node> children = new HashMap<>();
        final List<String> top = new ArrayList<>();   // best first
    }

    private final Node root = new Node();
    private final int k;
    private final Map<String, Long> freq = new HashMap<>();
    private final Comparator<String> byRank;

    public AutocompleteTrie(int k) {
        this.k = k;
        this.byRank = Comparator.comparingLong((String q) -> freq.get(q)).reversed()
                                .thenComparing(Comparator.naturalOrder());
    }

    public void insert(String query, long count) {
        freq.merge(query, count, Long::sum);           // supports incremental updates
        Node node = root;
        for (char ch : query.toCharArray()) {
            node = node.children.computeIfAbsent(ch, c -> new Node());
            if (!node.top.contains(query)) node.top.add(query);
            node.top.sort(byRank);
            if (node.top.size() > k) node.top.remove(node.top.size() - 1);
        }
    }

    public List<String> suggest(String prefix) {
        Node node = root;
        for (char ch : prefix.toCharArray()) {
            node = node.children.get(ch);
            if (node == null) return List.of();
        }
        return List.copyOf(node.top);
    }

    public static void main(String[] args) {
        AutocompleteTrie t = new AutocompleteTrie(3);
        t.insert("ipl score", 1200);
        t.insert("iphone 16", 900);
        t.insert("ipl 2026 schedule", 800);
        t.insert("iphone 15", 700);
        System.out.println(t.suggest("ip"));   // [ipl score, iphone 16, ipl 2026 schedule]
    }
}

Complexity: lookup is O(L) for prefix length L. Build is O(total characters × k log k). The Java version supports incremental count increases (re-sorting at each node on the path), but note an important limitation: if a query's count decreases or a query falls out of one node's top-k and later climbs back, a simple incremental update can miss it, because nodes only remember their current top-k. That is one reason production systems rebuild the index from aggregated counts instead of mutating it in place.

Practical refinements

• Radix (compressed) trie: merge single-child chains ("iphone 1" stored as one edge) to cut node count and pointer overhead dramatically.
• Store IDs, not strings: top-k lists hold 4–8 byte query IDs pointing into one string table.
• Flatten for serving: serialise as a sorted array of prefixes or a hash map prefix → [ids] in a memory-mapped file. A map is often simpler to shard and to load than a pointer-based tree, and is what the capacity estimate assumed.
• Prefix length cap: stop materialising beyond ~20 characters.

For more trie practice, see trie interview problems; the top-k-per-node idea also mirrors heap-based top-k in heap and priority queue problems.

High-Level Architecture

The central property: the online path never touches a database. It reads an immutable in-memory snapshot plus two small, frequently refreshed overlays (trending and blocklist).

Deep Dive 2: The Offline Aggregation Pipeline

1. Collect. Every executed search (not every keystroke) is logged with timestamp, normalised query, locale and an anonymised user/session ID. Logs flow through Kafka into a data lake partitioned by hour.
2. Normalise. Lowercase, trim, Unicode normalise, strip trailing punctuation. Merge trivial variants so "IPL score" and "ipl score" count together.
3. Count with time decay. Popularity should favour recent interest. A common scheme: score = Σ count_day × 0.5^{(age_days / half_life)}, with a half-life of, say, 7 days. Last week's query matters half as much as today's.
4. Threshold and filter. Drop queries seen from fewer than N distinct users (protects privacy and removes junk), then apply blocklists and classifiers (next sections).
5. Build per locale. Suggestions differ by language and country; build separate indexes (en-IN, hi-IN, en-US) or tag entries with locale.
6. Build and validate the index. Generate the prefix → top-k map, run sanity checks (size within expected range, golden prefixes return expected results, no blocklisted terms), and write versioned snapshot files to object storage.
7. Deploy safely. Servers download the new version, load it alongside the old one, run health checks and atomically swap a pointer. Keep the previous version for instant rollback. Roll out region by region.

Deep Dive 3: Sharding the Trie

First question: do you need to shard at all? If the index for a locale fits in one machine's memory (with the capacity estimate above, 120 GB fits on a large instance), replicate the entire index to every server. Every request can go to any server; no routing logic, no hot shards. Shard only when the index outgrows memory or build/load times become painful.

Option A: range sharding by prefix

Split by leading characters: shard 1 serves a–c, shard 2 d–f, and so on. Simple routing, but English prefixes are badly skewed: far more queries start with "s" or "c" than "x" or "z". Fix it by using a traffic histogram to pick split points: shard 1 might be "a–am", shard 2 "an–b", while "x–z" share one shard. A routing table (in the load balancer or a thin router) maps prefix ranges to shard groups.

Option B: hash sharding the prefix map

If the index is a flat prefix → top-k map, shard by hash(prefix). Each lookup is still a single-shard read, load is even, and short and long prefixes land on different shards. The downside is that a client's consecutive requests ("i", "ip", "iph") hit different shards, which prevents shard-local caching tricks, but those rarely matter.

Hot prefixes

One- and two-character prefixes get enormous traffic and change slowly. Cache them at the CDN edge and in every server's local memory regardless of sharding; that removes most hot-shard risk. During events (an IPL final, a Budget day), trending queries concentrate on a few prefixes; the edge cache with short TTLs absorbs those too.

Deep Dive 4: Trending and Fresh Queries

A daily build is too slow for "earthquake delhi" or a new movie release. Add a streaming path:

• A Flink job counts queries over sliding windows (for example, last 15 minutes vs the same window last week) and flags queries whose ratio spikes beyond a threshold and whose absolute volume is meaningful.
• Flagged queries go through the same filters, then into a small trending overlay: a prefix → [trending queries] map pushed to serving nodes every minute or two.
• At serve time, merge the overlay into the snapshot's top-k with a boost, capped at one or two slots so trends do not crowd out stable suggestions.

This is the same streaming top-k problem as trending hashtags (count-min sketch plus heaps); see top-K trending hashtags system design for the internals.

Deep Dive 5: Personalization

Pure popularity is a good baseline, but a user in Chennai typing "wea" probably wants "weather chennai", and a developer who searched "kafka consumer lag" yesterday may want it again.

1. Fetch more candidates. Ask the index for the top 30 instead of top 10 (store k = 30 in the index if you plan to personalise).
2. Add user candidates. Pull the user's recent searches matching the prefix from a per-user store (a small KV list of recent queries, or keep it on the device entirely for privacy).
3. Re-rank with a cheap score: score = w1 × log(global_popularity) + w2 × user_history_match + w3 × locale_match + w4 × freshness. Weights come from offline experiments or a small learned model.
4. Return the top 8–10, deduplicated, with the user's own history items possibly labelled ("You searched…") and removable.

Location and language segmentation is often the biggest win in India. A query like "kaise" (Hindi transliterated in Latin script) should complete to Hinglish queries, while a Devanagari "कैसे" prefix needs its own index. Personalised responses must use Cache-Control: private so CDNs do not serve one user's suggestions to another.

Deep Dive 6: Filtering Suggestions

A bad suggestion is a reputational and sometimes legal problem: defamatory phrases attached to a person's name, sexual or violent content, private phone numbers, or completions that are illegal in a jurisdiction.

• Build-time filters: curated blocklists of terms and patterns, ML classifiers for hate and adult content, regexes for phone numbers, emails and Aadhaar-like 12-digit numbers, and minimum distinct-user thresholds so a handful of people cannot inject a suggestion by spamming searches.
• Serve-time blocklist: a small set of blocked query IDs and patterns pushed to every server within minutes. Applied after lookup and before returning, so takedowns do not wait for the next build.
• Context rules: stricter filtering for names of people and for SafeSearch-enabled users.
• Audit: log every removal reason to support appeals and legal requests.

How to Present Autocomplete in an Interview

1. Start with the latency budget and the read/write split. "Reads are a million per second and must be instant; data changes slowly. So precompute everything offline."
2. Explain the top-k trie and why plain tries are not enough. Sketch the node structure and give the complexity.
3. Draw the two paths: offline pipeline to immutable snapshots, online path to in-memory lookup.
4. Size it, then decide on sharding. Replicate if it fits; otherwise prefix-range with a histogram or hashed prefixes.
5. Close with freshness, personalisation and filtering.

Common follow-ups

• "Handle typos?" Fuzzy matching with edit distance over a small candidate set, or a spell-correction model that rewrites the prefix before lookup.
• "E-commerce autocomplete?" Rank by conversions and stock, not just query frequency; mix in categories and brands ("in Mobiles").
• "Mid-word matching ('pro max' finding 'iphone 16 pro max')?" That is an inverted index problem, closer to Elasticsearch's edge n-grams than to a trie.

Practise the estimation steps until they are automatic with back-of-the-envelope estimation; autocomplete is a question where the numbers directly decide the architecture.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.