Design a typeahead service

01Define what a suggestion means

Design a service that suggests up to ten approved search terms while a person types. The request “ca” can match “cat,” “capital,” “captain,” “caption” and “cap.” Rank matching terms by recent submitted-search popularity, with deterministic ties. Suggestions should arrive quickly enough to remain useful while typing; use an illustrative 200 ms end-to-end target.

Choose exact prefix matching for the first design. Typo correction, arbitrary substring search and semantic similarity need additional candidate generators. A prefix index does not acquire those capabilities because it has more replicas. Require at least two characters, bound input length and keep ordinary search submission usable when suggestions fail.

The public vocabulary is approved separately from private search history. Index and query processing share one documented Unicode normalization and locale-aware case policy while preserving display spelling. This prevents predictable mismatches between stored terms and input; it is not a complete defense against visually confusing characters.

Use hourly popularity updates. Urgent blocked-term removal uses a current serving-time policy check, independent of the hourly index. This worked design does not promise a worldwide removal deadline or control words already displayed on an offline browser; those stronger contracts belong in a later discussion.

Clarify exact-prefix versus typo-tolerant matching, the ranking signal, acceptable popularity delay and the behavior during policy-service failure. The following contract chooses exact prefixes and safe empty suggestions when current approval cannot be established.

02Functional requirements

Agree on these supported actions before selecting components.

1. Return ranked prefix matches. Given at least two input characters and a locale, return up to ten approved matching terms ordered by recent submitted-search popularity and deterministic ties.

2. Handle changing input. Use compatible normalization in indexing and queries, preserve display spelling and render only responses belonging to the search box’s current input sequence.

3. Update popularity and policy. Ingest identified submitted-search events, rebuild popularity snapshots and remove blocked terms from final candidate results.

4. Keep ordinary search usable. Return fewer or no suggestions when necessary without preventing query submission. Private history, when present, remains user-scoped rather than entering a public response cache.

03Non-functional requirements

Use these as illustrative interview assumptions to agree with the interviewer. Numerical targets require measurement; they are not claims about an existing product or a proven implementation. p95 (the 95th percentile) means 95% of measured operations finish within the stated time.

1. Workload and memory. Plan for approximately 1.16 million suggestion requests/s at the fivefold peak. The illustrative 40 GB snapshot may need 80 GB during replacement before process reserve; validate these assumptions with representative builds.

2. Response latency. Target p95 end-to-end suggestion latency of 200 ms after the browser sends a request on the declared regional client/network profile at admitted peak load. Debounce waiting before send is measured separately, not hidden inside server time.

3. Ranking freshness. Publish popularity snapshots hourly from a fixed input cutoff using the selected ten-day count window. Delayed or failed builds retain the previous validated snapshot and expose its age.

4. Coherent and rebuildable state. A query uses one complete snapshot version. Durable vocabulary and count inputs survive a process restart or one database-node failure; serving indexes can be rebuilt and hot ranges replicated.

5. Current approval and privacy. Check final candidates against current policy after all cache and index sources. If that check fails, return no suggestions. Do not promise a worldwide removal deadline or recall of words already displayed.

6. Bounded request cost. Limit input length, candidates, shard fanout and retained raw events. Candidate ranking must remain meaningful under abuse controls rather than letting repeated malicious submissions dominate counts.

04Find and rank five words by hand

A trie is a tree in which following successive character edges locates a prefix. Traversing c, then a, reaches the subtree containing the five example words. A terminal marker identifies a complete term: cap is both a valid word and the start of capital, captain and caption.

Build this small index from a durable vocabulary and counts. At query time, traverse the prefix, enumerate descendant terminal terms, sort them by popularity and return the first ten.

For cap, cat does not match and must disappear regardless of its higher score.

The browser waits for a short pause in typing before sending a request; this is debouncing. Give each input change an increasing request sequence. If ca is request 12 and cap is request 13, only the response matching the current sequence may update the screen. Canceling request 12 can save work, but it cannot guarantee that an already completed response will not arrive.

This baseline works with one application and one in-memory index rebuilt from durable data. A database prefix query would also work for a small vocabulary. The reason to evolve the trie is measurable query work, not that databases are intrinsically unsuitable for suggestions.

