Search Autocomplete System Design Interview: Tries, Ranking, and Low Latency

A search box can have a fast trie and still feel broken: its suggestions may be irrelevant, outdated, or replaced by a slower response for an earlier prefix. Search autocomplete system design interviews are about maintaining a useful ranked answer while requests, scores, and indexes change. Start with matching semantics, define what top-k means, and then allocate the latency budget.

Use PracHub's popularity-ranked autocomplete design question to rehearse that contract. The question records below are practice material, not predictions of your exact interview. Official engine documentation supports the named mechanisms in this guide; workload numbers and counterexamples are original exercises, not production benchmarks or candidate reports.

Define the suggestion contract before choosing a trie

Ask whether suggestions are query strings, products, people, or documents. A query-completion service might offer “camera lens” after “cam”; a product service may need inventory, locale, access permissions, and deduplication across several variants. Those requirements change both retrieval and ranking.

A trie is a tree whose edges represent characters or tokens. Following a prefix reaches the subtree containing its possible completions. Reaching that subtree does not by itself identify the best suggestions: the system still needs a ranking rule and an efficient way to select candidates.

Declare whether matching starts at the beginning of a string, at any token boundary, or anywhere within a field. Official Elasticsearch documentation distinguishes its search-as-you-type field, which supports prefix and infix completion, from its completion suggester, a fast navigational suggestion mechanism with an in-memory index. These are different contracts, not interchangeable names for a trie.

For an original interview baseline, return five public query strings for a normalized prefix, ranked by a fixed global score and deterministic lexical tie-break. Exclude personalized history initially. Specify a minimum prefix length, maximum input size, locale, and whether suggestions may lag accepted popularity events. This gives the design something precise to preserve.

Show why prefix lookup is only part of the cost

Following a trie prefix of length p takes O(p) traversal steps under an appropriate child lookup representation. Enumerating its entire subtree can visit many nodes and strings. The complete retrieval cost includes candidate collection, score evaluation, tie-breaking, deduplication, serialization, and any filtering.

One baseline stores the best k completions at each prefix node. Lookup then reads a bounded list after traversal. Storage grows because the same suggestion appears in multiple ancestor lists; use term IDs rather than copying every full string. A compressed trie or finite-state representation can reduce overhead, but its updates and ranking payloads still need an explicit design.

Explain the update cost rather than promising constant-time maintenance. A changed score can affect every prefix of a term. Increasing one term's score is often easier than decreasing the current winner: a short top-k list may lack the next replacement. Removing a banned term has the same missing-candidate problem.

A defensible baseline rebuilds an immutable ranked index from a durable event stream and periodically swaps a versioned snapshot. Incremental overlays serve urgent changes, while a denylist applies removals immediately. This is a proposed architecture, not a claim that every autocomplete engine uses it.

Trace the top-k counterexample

Consider three completions for “ca”: camera, camping, and cafe. Their global scores are 100, 90, and 80. A cached top-two list contains camera and camping. For one user, an additional history score gives cafe a bonus of 50, making its personalized score 130.

Reranking only the cached two candidates cannot return cafe. Increasing the ranking model's sophistication does not help when retrieval has discarded the winner. This original exercise separates candidate recall from ranking quality, an important follow-up when someone proposes machine learning after a fixed trie lookup.

One solution retrieves a larger global shortlist plus candidates from recent user history. Merge by stable suggestion ID, filter eligibility, and score the union. A larger shortlist improves coverage but gives no universal guarantee for arbitrary personalization bonuses. To claim exact top-k, provide a bound on the bonus and retrieve until unseen candidates cannot beat the current kth score, or evaluate every eligible candidate.

Also distinguish static ranking from time-dependent decay. If scores decay differently, the top list can change without a new event for that term. A periodic ranking refresh or a suitable dynamic structure is required. State which consistency approximation your service accepts.

Design partitioning around the query fan-out

Partitioning by suggestion ID balances storage, but a prefix query may need every shard. Each shard returns local candidates, and an aggregator merges them. Under the same total ordering and eligibility contract, each shard's local top-k is enough for a global top-k: an omitted item already has at least k better items in its own shard.

That argument fails when shards apply a different score or when later filtering removes candidates. If an aggregator deduplicates several aliases into one result, local k entries may contain fewer than k distinct usable suggestions. Request more candidates or keep fetching; do not silently present an approximate result as an exact one.

Partitioning by prefix narrows routing, but short popular prefixes create skew. A shallow prefix can represent a disproportionate fraction of requests and descendants. Replicate read-only snapshots, cache popular normalized prefixes, and route deeper branches separately when the distribution justifies it.

