Search Autocomplete
Return fast prefix suggestions that combine a stable vocabulary with recent trending queries while controlling abuse and freshness.
Return fast prefix suggestions that combine a stable vocabulary with recent trending queries while controlling abuse and freshness. This worked design targets SDE-2; the scale figures below are exercise assumptions, not claims about a named company's implementation.
Clarify the prompt
| Ask the interviewer | Decision to record |
|---|---|
| Global or personalized suggestions, and which locales? | They change cache keys and privacy. |
| What does trending mean: last hour, growth rate or raw popularity? | Define event windows. |
| Can harmful or private queries appear? | Filtering and deletion are part of serving, not only training. |
Requirements and scope
The core deliverable is: Return fast prefix suggestions that combine a stable vocabulary with recent trending queries while controlling abuse and freshness. The first design implements the APIs below and the state constraints in the data model. Agree the latency, freshness, retention and failure policy before adding infrastructure. Every successful acknowledgment must have an explicit meaning: accepted intent, committed state or completed external work. These are separate milestones.
Capacity and bottleneck reasoning
Assume 20 million users type ten searches/day with six keystroke requests each: 1.2 billion requests/day, about 13,900/s average and 70,000/s peak. At ten 40-byte results, peak payload is about 28 MB/s before protocol overhead.
Keep average and peak demand separate. Add replication, indexes, retries and safety headroom to raw arithmetic before selecting capacity. Load-test the busiest ownership key and recovery traffic as well as uniform happy-path throughput.
APIs and data model
- GET /suggest?q=rest&locale=en&limit=10 -> suggestions,version
- POST /search-events {eventId,query,eventTime} -> accepted event
- POST /moderation/suggestions/{hash}/suppress -> policy version
query_event(event_id, normalized_query, locale, event_time, actor_bucket)
prefix_snapshot(version, locale, prefix -> top_candidates)
trending(window,locale,prefix,candidate,count); policy_tombstone(query_hash,version)Authorize resource ownership at the API boundary; do not trust IDs or state supplied by a client. Bind retry identity to the caller and payload for mutating operations. Reject an incompatible replay instead of returning an unrelated stored result.
Component relationships
Read the diagram
Follow the labeled relationship panels; they are separate directed paths, not one global timeline.
Step-by-step design
1. Establish the authority
Normalize Unicode and locale consistently, then debounce and cancel obsolete client requests. Serve bounded top-K candidates from a prefix index or finite-state/trie snapshot; cache popular prefixes by locale and permitted personalization scope.
2. Make retries and concurrent work safe
Build a stable snapshot offline. Separately deduplicate search events and maintain bounded event-time trending windows, with a documented late-event policy and per-actor contribution caps. Merge baseline and trending candidates using a versioned scoring rule.
3. Scale and recover the critical path
Publish snapshots atomically through a version pointer. Apply suppression filters after merging so a fast trend cannot bypass policy. If trending processing fails, serve the last stable snapshot with its age rather than block typing.
Worked request and concurrency example
For prefix "res", baseline scores favor "restaurant" while a new event makes "results" trend in the last hour. The serving tier merges bounded candidates, applies locale and safety filters, and returns ten items. An older response for "re" arrives after "res"; the browser discards it using a request sequence. A duplicated query event contributes once, and late events outside the admitted window do not rewrite already closed windows.
Failure and recovery walkthrough
A bot repeats one query to manipulate trends. Cap contributions by actor and time bucket, apply anomaly checks and keep a suppressible candidate identity. A new snapshot with bad ranking is rolled back by switching the version pointer.
Read the diagram
This numbered trace follows one scenario; explain the durable evidence at each transition.
Decisions and alternatives
| Decision | Trade-off |
|---|---|
| Alternative 1 | A trie with stored top-K makes prefix lookup cheap but uses memory and requires snapshot rebuilds. A search index is flexible but has query and refresh overhead. |
| Alternative 2 | Personalization improves relevance but fragments caches and can leak query history. Start with locale-scoped global suggestions and add user features only under a clear policy. |
Operational contract
Track p95 suggestion latency, snapshot age, event-time watermark lag, cache hit rate, empty-result rate and suppressed-query leakage. Canary new snapshots by locale and compare latency and relevance before widening rollout.
Choose alert thresholds from the agreed user-facing objective. Assign an owner for stuck work and a replay/repair procedure that preserves the original business identity. Bound queue depth, concurrency and recovery throughput so an outage does not produce an uncontrolled catch-up burst.
Foundation, senior and staff depth
- Foundation: explain the user action, model, first complete request and the correctness constraint without relying on a list of technologies.
- Senior: defend this lesson's partition/coordination boundary, capacity estimate and failure recovery; explain the cost of the rejected alternative.
- Staff: identify failure domains and operational ownership, stage a rollout with measured guardrails, and state when rollback stops being safe.
Practice before revealing the answer
Spend 45 minutes: 5 clarifying scope, 7 on capacity/APIs/state, 12 on the first architecture, 15 on the concurrency and failure examples, and 6 on trade-offs and operations. Draw your own design before comparing it with this chapter.
Question: How do you keep trending fresh without rebuilding the entire trie every second?
Show answer and explanation
Answer: Use a small independently updated overlay for recent candidates, merge it with the stable snapshot at serving time and bound candidate counts. Measure overlay age and safely fall back to the baseline.
Verification and rollout
Reproduce the worked example using two concurrent actors or a repeated request where applicable. Inject the stated failure between the durable transition and its acknowledgment; verify the resulting state and user-visible outcome. For read/ML paths, test missing or stale dependencies and verify the documented fallback still enforces permissions. Use a small canary, compare correctness and user-facing latency with the baseline, and roll back when those guardrails regress. Do not use an average throughput number as evidence that a tail-latency target is met.
Primary technical reference
Official documentation for the mechanism used in this exercise. This lesson is an original interview design, not a description of undisclosed company internals.
Related study
Before this design, review these mechanisms and identify which owns the critical state transition:
Use the Interview Playbook to adapt the depth and timing, then return to the question breakdown overview.