05Budget the index, not only its strings

Assume five billion submitted searches/day. If each submission generates four suggestion requests after debounce, the serving average is approximately 231,481 requests/s, with a fivefold peak near 1.16 million/s. Counting submitted searches alone understates the load.

A broad prefix may match millions of words. Traversing its few characters is cheap; enumerating and sorting every match is not. Extra replicas repeat that expensive work. Precomputing a bounded shortlist at each prefix trades memory and update effort for predictable serving cost.

The node count and snapshot size are assumptions to benchmark, not deductions from vocabulary bytes. Compression can reduce chains of single-child nodes, and compact arrays can reduce pointer overhead. Plan peak loading memory as well as steady-state memory: a machine that holds one snapshot may fail when asked to stage its replacement.

06Tie the response to input and index versions

The request identifies the typed prefix, locale and current browser input sequence. The response returns that sequence, the normalized prefix, the index version and a bounded list of term IDs with display text.

Suggestion request

GET /v1/suggest?prefix=ca&locale=en-US&limit=10&requestSeq=12

Illustrative response for the five running terms

{
  "requestSeq": 12,
  "normalizedPrefix": "ca",
  "indexVersion": "snapshot-42",
  "terms": [
    {"termId": "t-cat", "displayText": "cat"},
    {"termId": "t-capital", "displayText": "capital"},
    {"termId": "t-captain", "displayText": "captain"},
    {"termId": "t-caption", "displayText": "caption"},
    {"termId": "t-cap", "displayText": "cap"}
  ]
}

The example IDs identify the five terms; internal scores need not be exposed.

Do not count every typed prefix as a successful search. Otherwise “cap” accumulates popularity merely because people continue typing “capital.” Choose submitted searches as this design’s score input, deduplicate repeated event IDs over the processing window and bound contributions from abusive clients.

Return fewer than ten results when matching or approved candidates are insufficient. An empty suggestion list is a valid degradation, while the search box remains usable. Render display text safely rather than interpreting it as markup. The browser discards a response for an old input even if the server used the newest index; input freshness and ranking freshness solve different problems.

07Store enough information to rebuild the shortlist

Durable records supply the vocabulary and popularity evidence used to generate the serving trie.

The serving trie must not be the only copy of vocabulary or popularity evidence.

Each node stores transitions, an optional terminal term and a bounded candidate list containing term IDs and scores. Store display strings once in a term table rather than repeating full strings at every prefix. A compressed edge can consume several characters; when a query ends inside a matching compressed edge, its candidates still come from that subtree.

Choose a ten-day sliding window of submitted-search counts, aggregated into hourly buckets. A score is the sum of the included buckets under the build’s fixed cutoff. Older buckets expire, so scores can decrease. This is different from exponential decay, which gradually changes older events’ weights; do not mix those definitions in one unexplained formula.

Public cache keys include normalized prefix, locale and index version. Private history is stored separately by authenticated user. If personalization is added, merge a bounded personal candidate source after retrieving public candidates, then apply the same policy checks. Never put the resulting private response into a cache shared by other users.

08Precompute winners without forgetting excluded terms

Build each prefix’s top ten from its own complete term and its child prefixes’ top tens. Why is that enough? A term excluded from a child’s top ten already has ten better matches. Those same matches qualify for the shorter parent prefix, so the excluded term cannot win there either. This requires the same global score and tie-breaker everywhere.

The serving shortlist alone is insufficient for future updates. Consider k = 2 under cap:

The original shortlist is capital, captain. After the decrease, the correct answer is captain, caption. Lowering capital’s score inside the old pair would never discover caption.

Therefore build from complete retained terms and counts, recomputing child and parent lists bottom-up. Building separately avoids changing scores and prefix shortlists while queries read them. The online request then traverses the prefix and reads a bounded prepared list instead of sorting a huge subtree.

The top-k argument assumes global independent scores. Arbitrary personalization or diversity rules can change which excluded terms become useful. That extension needs a larger candidate pool or separate personal candidates and an explicit recall tradeoff.

09Publish coherent snapshots and route prefixes

Queries reuse precomputed rankings while popularity changes accumulate. Build a separate read-only index hourly from a fixed vocabulary/count cutoff. Check representative prefixes, checksums, ranking and memory size before directing queries to it. Serving requests retain one index version until they finish; new requests can switch to the replacement while older readers finish on the previous version.

