Design a Search Autocomplete: System Design Interview Guide

Search autocomplete is one of the most common system design interview questions because it looks simple on the surface but hides real depth: data structures, ranking, scale, and latency all collide in one feature. This guide walks through how to approach the problem the way a strong candidate would in a 45-minute interview.

Clarifying the Problem

Before writing anything, spend two to three minutes clarifying scope. A typical prompt is: “Design a search autocomplete system, similar to Google Search or Amazon’s product search bar, that suggests queries as a user types.”

Key questions to ask the interviewer:

• Are we suggesting full queries (like Google) or entity names (like a product catalog)?
• How many queries per second (QPS) do we need to support?
• What latency budget do we have per keystroke? (Usually under 100ms.)
• Do suggestions need to be personalized, or is a global ranking acceptable for v1?
• How fresh does the data need to be? Minutes, hours, or a day is fine?

Most interviewers want you to design for something like 10 million distinct queries in the corpus, 500 million searches per day, and sub-100ms p99 latency for suggestions.

Core Requirements

Functional requirements:

• As a user types a prefix, return the top 5-10 matching suggestions.
• Suggestions should be ranked by relevance, typically popularity/frequency.
• Support fuzzy or typo-tolerant matching (nice-to-have, mention it, defer implementation detail).

Non-functional requirements:

• Low latency: sub-100ms end to end.
• High availability: this is a user-facing feature; degrading gracefully (returning empty or cached results) beats an outage.
• Scalability: the system should handle spiky traffic (trending queries).

The Trie: Why It’s the Default Data Structure

The trie (prefix tree) is the textbook answer for prefix matching, and for good reason. Each node represents a character, and a path from root to node represents a prefix. Once you’re at the node for the user’s typed prefix, every subtree in that node contains all completions.

Walking down a trie for a prefix of length k takes O(k) time, independent of how many total strings are stored. That’s the entire pitch: lookups don’t get slower as your corpus grows, only as the query gets longer.

But a naive trie doesn’t rank anything. It just tells you the set of valid completions. You need to augment it:

• Store top-N suggestions at each node. As you insert a string into the trie, propagate its frequency score up to every prefix node along the insertion path, and keep a small heap (e.g., top 10) of the highest-frequency completions at each node. This turns an O(subtree size) query into an O(k) lookup.
• Memory tradeoff. Storing top-N at every node multiplies memory usage. For 10M queries, this is usually still manageable (a few GB), but it’s worth mentioning the tradeoff explicitly to show you understand it.

An alternative some candidates propose is an inverted index over n-grams, but the trie is almost always the expected answer because it maps cleanly onto the “typing a prefix” mental model.

Ranking by Frequency

Naive frequency counting has two problems interviewers expect you to catch:

1. Stale popularity. A query that was popular last year but has died off shouldn’t outrank a query trending this week. The fix is a time-decayed score, something like score = frequency * decay_factor^(days_since_last_seen), recomputed periodically rather than in real time.
2. Personalization gap. Global frequency ranking ignores the individual user. A common answer is a two-stage design: serve a fast, globally-ranked list from the trie, then re-rank the top 20 candidates using a lightweight personalization signal (user’s own search history, location) at the application layer. This keeps the hot path fast while still improving relevance.

Real-Time Suggestions and the Data Pipeline

The tricky part interviewers probe for is: how do new/trending queries get into the trie without rebuilding the whole structure on every search?

The standard answer is a two-tier system:

• Offline/batch layer: aggregates raw query logs (from a stream like Kafka) every 5-15 minutes, computes frequency counts, and builds a new trie snapshot.
• Online layer: serves the current trie snapshot from memory, swapping in the new snapshot when it’s ready (blue-green style, so there’s no downtime during the swap).

For queries that need to appear within seconds (breaking news, flash sales), some designs add a small “hot updates” overlay: a lightweight in-memory structure that captures very recent spikes and merges its results with the main trie’s results at query time, then gets folded into the next batch rebuild.

System Architecture at a Glance

A typical high-level flow: client sends prefix on each keystroke, hits an API gateway, which fans out to a trie-serving fleet behind a load balancer. Each server holds a full copy of the trie in memory (since 10M queries with top-N caching still fits comfortably in RAM on a modern server). Query logs stream asynchronously to the aggregation pipeline, which rebuilds and redistributes trie snapshots.

Comparison of Design Approaches

Common Interview Pitfalls

• Jumping straight to “use a trie” without discussing tradeoffs. Interviewers want to hear why, and what breaks at scale.
• Ignoring the write path. Many candidates only design the read (query) path and forget how new data enters the system. This is usually where the interview earns or loses points.
• Not discussing caching. A CDN or edge cache for the most common prefixes (single letters, top brand names) meaningfully reduces load on the trie-serving fleet.
• Forgetting fault tolerance. If a trie-serving node goes down, what happens? Multiple replicas behind a load balancer with health checks is the expected answer.

Sample Interview Script

When asked to design this system, a strong answer flows roughly like this: clarify scope and scale, state functional and non-functional requirements, propose the trie as the core data structure with top-N caching per node, explain the batch aggregation pipeline for frequency updates, address personalization as an optional re-ranking layer, and close with a discussion of caching, replication, and fault tolerance. That’s a complete, interview-ready structure that respects the clock.

Further Reading

For more structured practice on this exact category of question and dozens of others, The 0-to-1 SWE Interview Playbook (Amazon: https://www.amazon.com/dp/B0H256Z1MF?tag=sirjohnnymai-20) walks through a repeatable framework for tackling any system design prompt from a blank whiteboard, with worked examples across search, messaging, and streaming systems.

Autocomplete is a great question to master early in your prep, because the trie-plus-ranking pattern reappears in variations across many other prompts: typeahead for usernames, product search, and even spell-check systems. Once you’ve internalized the pattern here, you’ll recognize it everywhere.