Search autocomplete system design interview: a worked guide

Ask whether the box completes a prefix, searches for terms that contain the input, or suggests full queries. Prefix completion is a narrower problem than general search. For this design, assume a public product-search box that returns up to eight query suggestions after the user types two characters. Results are scoped to a locale, with no personal history or account-specific ranking.

• Return useful suggestions before the user submits a search.
• Keep the response within an agreed interactive latency target, such as 100 ms at p95.
• Reflect new, removed, or blocked suggestions within a stated freshness window.
• Do not expose a rare or sensitive query because one person typed it.

Treat the latency and freshness numbers as interview assumptions. Ask the interviewer to change them before choosing a storage or update strategy.

Suppose 10 million people search each day, each makes eight searches, and the client sends five eligible prefixes per search. That gives 400 million suggestion requests per day, or about 4,600 requests per second on average. If peak traffic is five times the average, size the read path for about 23,000 requests per second. These are round interview inputs, not measured product traffic.

The result explains why the client should debounce keystrokes and stop requests for prefixes that are too short. It also gives a starting point for cache sizing. Next, ask how many distinct suggestions exist, how many are active in each locale, and how quickly popularity changes. Those answers drive index size and refresh work.

Keep typing requests off the pipeline that learns which suggestions are useful. The online path reads a versioned index. A separate batch or streaming pipeline validates candidate phrases, updates scores, and publishes a new index snapshot.

1. The browser normalizes the prefix, waits briefly for typing to pause, and sends the locale.
2. An edge or API layer checks request size, rate limits callers, and checks a cache for the prefix.
3. A suggestion service reads matching candidates from the locale's prefix index.
4. The ranker filters blocked candidates, orders the remaining suggestions, and returns at most eight.
5. A separate pipeline aggregates approved query activity and publishes index versions.

Cache by normalized prefix and locale. A short expiration keeps common prefixes cheap to serve, while index versioning lets every region switch to a complete snapshot instead of seeing a half-written update.

A trie or finite-state transducer fits exact prefix completion. It can keep a compact, read-optimized map from a prefix to likely completions. The serving path is predictable, but ranking, frequent updates, and multi-locale data need a deliberate design.

An inverted search index with edge n-grams or a search-as-you-type field fits richer matching, such as matching a prefix at the start of each word. It shifts more work to indexing and uses more index space. OpenSearch documents prefix matching, edge n-grams, search-as-you-type, and completion suggesters as separate approaches. Its completion suggester stores suggestions in a finite-state structure for prefix lookup. Read the OpenSearch autocomplete guide.

Redis sorted sets can also support a lexicographic prefix range when members share the same score. That gives a simple index for a bounded suggestion set, but returning candidates in popularity order requires a second ranking step. See the Redis lexicographical index pattern.

Start with a completion structure if the requirement is prefix-only and the candidate set is curated. Add an inverted index only if the prompt needs infix matching, typo tolerance, or richer filters. Do not choose a search cluster just because the feature contains the word search.

A simple score can combine recent query count and longer-term count. For example, use a weighted sum of the logarithms of each count, then apply explicit boosts for freshness and penalties for stale or low-quality phrases. The logarithm prevents a single extremely popular phrase from crowding out every alternative.

Normalize accents and case for matching, but keep the display text users expect. Filter by locale, policy, and product availability before ranking. If you add personalization, define its data source and deletion behavior separately. The base design should still work without it.

A daily batch update is simpler and makes the index easy to publish atomically. A streaming update reflects new trends sooner, but it adds ordering, deduplication, and rollback concerns. Choose the freshness target first. Keep a previous index snapshot available so a bad update can be rolled back.

A query typed by one person is not automatically a good suggestion for everyone. Aggregate counts before building the shared index, apply a minimum-volume threshold, and suppress phrases that may expose personal or sensitive information. Keep raw query retention short and separate it from account identity. The product's privacy policy should say what the pipeline stores.

Add a moderation path for slurs, spam, impersonation, and queries that point to unavailable products. A removal should invalidate cached results as well as the source index. Rate limits and a maximum prefix length also limit abuse and prevent large range scans.

Use the caching guide to reason about hot prefixes and stale results. Use the rate limiting guide to protect the API. Then run a timed system design mock interview and explain why the matching method fits the prompt.

This walkthrough is original practice material. Its example targets and architecture choices are assumptions to discuss in an interview, not claims about a named company's production system.