Prompt and Applicable Context
Design the backend service that returns the top 10 query suggestions for a typed prefix. Assume 50 million daily active users, 10 searches per user per day, five suggestion requests per search, a 150,000-request-per-second peak, a 50 ms p99 latency target, a 15-minute popularity refresh target, and a one-minute policy-removal target.
These are interview assumptions, not measured production facts. The base design serves anonymous, locale-specific popularity suggestions. The browser component, spell correction, semantic completion, and per-user personalization are outside the initial scope. The service must not expose rare or disallowed queries merely because they appear in logs.
This is a system-design problem because the core work spans event ingestion, ranking, immutable index construction, online serving, cache and shard behavior, and safe publication. A frontend autocomplete component can consume this API, while a Trie is only one possible local index representation.
What the Interviewer Evaluates
A strong answer first separates the write-heavy learning path from the read-heavy serving path. Scanning raw logs or sorting candidates on every keystroke cannot meet a tight tail-latency target. Aggregation, eligibility checks, moderation, and most ranking should happen before requests arrive; the online path performs a bounded prefix lookup and returns a small list.
The second signal is quantitative reasoning. The daily assumptions imply 2.5 billion requests: 50 million times 10 times five. That is about 28,900 requests per second on average, so the stated 150,000 peak is roughly a fivefold peak factor. At an estimated 1 KB response, the peak response payload is about 150 MB/s before protocol overhead and replication. These calculations drive replication, cache, and load-test targets; they do not pretend to size memory without measuring the encoded index.
The third signal is publication correctness. A partially built or inconsistently routed index can return missing or differently ranked results. Strong candidates build a versioned immutable artifact, validate it, load it alongside the old version, atomically activate routing, and retain the previous good version for rollback.
Finally, popularity is not the same as eligibility. Search logs can contain personal data, manipulation, and harmful text. Minimum-frequency thresholds, retention controls, anti-abuse signals, moderation before publication, and a faster emergency deny path are part of correctness.
Questions to Clarify Before Answering
- What does a suggestion represent? Query completions, product entities, and navigation destinations need different candidate sources and ranking features. The base design returns complete query strings.
- Which matches are required? Prefix-only lookup permits a compact ordered prefix index. Infix, fuzzy, or semantic matching adds candidate generators and makes the online budget harder to bound.
- How fresh must each change be? Popularity can tolerate the assumed 15 minutes; policy removals need one minute. This leads to a versioned base index plus an independently refreshed deny layer.
- Are results global or personalized? Global results can be heavily cached. Personalization reduces cache sharing and adds consent, deletion, and feature-fetch latency. It is excluded initially.
- How are locale and normalization defined? Case folding, script, accents, and word boundaries differ by locale. Index and query must use the same versioned normalization policy.
- What happens for empty and one-character prefixes? They are extremely hot and can reveal broad trends. The base system returns a curated locale list for empty input and a precomputed list for one character.
- What are the safety and privacy requirements? They determine log retention, aggregation thresholds, reviewer workflow, regional storage, and whether a candidate may ever enter the index.
30-Second Answer Framework
“I would split the system into an offline build path and a bounded online lookup path. Search events enter a stream, are normalized and aggregated by locale and time window, then pass frequency, abuse, privacy, and moderation gates. A ranking job writes the top candidates into a versioned prefix index. After validation, serving replicas load the immutable version and routing switches atomically. Online requests normalize the prefix, check a hot-prefix cache, route to the locale and prefix shard, apply the fast deny layer, and return ten results. I would size from the 150,000 peak, split hot prefixes when needed, keep the previous index for rollback, and measure p99 latency, coverage, safety recall, stale-version rate, and ranking quality.”
Step-by-Step Deep Dive
Step 1: Derive the budget and contract
Use a small idempotent read API:
GET /v1/suggestions?prefix=iph&locale=en-US&limit=10
200 {
"suggestions": [
{ "text": "iphone charger", "id": "q_7f2" }
],
"indexVersion": "2026-07-19T17:30Z"
}Clamp limit, cap the normalized prefix length, reject unsupported locales, and never accept ranking weights from the client. The stable opaque ID supports analytics without treating display text as an identifier. indexVersion makes stale or mixed-version responses observable.
The 2.5-billion daily calculation gives about 28,900 average QPS. The supplied 150,000 peak is the capacity target. If one response is approximately 1 KB, serving 150 MB/s requires regional replicas and compressed transport. Cache capacity and index RAM still require production samples: serialize representative artifacts, measure bytes per prefix and top-K entry, then add replication and headroom. Multiplying a guessed Trie-node size by candidate count would produce false precision.
Step 2: Build candidates without publishing raw logs
Clients emit a completed-search event with query ID, normalized locale, coarse context, timestamp, outcome signals, and a short-lived privacy-preserving actor key used only for bounded aggregation. The ingestion service validates schema and drops obvious bots before an append-only stream. Windowed aggregation computes distinct-actor counts and quality signals; raw user identifiers never become part of a suggestion key.
The candidate pipeline applies a minimum distinct-user threshold, rate and abuse controls, privacy and retention rules, and policy classification. It then ranks eligible candidates using a documented combination of popularity, recency decay, result quality, and editorial rules. Exact weights are learned and tested; they are not universal constants. Keep rejected candidates and reasons in a restricted audit store, not in the serving index.
Ranking from observed clicks can reinforce whatever was already displayed. Use offline relevance judgments and guarded experiments alongside engagement, and monitor suggestion coverage, no-result rate, complaints, and exposure concentration. Moderation belongs before the index build because automated log-derived suggestions can reproduce harmful or biased text.
Step 3: Materialize a bounded prefix index
For each eligible suggestion, generate prefixes under the same locale-aware normalization used online. Store only a bounded top list per prefix—for example, the best 20 candidates when the API returns 10—so lookup and filtering remain bounded. The extra candidates permit deduplication and emergency removals without walking a subtree.
A Trie or finite-state transducer can represent shared prefixes; an ordered key-value table keyed by locale plus prefix is operationally simpler and may compress well. Choose after benchmarking artifact size, build time, lookup p99, and update workflow. Elasticsearch’s completion suggester illustrates the same trade-off: fast prefix lookup uses an in-memory structure that is costly to build, and weights and contexts influence ranking and filtering.
Base scope is exact prefix completion. Fuzzy completion is a separate generator because edit-distance expansion changes recall, CPU cost, and safety analysis. It should not silently share the same latency promise.
Step 4: Publish immutable versions safely
Each build has an input watermark, normalization version, ranker version, policy version, checksum, and creation time. Validation checks schema, candidate counts, prohibited test phrases, locale isolation, deterministic tie-breaking, lookup samples, artifact size, and latency on a loaded replica.
Replicas load the new immutable index beside the active one. A health report confirms its checksum and representative queries. The control plane then atomically changes the active version for a shard group. During rollout, requests stay pinned to one version; mixed results are measured. Keep the prior good version until the new version passes a canary window, then roll back routing if latency, safety, or coverage regresses.
A failed or late build does not replace a healthy index. Freshness is an SLO, not permission to publish an invalid artifact.
Step 5: Keep the online path short
The request passes rate limiting, normalization, locale resolution, and an exact hot-prefix cache. A router selects the prefix shard and replica. The replica performs one index lookup, removes entries in the fast deny set, deduplicates stable IDs, and returns the first 10. No raw-log query, distributed aggregation, or full sort belongs on this path.
Cache keys include locale, normalized prefix, limit, policy version, and active index version. This prevents an old ranking or policy response from surviving activation. Empty and one-character prefixes are precomputed separately because their traffic and candidate sets are unusually broad. Negative caching can protect nonexistent prefixes, but its TTL must not hide newly eligible suggestions beyond the freshness target.
Step 6: Shard for locality and hot prefixes
Partition first by locale, then by a prefix range or hash of the first few normalized characters. Range partitions preserve locality but create hot shards; pure hashing balances load but may require extra routing metadata. A practical router owns a versioned map from prefix range to shard and can split a hot range such as a single popular first character without rebuilding unrelated ranges.
Replicate each shard across failure domains and route to a healthy local replica. Record per-prefix QPS, cache hit rate, shard CPU, lookup p99, and index bytes. Adding replicas solves read load; splitting or isolating a hot range solves skew. If a shard is unavailable, return a cached version with an explicit freshness metric or an empty list—never suggestions from another locale.
Step 7: Meet two freshness clocks
The base index rebuilds every 15 minutes. A small recent-trend overlay can aggregate a shorter window and merge a bounded set with base candidates, but it must pass the same privacy and safety gates. If that overlay fails, serve the last good base index rather than make the whole endpoint unavailable.
Policy removals use a separately distributed deny set with a one-minute target. Serving replicas filter denied IDs after lookup, and cache keys include its version. The next base build removes them permanently. This two-clock design avoids rebuilding a large artifact for an emergency removal while preserving deterministic base publication.
Step 8: Validate ranking, safety, and operations
Load tests replay the observed prefix-length and locale distribution at 150,000 peak QPS, including hot one-character prefixes, cold-cache startup, replica loss, and version activation. Assert p99 under 50 ms at the service boundary, bounded error rate, no mixed checksums per response, and recovery without a thundering herd.
Offline evaluation covers top-K relevance, coverage, duplicate rate, locale correctness, prohibited-content recall, and stability between versions. Online experiments use search completion and downstream result quality with guardrails for no-result rate, latency, complaints, and exposure concentration. A higher click rate alone is insufficient because display position affects clicks.
Operational drills include a poisoned event batch, failed build, oversized artifact, hot shard, stale deny set, partial replica rollout, and ranker regression. Every alert should map to a safe action: hold activation, fall back to the last good version, isolate the overlay, split the range, or activate the emergency deny rule.
High-Quality Sample Answer
“I would start with anonymous, locale-specific prefix completion and ten results. From 50 million users, ten searches, and five requests per search, I get 2.5 billion requests per day, about 28,900 average QPS. I would capacity-plan for the stated 150,000 peak and measure serialized index size instead of guessing Trie memory.
The data path and serving path are separate. Completed-search events enter a stream. Aggregation produces distinct-user counts, recency and result-quality signals. Candidates pass minimum-frequency, abuse, privacy, and moderation gates before a ranker writes a bounded top list per normalized prefix. Every artifact records its data watermark, normalization, ranker, and policy versions.
Serving replicas hold immutable index versions. They load and validate a new version beside the old one, then routing switches atomically and can roll back. A request normalizes prefix and locale, checks a versioned cache, routes to the prefix shard, performs one lookup, applies the fast deny set, and returns ten. Hot one-character ranges get dedicated cache and can be split independently.
The base rebuild meets the 15-minute target. A small, gated trend overlay may improve recency, while emergency removals use a one-minute deny layer; either can fail without corrupting the last good base. I would test the actual prefix distribution at 150,000 QPS and track p99, freshness, cache hit rate, shard skew, relevance, locale leakage, safety recall, and rollback time.”
Common Mistakes
- Querying and sorting raw logs on every keystroke → work grows with history and makes tail latency unpredictable → precompute bounded top-K lists and keep online lookup constant-bounded.
- Calling the data structure “a Trie” and stopping → this omits ranking, publication, sharding, safety, and recovery → describe both build and serving lifecycles and benchmark representations.
- Estimating RAM from an invented node size → encoding and prefix sharing determine real bytes → serialize representative data and measure artifact size and lookup latency.
- Caching only by prefix → locales, policy, and index versions leak or preserve wrong results → put every result-affecting version in the key.
- Publishing in place → readers observe partial or mixed data → build immutable artifacts, validate, load side by side, and atomically activate.
- Using popularity as the only eligibility rule → rare personal, manipulated, or harmful text can surface → apply distinct-user thresholds, anti-abuse, privacy, and moderation gates.
- Rebuilding everything for emergency removal → the safety deadline depends on a large batch job → distribute a fast deny layer and remove permanently in the next base build.
- Treating click-through rate as unbiased relevance → displayed rank influences clicks → combine guarded experiments with offline judgments and safety metrics.
Follow-Up Questions and Responses
Follow-up 1: How would you add fuzzy matching?
Keep exact prefix lookup as the first, cheap generator. Trigger fuzzy generation only after a minimum length or when exact coverage is low, cap edit distance and candidate count, and merge through one ranker and moderation policy. Benchmark Unicode-aware distance and adversarial inputs because fuzzy expansion increases CPU and can retrieve policy-sensitive variants.
Follow-up 2: How would you add personalization?
Blend a small authorized personal candidate set after retrieving global candidates. The cache remains global up to that boundary; final responses become user-scoped and should not enter a shared cache. Define consent, retention, deletion, sensitive-query exclusions, feature timeouts, and a global-only fallback before adding ranking features.
Follow-up 3: What if one locale no longer fits in memory?
Split its prefix ranges using measured bytes and QPS, then update the versioned routing map. Keep top-level hot prefixes on dedicated replicas and allow cold ranges to use a memory-mapped or remote index if their p99 still meets the budget. Rebalance by artifact version so readers never depend on an in-place key migration.
Follow-up 4: How would you support breaking news within seconds?
Do not shorten the whole base build blindly. Add a tightly bounded streaming overlay with trusted candidate sources, a high eligibility threshold, immediate moderation, TTL, and a kill switch. Merge it with base results under a fixed candidate budget. If its freshness or policy watermark is stale, discard the overlay and serve the last good base.
Follow-up 5: How do you delete a query after a privacy request?
Remove or tombstone eligible raw events and aggregates according to the data model, add the suggestion ID to the fast deny layer, invalidate affected cache entries through the policy version, and rebuild the base artifact from corrected inputs. Audit the propagation time across regions without logging the sensitive text again.