If both versions do not fit on one machine, stage new hosts and shift traffic after readiness checks. Do not solve a loading-memory shortage by freeing data still used by active requests. Keep the previous artifact for rollback and retain durable inputs for rebuilding.

Partition large indexes by measured lexical ranges, meaning contiguous portions of the normalized term ordering. A prefix can intersect more than one range, so a router asks the relevant shards and merges their bounded candidates. Every shard response uses the request’s pinned snapshot version. Hashing complete terms spreads storage but scatters prefix matches, usually requiring every shard or a separate prefix-routing index.

Equal first-letter shards are rarely balanced. Split large ranges and replicate hot ranges according to measured memory and traffic. Splitting unrelated data does not reduce requests for the exact same hot prefix; replicate its serving work and cache its public candidates. Keep candidate limits and shard fanout bounded so a broad query cannot overwhelm the cluster.

Store the source vocabulary, count buckets and published snapshot metadata with durable majority commits across three replicas in independent regional failure domains. That meets the chosen one-node-loss boundary only if failover preserves acknowledged inputs. Snapshot-serving replicas remain replaceable; keeping ordinary search available is the fallback when suggestions cannot be served safely.

10Filter removals after every candidate source

Hourly ranking freshness is acceptable here, but a removed term should not survive simply because it remains in an old snapshot. Before returning suggestions, the API checks the final candidate IDs against current policy state. This includes candidates from caches and private history. If the policy check is unavailable, return no suggestions rather than assume an old allowed decision remains valid.

Choose this request-time check for the worked design. Its extra dependency and latency must be budgeted; a separate replicated policy service can batch the small list of candidate IDs. Faster distributed policy caches with bounded freshness are an Advanced alternative, because an explicit removal deadline also needs a clock, expiry and client-display contract.

Filtering can leave a short list. Precompute a modest larger pool if measurements show that approved results are frequently lost, but do not perform an unbounded subtree scan or refill afterward from an unfiltered source. Increasing the pool costs memory at every retained prefix.

Private history adds another boundary: logout and history deletion must clear user-scoped cached data. Public popularity counts should not expose raw personal search logs. Prefixes can contain secrets or pasted identifiers, so minimize logging and restrict retained raw data.

11Keep search usable while suggestions recover

If a snapshot build fails, continue serving the previous validated index with current policy checks. If loading exceeds memory or fails its checksum, that replica remains unready. A pointer to a partially loaded artifact must not reach request routing.

Popularity aggregation must tolerate repeated events. One simple implementation recomputes each completed hourly bucket from a fixed input-log range, deduplicating event IDs before publishing that bucket. Replaying the build produces the same counts instead of incrementing them again. Event retention bounds how far back reconstruction is possible.

When a hot-prefix replica fails, spare replicas and shared public candidate caches absorb traffic within measured capacity. Admission limits preserve service health. Suggestion failure should leave normal query submission available; it should not freeze the input box waiting for retries.

Monitor end-to-end latency, empty-result rate, response-discard rate, snapshot age, load-time peak memory and policy-check failures. Evaluate relevance on held-out prefixes as well as clicks, since click volume can reward sensational suggestions. Apply contribution limits and detect sudden suspicious popularity spikes before they dominate the next build.

12Check the design against the requirements

Use the agreed lists to check the finished design. The tests below still need to establish the targets; a proposed mechanism is not a measured result. FR refers to the numbered functional requirements above; NFR refers to the numbered non-functional requirements.

13Rapid revision

Remember: Precompute rankings to reuse them across queries; replace the whole snapshot so readers never see half-updated shortlists.

Close by following ca: the browser numbers its input, the server reads one index version and checks its candidate list, then the browser displays the response only if ca is still current. Explain that serving speed came from moving work into index construction, not from ignoring ranking correctness. The next measurements are peak snapshot memory, hot-prefix load and useful suggestion quality. Personalization, typo correction and hard removal deadlines can then be discussed as specific extensions with additional requirements.

Recall the key ideas

Answer from memory before opening each card. Explain why the choice works and what it costs. Revisit missed cards tomorrow.