Virtual nodes balance ownership across many keys; they do not divide one hot prefix request by themselves. A replicated immutable index is attractive for read-heavy public suggestions, while personalized responses require keys that include the relevant context or an explicit uncached ranking step.

Allocate an end-to-end latency budget

For a teaching target, suppose the service aims for a 100 ms p99 response after receiving a request. Reserve time for routing, candidate retrieval, optional ranking, and response transmission. These numbers are assumptions to negotiate, not reported requirements from an employer.

Measure the entire path. A local trie benchmark excludes network distance, cold pages, shard queues, fan-out, garbage collection, and client rendering. With many shards, one slow shard can delay the final response. Put a deadline on each stage and decide whether partial results are acceptable.

A useful degraded mode returns a recent public prefix list when personalized ranking misses its deadline. Attach the index version and avoid mixing incompatible ranking snapshots if stable ordering matters. Falling back to an unfiltered public result is inappropriate when access permissions determine eligibility.

Bound work at the API: cap result count, prefix length, fuzzy expansions, and expensive optional features. A one-character fuzzy query can generate far more work than a longer exact prefix. Admission limits protect useful interactive traffic when an upstream caller sends pathological requests.

Prevent older responses from winning the screen

An original race starts with request 17 for “ca,” followed by request 18 for “cam.” Response 18 arrives first. Response 17 arrives later and overwrites the list, making the interface show results for text the user no longer has.

Debouncing reduces request volume but does not establish response order. Give each input generation a monotonically increasing local sequence number. Apply a response only if its generation and relevant context still match the current input. Clearing the input should also invalidate pending generations.

The official AbortController API can abort supported asynchronous operations such as fetch. Treat cancellation as resource control, while a generation check protects the visible result. An earlier request may already have completed or reached the server; cancellation does not prove that all upstream work disappeared.

Keep keyboard selection tied to the current result list. If an asynchronous refresh changes ordering while the user presses Enter, define whether selection follows the item ID or resets. This small client detail can turn a technically fast service into a confusing product.

Update popularity without publishing private history

Aggregate accepted query events into counts or another declared score. Deduplicate event IDs where retries would inflate popularity, record event time and ingestion time, and define how late arrivals affect windows. A daily snapshot plus recent delta needs a boundary that prevents counting the same events twice.

Raw keystrokes can contain sensitive or unfinished text. An interview design should explain data minimization, retention, and the difference between public aggregate suggestions and private account history. Do not promote every rare submitted string into a public index.

Use a moderation path for removals and poisoning attempts. A popularity-only score can reward automated submissions; rate controls and eligibility filters belong before public publication. An urgent removal should invalidate caches and overlays as well as the next full snapshot.

When normalization changes, rebuild and version the index. Case folding, accents, tokenization, and Unicode handling can change prefix behavior. Keep display strings separate from lookup keys so normalization does not corrupt the text shown to users.

Evaluate useful answers and operational failure together

Track candidate recall against a reference retrieval set, ranking quality for the chosen task, and successful search outcomes. Click-through alone is affected by placement and feedback loops: putting a suggestion first can increase clicks and then reinforce its popularity.

Operational measures should include p50 and p99 latency, timeouts, empty suggestions, index age, rejected updates, and moderation propagation delay. Segment by prefix length, language, traffic concentration, and personalized versus public requests. A good average can hide a slow popular prefix or missing suggestions for one locale.

An original acceptance test sends overlapping input generations, reorders their responses, then changes the locale and clears the search field. No response from the earlier context should reappear. A separate index test decreases the top score and verifies that the correct replacement enters the list.

Explain which tests run against a complete reference implementation and which merely exercise a proposed interface. Passing a local generation-order test does not establish production ranking relevance or a real p99 latency target.

Practise the matching and ranking follow-ups

For each prompt, write the matching contract first, then state the source of truth for scores and the acceptable freshness lag. Draw one race or counterexample before adding infrastructure. This gives your answer a reason for each cache, index, deadline, and update stream.

Finish with the popularity-ranked prefix suggestion exercise. Explain how you would change it for personalized results without discarding a possible winner during retrieval. If you can identify where an exact result becomes an approximation, you are prepared for a more useful system design discussion.

Sources and Further Reading

• Elasticsearch: Completion, term, and phrase suggesters
• Elasticsearch: Search-as-you-type field
• MDN: AbortController

Primary references checked September 30, 2026. Verify analyzer and API behavior against the engine and client versions in your exercise.