Technologies referenced in this case study: Redis · Elasticsearch · Kafka · Flink

Related case studies: Search Indexing · CDN & Edge Caching · Distributed Caching · Leaderboards & Counting · Stream Processing

How to Use This Case Study#

Organized for interview use first, reference second. Full-text retrieval, inverted indexes and relevance scoring live in Search Indexing; this case study is about answering a prefix in under 100ms, millions of times a second, without ever suggesting something you'll regret.

Without a safety design:
t=0:      A coordinated group searches "<public figure> is a <slur>" 40K times
t=+1h:    Hourly pipeline promotes it into the top-5 for "<public figure> is"
t=+1h:    Prefix tables rebuilt and pushed to all serving nodes
t=+3h:    Screenshot trends on social media
t=+4h:    Engineer manually edits the blocklist file; full rebuild needed
t=+6h:    Rebuild + rollout completes. Press coverage already written.

With a safety design:
t=0:      Same coordinated burst
t=+1h:    Pipeline requires ≥N distinct users over ≥M days; burst fails threshold
t=+1h:    Velocity anomaly flags the pattern for trust-and-safety review
t=+20min: (If anything slipped through) T&S adds a serving-time override
t=+21min: Override propagates to all nodes and edge caches purge — no rebuild

Executive Summary

If you only read one section, read this. Typeahead is a read-optimized precomputation problem with a safety obligation attached.

What This Interview Actually Tests#

Typeahead is not a trie question. Everyone can draw a trie.

This is a latency-budget and precomputation question that tests:

• Whether you derive the design from a per-keystroke budget (~100ms end to end, ~10–20ms server)
• Whether you move work from query time to build time — and know what that costs in freshness
• Whether you place caching at every layer (client, edge, server) and know which layer absorbs what share of traffic
• Whether you treat suggestions as published content with safety, legal and privacy obligations

The key insight: every suggestion is something your product said to the user before they asked. Staff engineers design typeahead as a publishing pipeline — build offline, review, publish versioned, override instantly — with a serving tier that is just a fast lookup.

The L5 → L6 → L7 Contrast — Start Here#

The Staff Positions#

The Three Intents#

🎯 Staff Move: "I'll design query completion for the main search box — that's where the QPS, the caching and the safety risk live. Entity typeahead reuses the serving tier with a per-user candidate set merged in, and I'll show where that plugs in."

The Five Fault Lines#

In the Wild: Real Production Systems#

Why this section belongs here: Typeahead is a well-documented problem with public engineering write-ups. Citing them shows you know the hard parts are latency and safety, not tries.

Facebook — Typeahead for people and pages#

Facebook's engineering blog post "The life of a typeahead query" (2010) described a design that pre-loads a user's first-degree connections and frequently-used entities to the browser, so many queries are answered client-side before any request is sent. Server-side, queries fan out to a global index of entities and a per-user graph index, results are merged and ranked by social signals, all within a tight budget measured in tens of milliseconds.

Staff insight: The fastest request is the one you don't make. Pushing a per-user candidate set to the client is a caching decision driven by the latency budget — and it's the canonical example of personalization as a merge, not a separate global index.

LinkedIn — Cleo#

LinkedIn open-sourced Cleo (2012), a typeahead library used for its search boxes. It partitions a large entity set, uses compact per-element prefix signatures (Bloom-filter style) to cheaply reject non-matching candidates, and then scores the survivors — supporting both "network" (personal connections) and "generic" (global) typeahead.

Staff insight: Separating a cheap candidate filter from an expensive scorer is the same move as top-K precomputation: bound the work per keystroke so latency doesn't depend on corpus size.

Google — Autocomplete policies#

Google publishes autocomplete policies describing categories of predictions it removes (e.g., sexually explicit, hateful, violent, dangerous content, and certain predictions about individuals), and gives users a way to report predictions. Removals are driven by automated systems plus enforcement teams.

Staff insight: At scale, suggestion safety is a published policy with an enforcement pipeline, not a word list. In an interview, naming the policy owner and the removal path is a stronger signal than any data structure.

Elasticsearch — Completion suggester#

Elasticsearch's completion suggester builds an in-memory FST per segment for prefix lookups, trading index-time cost and immutability for very fast reads. It supports weights and contexts (e.g., category or geo filters) but not arbitrary ranking at query time.

Staff insight: Even a general-purpose search engine ships a precomputed, immutable structure for autocomplete — because query-time full-text search can't meet the per-keystroke budget.

What Interviewers Probe#

System Architecture Overview#

Reading the diagram: The client and edge absorb most keystrokes. The serving tier is a dumb, fast lookup over an in-memory snapshot plus a small trending overlay, filtered through an override list on every response. All ranking, privacy filtering and policy classification happen offline in the build pipeline. Trust & Safety has a direct path to the override filter and the CDN purge — removals never wait for a rebuild.

Quick-Reference: The 30-Second Cheat Sheet#

Key Numbers Worth Memorizing#

Interview Walkthrough

The most common mistake: Candidates spend 20 minutes on trie node layouts and memory per pointer, then run out of time before latency budgets, caching layers, freshness and safety — which is where the level is decided. The phases below get the data structure done in 5 minutes.

Phase 1: Requirements & Framing (2–3 min)#

Functional requirements in 30 seconds:

"As the user types into the search box, return up to 10 ranked completions for the current prefix, per keystroke."

Then the framing that matters:

"There are three typeahead problems hiding here — query completion, entity lookup for people and pages, and in-app command completion — and they rank and cache differently. I'll design query completion for the main search box and show where personalization plugs in."

Then commit to numbers:

"I'll assume 5B searches a day, ~6 suggest requests per search after debouncing — about 350K requests/s average and 1M/s peak. Budget: 100ms from keystroke to rendered list, so the server gets 10–20ms p99. Suggestions must never include policy-violating or private queries, and removals must propagate within minutes."

🎯 Staff Move: Putting "removals must propagate within minutes" in the requirements tells the interviewer you see suggestions as published content. It also sets up the override layer, which is the piece most candidates never design.

Phase 2: Core Entities & API (1–2 min)#

• Suggestion: text, score, source (base / trending / personal), entity_ref?
• PrefixEntry: (locale, normalized_prefix) → [top-K suggestion ids + scores]
• IndexSnapshot: version, locale, built_at, policy_version, checksum
• Override: match (exact / prefix+completion / entity / regex), action (deny / demote), reason, owner, expires_at

Serve path:

GET /v1/suggest?q=how+to+t&locale=en-US&client=web&session=…
200 OK  Cache-Control: public, max-age=300   (if non-personalized)
{ "q": "how to t", "suggestions": [ {"text":"how to tie a tie","src":"base"}, … ],
  "index_version": "en-US-2026-10-01T03", "personalized": false }

Override path (T&S, cold):

POST /v1/overrides { match: {type:"pair", prefix:"<name> is", completion:"<term>"},
                     action:"deny", reason:"policy:harassment", ticket:"TNS-4411" }

🎯 Staff Move: "The response says whether it's personalized. Non-personalized responses are public-cacheable at the edge; personalized ones are private. That single bit decides whether a keystroke costs us a CDN hit or an origin request."

Phase 3: High-Level Architecture (≤5 min)#

"Reads are a lookup in an in-memory prefix table — one hash get per request. All ranking happens in the offline build. Trending is a small overlay merged at serve time. Overrides are applied to every response. Client and edge caches take most of the traffic."

Phase 4: Transition to Depth#

"The lookup is the easy part. The design lives in four places: the per-keystroke latency budget and caching layers, how fresh suggestions get without letting brigades publish themselves, how personalization coexists with caching, and the safety pipeline. I'll start with the latency budget because it drives everything else."

Phase 5: Deep Dives (25–30 min)#

Phase 6: Wrap-Up (2–3 min)#

"To summarize: a read-only, in-memory prefix table built offline, served from replicated nodes behind client and edge caches, with a trending overlay for freshness and a serving-time override layer for safety. The server budget is 10–20ms and most keystrokes never reach it. Next I'd add per-locale tokenization for CJK and IME input, typo-tolerant fallback for long prefixes that miss the table, and an experimentation framework for ranking. What I wouldn't build on day one is a real-time mutable trie — the freshness it buys isn't worth the safety and operational risk."

Common Timing Mistakes#

1. The Staff Lens#

1.1 Why This Problem Exists in Staff Interviews#

Typeahead is deceptively small. The functional spec is one sentence, and the textbook data structure takes five minutes. That leaves 40 minutes in which the interviewer learns whether you can reason from a latency budget, move work from read time to build time, cache at the right layers, and own something that is effectively a publishing system: every suggestion is a sentence your company says to millions of people, unprompted.

It also has an unusual shape: extreme read QPS (often the single highest-QPS endpoint in a search product), a tiny response, a mostly-static dataset, and a small but critical write path (overrides) that must propagate faster than anything else in the system.

1.2 The L5 → L6 → L7 Contrast — Visual#

The L5 path produces a working autocomplete. The gap is that its first incident — a brigade, a court order, a hot prefix, a Japanese launch — has no designed answer.

1.3 The Staff Question That Cuts Through Everything#

"If a suggestion has to disappear right now, how long does it take, and who can make it happen?"

If the answer is "a rebuild, a few hours, an engineer", the design is L5. If the answer is "under 10 minutes to every node and every edge cache, by a T&S operator through an audited console", the design is Staff-grade. Answering it forces the build/serve split, the override layer, the cache purge path and the ownership model all at once.

2. Problem Framing & Intent#

2.1 The Three Intents — Explained#

Query completion. Completes what the user is typing into a full query, ranked by how often that query is issued (with time decay), how often the suggestion gets clicked, and freshness. The same prefix gets the same answer for most users in a locale — which makes it cacheable at the edge. The risk is reputational and legal: offensive, defamatory or private suggestions. The owner is search infra (mechanism) with Trust & Safety (policy).

Entity typeahead. Completes to things — people, pages, products, places — usually with an icon and a link. Ranking is dominated by the user's relationship to the entity (friends, follows, recent visits) and by entity popularity. It's mostly personalized, so it's not edge-cacheable; latency comes from pushing candidate sets to the client and from fast per-user lookups. The risk is privacy: never suggesting a private entity or revealing who someone looked up.

In-app navigation / command completion. Completes to commands, settings, documents or records inside an application. The corpus is small (thousands to a million items) and permission-filtered per user or tenant. Often the right answer is to ship the index to the client, or to run a per-tenant search index with prefix matching and typo tolerance. The risk is showing items a user isn't permitted to see.

🎯 Staff Move: "Query completion is a global, cacheable publishing problem. Entity typeahead is a per-user retrieval problem. Command completion is a permissions problem. I'll design the first and show the merge point for the second."

2.2 When NOT to Build a Typeahead Service#

• Small corpus (< ~100K items). Ship the list to the client and filter locally. Zero server QPS, zero latency, no service to own.
• Low traffic search boxes. If the search box gets 10 queries/s, use your search engine's completion suggester (Elasticsearch, OpenSearch, Solr) — a separate service adds an on-call rotation for no benefit.
• Highly permissioned data with no shared ranking. If every user's visible corpus differs (e.g., enterprise documents), a shared prefix table doesn't help; use per-tenant search with prefix queries.
• When suggestions create more risk than value. Sensitive domains (health, legal, children's products) may choose curated suggestions only, or none.

🎯 Staff Move: "If the corpus is a few thousand help articles, I'd ship them to the client as a compressed list and filter in JavaScript. A suggest service is something you build because QPS or corpus size forces you to."

2.3 What the Interviewer Leaves Underspecified#

2.4 Precise Terminology#

3. The Five Fault Lines#

3.1 Fault Line 1: Precompute vs Compute at Query Time#

The tension: Precomputing top-K for every prefix makes serving a single lookup, but rankings are frozen until the next build and storage grows with the total length of all queries. Computing at query time (walk a trie, score candidates, rank) is flexible and always current, but latency scales with the subtree size — and for a 1-character prefix that subtree is the whole corpus.

Staff default: Precompute top-K (K = 10, store N = 20–50 for re-ranking headroom) for every prefix up to length L = 20 characters of the normalized query. For prefixes longer than L, take the length-L entry and filter its candidates by the full prefix; if empty, fall back to a small query-time search over a long-tail index — rare (<2% of requests) and allowed a 50ms budget.

Sizing: 50M suggestible queries × average 25 chars, but prefixes are shared heavily. Distinct prefixes ≈ 200–500M. Each entry: 20 candidate IDs × 4 bytes + scores ≈ 120–160 bytes + key ≈ 200 bytes → ~40–100 GB raw; with an FST or front-coded keys, ~20–50 GB. Pruning prefixes nobody types (no traffic in 30 days) typically cuts another 30–60%.

🎯 Staff Move: "I'll move all ranking to build time. The server's job is one hash lookup and an override filter — that's how I hit a 10ms p99 at a million QPS on boring hardware."

3.2 Fault Line 2: Freshness vs Safety & Stability#

The tension: Users expect breaking news and new products to show up in suggestions within minutes. But every shortcut from "people searched it" to "we suggest it" is a path for brigading, spam and accidental publication of something harmful — and every refresh is a chance to roll out a bad index.

Staff default: Base index rebuilt daily (hourly for high-churn locales), with exponential time decay (half-life ~7 days for base, ~1 day for news-heavy verticals). Trending stream computes per-query rate over 5-minute windows vs a 7-day baseline; a query enters the overlay only if rate / baseline > 5×, distinct users ≥ 500 in the window, distinct /24 networks ≥ 100, and it passes the same policy classifiers as the base. Overlay capped at ~100K entries per locale, TTL 6–24h unless promoted into the base by the next build.

When to deviate: News or sports surfaces may lower thresholds and add human review for named entities. Commerce surfaces can drop trending entirely and refresh hourly.

🎯 Staff Move: "Trending is where abuse enters. I'll gate it on distinct users and network diversity, not raw counts — 50K searches from 300 accounts is a brigade, not a trend."

3.3 Fault Line 3: Global Cacheable vs Personalized#

The tension: A global answer per (locale, prefix) is cacheable everywhere — client, CDN, server — and is cheap. A personalized answer is better for the user but uncacheable outside the client, multiplying origin QPS and latency.

Staff default: Two requests or one merged response. Option A (cheapest): the client fetches the global list from the edge and merges its own locally stored recent queries (last ~50–100) that match the prefix — zero server personalization. Option B: the server merges a per-user candidate list (KV lookup, ~1ms) with global top-N and re-ranks; response marked Cache-Control: private. Start with A; add B only where measured relevance gain justifies the origin cost.

Privacy: recent-query history is user data — retention limits, deletion on request, and never shown on shared devices without a signed-in user.

🎯 Staff Move: "I'd personalize on the client first. The user's own recent searches are already on their device; merging them locally keeps the global response public-cacheable and costs us nothing."

3.4 Fault Line 4: Replicate vs Shard#

The tension: Sharding the prefix table across nodes scales memory, but prefix traffic is extremely skewed — single letters and common starts take a large share — so range sharding creates hot shards, and hash sharding still concentrates the hottest keys. Full replication avoids fan-out and hot shards but requires the whole table in every node's memory.

Staff default: Replicate. A 64–128 GB node holds the major locales; small locales share nodes. Group locales into serving pools. Shard only when one locale's table exceeds a node's RAM, then use the hybrid: prefixes of length ≤ 4 replicated in every shard (a few hundred MB), longer prefixes hash-sharded.

Hot-prefix math: at 1M QPS peak with ~60% absorbed upstream, origin sees ~400K QPS. If prefix "a" alone is ~1% of origin traffic (4K QPS), any node can serve it from RAM in microseconds — it's only a problem if you sharded it onto one node.

3.5 Fault Line 5: Central Policy vs Product Autonomy#

The tension: A central suggestion policy and override service guarantees consistent safety across every suggester, but slows product teams that need domain-specific curation. Per-surface policies move fast and fit their domain, but the weakest surface determines the company's exposure.

Staff default: One override service, one audit log, one propagation SLA. Every suggester calls it (or loads its compiled deny-set) on every response. Surfaces may add stricter local rules; they may not opt out of the floor.

4. Failure Modes & Operational Reality#

4.1 Bad Index Rollout — The Empty (or Wrong) Suggestions#

Scenario: A build bug (a normalization change) produces a snapshot where every prefix containing an apostrophe maps to nothing, and many accented prefixes map to the wrong candidates. It rolls out to all nodes at once.

t=0:       New snapshot en-US-2026-10-01T03 swapped on all nodes
t=+1min:   suggest.empty_response_rate jumps from 2% to 9%
t=+5min:   Suggestion CTR drops 15%; search volume dips slightly
t=+20min:  On-call notices dashboard; no alert fired (threshold 15%)
t=+25min:  Rollback to previous snapshot (atomic swap, seconds)

Detection: suggest.empty_response_rate per locale (alert at 2× baseline); suggest.ctr canary vs control; build-time validation against a golden set of 10K prefixes.

Mitigation: Immutable snapshots make rollback a pointer swap. Staged rollout: 1 node → 5% → 50% → 100% with automatic comparison of empty-rate and CTR between versions at each stage.

Owner: Search infra (build + rollout). Golden set maintained jointly with ranking.

4.2 Hot Prefix / Cache Stampede After Purge#

Scenario: T&S purges all edge-cached prefixes starting with a celebrity's name after a removal. The name is trending; tens of thousands of users are typing it. Every keystroke misses the edge simultaneously.

t=0:       Purge of 1,200 prefixes across the CDN
t=+1s:     Origin QPS for those prefixes: 0 → 60K/s
t=+5s:     Suggest nodes fine (RAM lookup), but the API gateway's
           connection pools to the region saturate
t=+30s:    p99 for all suggest traffic in region: 15ms → 400ms

Detection: edge.origin_requests spike; gateway.pool_utilization; suggest.p99 by region.

Mitigation: Edge request coalescing (one origin fetch per key per POP, others wait); purge as soft purge (serve stale while revalidating for non-safety purges); for safety purges, replace with the corrected response rather than delete (push-to-edge).

Owner: Edge/CDN team owns coalescing; search infra owns purge strategy.

4.3 Brigaded Suggestion — Coordinated Search Abuse#

Scenario: A coordinated group searches " scam" 80K times across 2 hours to push it into suggestions for "".

Detection: Trending gate rejects it (distinct users 900, but distinct /24 networks 40 and account age median 2 days). trending.rejected_by_gate{reason} spikes; T&S review queue receives it.

Mitigation: Gates on user and network diversity; account-age and reputation weighting in aggregation (new and low-reputation accounts count less); base-index aggregation over ≥7 days dilutes bursts.

Owner: T&S owns thresholds and review; search infra owns gate implementation.

4.4 Override Propagation Lag — The Removal That Didn't Stick#

Scenario: Legal requires removal of a defamatory suggestion. T&S adds the override. It's applied on nodes within 2 minutes — but mobile apps cache suggestion responses locally for 24h, and the CDN TTL is 15 minutes. Users keep seeing it.

t=0:       Override created
t=+2min:   All serving nodes filter it
t=+15min:  Edge caches expire
t=+24h:    Mobile client caches expire

Detection: Synthetic probes from multiple regions and app versions query the affected prefix and assert absence; override.propagation_seconds p99 per layer.

Mitigation: Push the override deny-set to clients too (small, compiled bloom/hash set, refreshed with app config every few minutes); client filters cached responses against it. Edge: targeted purge for affected prefixes. Client cache TTL ≤ 1h for suggestions.

Owner: Search infra owns the SLA across all layers, including clients; mobile team owns client-side filter.

4.5 Latency Regression — p99 Doubles After a Ranking Change#

Scenario: The ranking team adds a serve-time re-ranker with a feature lookup. p50 is fine; p99 goes from 12ms to 45ms due to KV tail latency.

Detection: suggest.latency_p99 per stage (lookup, re-rank, override, serialize); alert at 25ms.

Mitigation: Hard per-stage deadlines: if the re-ranker misses 5ms, return the base ranking. Hedged KV requests at p95.

Owner: Ranking team owns the re-ranker budget; search infra enforces the deadline.

4.6 Locale Normalization Bug — Turkish I#

Scenario: A generic lowercase function maps "İstanbul" incorrectly; Turkish users typing "is" don't see Istanbul-related suggestions, and some prefixes collide.

Detection: Per-locale golden sets; suggest.ctr and empty_rate broken down by locale.

Mitigation: Locale-aware case folding and normalization (NFKC + locale rules) shared between build and serve as one library.

Owner: Search infra (internationalization specialist), with locale QA.

4.7 Operational Reality Matrix#

5. Evaluation Rubric#

5.1 Level-Based Signals#

5.2 Strong Hire Signals#

5.3 Lean No-Hire Signals#

5.4 Common False Positives#

• Detailed trie memory layout ≠ typeahead design. Knowing pointer sizes doesn't show you can meet a latency budget or remove a suggestion in minutes.
• "Use Elasticsearch completion suggester" ≠ done. It's a fine engine choice; it doesn't answer freshness, safety, caching or personalization.
• Real-time freshness enthusiasm ≠ product judgment. Faster trending is not free; it's abuse surface.
• Knowing Unicode normalization forms ≠ multi-language design. IME, segmentation and transliteration are the hard parts.

6. Interview Flow & Pivots#

6.1 Typical 45-Minute Shape#

6.2 How Interviewers Pivot — And What They're Testing#

6.3 What to Deliberately Skip#

• Full-text retrieval and ranking for the search results page — reference Search Indexing
• Trie node memory layout beyond one sentence
• Load balancer details
• ML ranking model architecture — name features and the latency budget instead

6.4 Follow-Up Questions to Expect#

1. "How big is the index, and does it fit in memory?"
2. "How do you roll out a new index without a bad version reaching everyone?"
3. "A suggestion must be removed in 10 minutes. Walk me through every layer."
4. "How do trending queries get in, and what stops abuse?"
5. "What's cached where, and what's the hit rate at each layer?"
6. "How do you handle a prefix longer than your precomputed length?"
7. "How do you evaluate whether a ranking change made suggestions better?"

7. Active Drills#

Drill 1: The Opening (Intent + Budget)#

Prompt: "Design autocomplete for our search box."

Drill 2: The Build Pipeline#

Prompt: "Walk me from raw query logs to what's in memory on a serving node."

Drill 3: The Latency Budget — Make It Concrete#

Prompt: "Where does the 100ms go, and what do you cache where?"

Drill 4: Trending Without Brigading#

Prompt: "A celebrity announces a new album at 9pm. Users expect it in suggestions by 9:15. How?"

Drill 5: Hot Prefix and Hot Shard#

Prompt: "You sharded by first letter. The 's' shard is at 90% CPU and 'x' is idle. Fix it."

Drill 6: Personalization Without Losing the Cache#

Prompt: "Product wants suggestions personalized by the user's history. How do you add that without blowing up cost?"

Drill 7: Build vs Buy#

Prompt: "Why not just use Elasticsearch's completion suggester?"

Drill 8: Changing the Blocklist or Ranking Without an Incident#

Prompt: "T&S wants a new classifier that removes 'dangerous' suggestions. How do you ship it?"

Drill 9: Cost — Halve the Serving Bill#

Prompt: "Typeahead costs more than search itself. Cut it in half."

Drill 10: Multi-Language and Multi-Region#

Prompt: "We're launching in Japan, China and the Middle East. What changes?"

8. Deep Dive Scenarios#

Deep Dive 1: Peak-Traffic Incident — Breaking News Spike#

Context: A major breaking news event. Search traffic triples in 5 minutes; suggest traffic quadruples because users type slowly and retype. Origin p99 goes from 12ms to 300ms in two regions, and suggestions for the event's keywords are stale (the trending overlay is 20 minutes behind). The on-call escalates to you.

Questions to Surface First:

• Is the latency at the suggest nodes, the gateway, or the edge-to-origin path?
• Why is the overlay 20 minutes behind — is the streaming job lagging or blocked by gates?
• What's the edge hit rate now vs normal? Did a deploy or purge reset caches?
• Are we near node memory or CPU limits, or connection limits?

Typical L5 Approach: Scales out suggest nodes and waits. Checks the stream job's lag and restarts it. Correct moves, but new nodes take minutes to load a 40 GB snapshot, and restarting the stream job adds more lag.

Staff Approach: Finds that edge hit rate dropped from 55% to 20%: event keywords are new prefixes not in cache, and the edge TTL is short for long prefixes. Enables edge request coalescing (if not on), raises edge TTL for non-personalized responses to 5 minutes during the event, and turns off server-side personalization (load-shedding mode) to make more responses cacheable. Overlay lag: the stream job is fine; the gate requires 500 distinct users over a full 5-minute window and the window just closed — expected. Origin p99 recovers in 3 minutes without new nodes.

Principal Approach: Writes a "surge mode" into the design: a single switch that raises edge TTLs, disables server-side personalization, and increases debounce via remote config — pre-approved by product as a degraded mode. Sets a capacity target in terms of origin QPS at 0% edge hit rate for the top 1,000 prefixes, and adds a quarterly load test simulating a news spike. Makes the trending-latency SLO explicit and agreed with T&S, so "20 minutes behind" isn't an incident when it's the agreed safety budget.

Key Takeaway: "In a surge, the edge is your capacity. Design the degraded mode that makes more responses cacheable, and get it approved before the surge."

What clears the Staff bar:

• Finds the bottleneck at the cache layer rather than scaling the origin blindly
• Distinguishes expected trending latency from a fault
• Uses pre-approved degraded modes

Deep Dive 2: Silent Failure — The Index That Stopped Updating#

Context: A product manager notices that suggestions for a product launched 9 days ago never appear. You find the base index for three locales hasn't been rebuilt in 11 days. No alert fired. Serving is healthy.

Questions to Surface First:

• Did the build fail, or succeed but fail validation, or succeed and fail to publish?
• Why didn't anything alert on snapshot age?
• Are other locales also stale but unnoticed?
• Is the trending overlay masking staleness for popular queries?

Typical L5 Approach: Finds the failed job (a schema change in the log table broke the normalization step for those locales), fixes it, reruns the build, adds an alert on job failure.

Staff Approach: Fixes and rebuilds, but alerts on the outcome, not the job: index.age_hours per locale on serving nodes, paging at 36h. Also finds that validation correctly rejected two builds — but rejection went to a log, not a person. Adds a contract test for the log schema the pipeline depends on, owned jointly with the logging team.

Principal Approach: Generalizes: any system serving precomputed artifacts (suggestions, recommendations, spell-correction dictionaries, ranking models) can go silently stale. Introduces a standard: every served artifact exposes its age and version as a metric, with an owner and a max-age SLO. Adds upstream schema changes to a change-review process with downstream consumers registered.

Key Takeaway: "Alert on the age of what you serve, not on the success of the job that builds it."

What clears the Staff bar:

• Moves alerting from process to outcome
• Notices validation rejections need a human owner
• Fixes the upstream contract, not just the parser

Deep Dive 3: Large Onboarding — A New Surface Adopts the Platform#

Context: The shopping team wants to retire its own autocomplete and use the shared suggestion platform. They have 80K QPS peak, a catalog of 200M products, need suggestions to reflect price drops and inventory within 15 minutes, and have their own blocklist of 30K terms. Launch in 6 weeks.

Questions to Surface First:

• Are they completing queries or products (entities)? Probably both.
• Does inventory need to be in the suggestion index, or can it be a serve-time filter?
• Is their blocklist stricter than the platform floor, looser, or overlapping?
• Who owns relevance regressions after migration — them or the platform?

Typical L5 Approach: Adds a "shopping" locale-like index to the build, imports their blocklist, and capacity-plans for 80K QPS.

Staff Approach: Splits their needs: query completion uses the shared build with a shopping-specific scoring function plug-in; product entity completion is a separate candidate source (top products per prefix) merged at serve time; inventory and price are serve-time filters from a small fast store, so the index doesn't rebuild every 15 minutes. Their blocklist is layered on top of the platform floor as surface-specific rules. Migration runs in shadow for 2 weeks comparing CTR against their current system.

Principal Approach: Uses the onboarding to define the platform's surface contract: what a surface can customize (scoring plug-in, candidate sources, stricter rules, UI) and what it cannot (privacy threshold, policy floor, override service, propagation SLA). Agrees on an SLO split — platform owns availability and latency; surface owns relevance — and a chargeback model so capacity growth is funded by the surface that drives it.

Key Takeaway: "Onboarding is where a platform defines its contract. Write down what surfaces can customize and what they can't before the first one migrates."

What clears the Staff bar:

• Moves fast-changing data (inventory) to serve-time filters
• Layers surface rules on a non-negotiable floor
• Splits SLO ownership explicitly

Deep Dive 4: Post-Mortem — The Suggestion That Made the News#

Context: For six hours, typing a politician's name suggested a false and defamatory completion. It reached social media and press. The suggestion passed the privacy threshold (thousands of distinct users searched it after a viral post) and no classifier flagged it. You're leading the post-mortem.

Questions to Surface First:

• Did it enter via the base build or the trending overlay?
• How long from first report to removal at each layer — nodes, edge, clients?
• Were there earlier signals (user reports, T&S queue) that were missed?
• Are other public figures exposed to the same pattern right now?

Typical L5 Approach: Adds the phrase to the blocklist, rebuilds, and adds the politician's name to a sensitive-entity list.

Staff Approach: Timeline shows it entered via trending (legitimate diversity — a real viral wave), removal took 6 hours because the override console required an engineer, and mobile clients cached it for 24h. Fixes: T&S operators can create overrides directly (audited); client-side deny-set; edge push-replace. Pattern fix: completions pairing a person entity with an allegation-type term ("is a", "arrested", "affair") require classifier scoring and, above a traffic threshold, human review before entering trending.

Principal Approach: Treats it as a policy and governance gap, not a classifier gap. Establishes an org-level suggestion policy for named individuals with legal and policy teams, a defined removal SLA (e.g., 30 minutes from report for high-severity), a 24/7 T&S staffing decision for that SLA, and quarterly removal-propagation drills across web, mobile and edge. Reports time-to-removal to leadership as a risk metric alongside availability.

Key Takeaway: "The removal path is the safety system. Measure it end to end, including caches you don't own."

What clears the Staff bar:

• Measures removal latency per layer, including clients
• Separates policy decision (T&S) from mechanism (infra)
• Fixes the pattern class, not the single string

Deep Dive 5: Multi-Region Expansion#

Context: Typeahead runs from two US regions. Leadership wants sub-50ms p95 keystroke latency in Europe, India and Southeast Asia, and EU data protection review flagged that EU users' query logs are processed in the US.

Questions to Surface First:

• What's current p95 for those users, and how much is RTT vs server?
• Does the EU requirement apply to query logs (personal data) or also to derived aggregates?
• Do overrides need to be global, regional, or both (some removals are country-specific)?
• What's the edge hit rate in those regions?

Typical L5 Approach: Deploys suggest nodes in each new region, replicates the snapshot store, and routes users by geo-DNS.

Staff Approach: Serving is easy to regionalize because snapshots are immutable files — replicate them to regional object storage, nodes pull locally. The harder part is the build: EU query logs are processed in an EU pipeline that produces EU-locale snapshots; aggregated, k-anonymized prefix tables can then be served anywhere. Overrides are a global replicated set with per-country scoping (a court order in one country applies only there). Edge caching in those regions handles most traffic.

Principal Approach: Separates two decisions with different owners and reversal costs: serving locality (an engineering decision, two-way door) and data processing location (a legal one-way door). Gets legal to confirm in writing that k-anonymized aggregates are outside personal-data scope before designing around it. Prices the regional build pipelines (each adds compute plus an on-call surface) and consolidates where regulation permits.

Key Takeaway: "Immutable snapshots make serving trivially regional. The hard part is where the raw data may be processed."

What clears the Staff bar:

• Separates serving locality from data-processing locality
• Scopes overrides by country
• Measures RTT before adding regions

9. Level Expectations Summary#

After studying this case study, you should be able to:

• Distinguish query completion, entity typeahead and command completion, and pick one with reasons
• Derive a per-keystroke latency budget and show where each millisecond goes
• Explain why top-K per prefix is precomputed offline, and size the resulting index
• Place caches at the client, the edge and the server, and explain how personalization affects cacheability
• Design a trending overlay with diversity gates that resists brigading
• Design the safety pipeline: k-anonymity, classifiers, overrides with an end-to-end propagation SLA
• Choose replication over sharding when the index fits, and handle hot prefixes when it doesn't
• Handle IME input, script-specific normalization and per-locale policy

The Bar for This Question#

Mid-level (L4): Builds a trie with frequencies, finds completions by traversal, maybe caches popular prefixes. Works for a demo; doesn't address latency at scale, freshness or safety.

Senior (L5): Precomputes top-K per node, serves from memory, shards and replicates, adds a cache, rebuilds periodically. Solid and correct. Tends to treat freshness as "rebuild faster", safety as a word list, and caching as one Redis tier; doesn't price personalization.

Staff+ (L6): Starts from intent and a per-keystroke budget. Moves all ranking offline into a pipeline with privacy and policy stages, publishes immutable versioned snapshots with staged rollout, layers caching from client to edge, adds a gated trending overlay, and owns an override path with a measured propagation SLA across nodes, edge and clients. Names owners: search infra for mechanism, T&S for policy, legal for removals. Handles non-Latin input. The interviewer should learn something from the answer.

10. Staff Insiders: Controversial Opinions#

10.1 "The Trie Is Not the Interview"#

The Staff position: Spend 2 minutes on the data structure — "precomputed top-K per prefix, FST or hash table, immutable snapshot" — and 40 on budget, caching, freshness and safety.

Why this matters in interviews: Interviewers who've asked this question many times have seen every trie. Moving past it quickly signals you know where the work is.

10.2 "Real-Time Suggestions Are a Liability, Not a Feature"#

The Staff position: Minutes, gated, with an overlay that expires. Seconds-fresh suggestions for open-ended queries create more incidents than value.

Why this matters in interviews: Pushing back on "real-time" with a reasoned safety argument is a classic Staff-level signal.

10.3 "Replicate the Whole Index — Sharding Is Usually Premature"#

The Staff position: Replicate until the table doesn't fit, then shard only the long tail.

Why this matters in interviews: "Shard by first letter" is the most common L5 reflex; arithmetic that shows it's unnecessary is memorable.

10.4 "The Best Personalization Happens on the Client"#

The Staff position: Merge recent history on the client; reserve server personalization for cases with measured lift.

Why this matters in interviews: It shows you see caching, cost and privacy as one decision.

10.5 "Suggestion Safety Is a Staffing Decision"#

The Staff position: The override mechanism is easy; a 30-minute removal SLA needs 24/7 T&S coverage and per-locale reviewers. Say so.

Why this matters in interviews: Naming the people cost of a safety requirement is a bridge into the L7 conversation.

11. The Principal Lens (L7)#

Why L7 Sees This Problem Differently#

A Staff engineer designs an autocomplete. A Principal engineer notices the company has six of them — web search, maps, shopping, help center, the mobile app's search, and an internal tool someone open-sourced — each with its own blocklist, its own privacy threshold (or none), and its own idea of how fast a removal happens. The next suggestion that makes the news will come from whichever is weakest. At org scale, typeahead is a publishing platform: a shared build pipeline with mandatory privacy and policy stages, one override service with an audited removal SLA, and surface-owned ranking on top. The lookup service is the least interesting part.

🧭 Principal Move: "Before designing another suggester, I'd like to know how many exist and how each handles a removal request. If a court order today means six tickets to six teams, the design we need is one override service and one policy floor — and this surface is its first customer."

The Org-Level Fault Line#

One suggestion platform vs per-surface suggesters.

The deciding question: how many surfaces show suggestions to the public? One: build it well. Two or more: the safety floor must be shared; ranking can stay local.

Cost Model#

Assumptions: cloud list prices, memory-optimized nodes ~$1–2K/month (128–256 GB RAM), CDN requests ~$0.50–$1 per million, loaded engineer cost ~$25K/month.

The line that matters to leadership: at 1M QPS peak, every 10 points of edge hit rate is roughly the cost of a regional serving pool. And the dominant non-infra cost is people: a 30-minute, 24/7 removal SLA across 40 locales is a T&S staffing commitment larger than the serving team.

The 3-Year Evolution Path#

Each step is triggered by an event. Building a multi-surface platform before a second surface exists is how a team spends a year on abstractions nobody uses.

One-Way Doors vs Two-Way Doors#

🧭 Principal Insight: Spend review time proportional to reversal cost. The FST debate gets an hour. Client cache TTLs in the mobile app, the privacy threshold and the log-processing location get a review with privacy, legal and mobile in the room — because those are the ones you can't take back quickly.

The Standard I'd Write#

RFC: Public Suggestion Surfaces Standard (v1)

Scope: Any product surface that shows auto-generated suggestions, completions or related searches to users.

Requirements:

• Suggestions derived from user behavior MUST pass a k-anonymity threshold of ≥ k distinct users over ≥ d days (values set by the privacy office per surface).
• Every suggester MUST apply the shared override service on every response and MUST meet the removal propagation SLA (p99 ≤ 10 minutes to serving, edge and supported clients).
• Client caches of suggestions MUST NOT exceed 1 hour TTL and MUST apply the client deny-set.
• Index builds MUST record the policy version and pass golden-set validation before rollout; rollouts MUST be staged.
• Surfaces SHOULD use the shared build pipeline; surfaces that do not MUST document equivalent privacy and policy stages.

Exceptions: Filed with the search platform architecture group and T&S; decision within 5 business days; maximum 2 quarters.

Success metrics: All public suggesters on the override service within 3 quarters; removal p99 ≤ 10 min measured by quarterly drill; zero suggestions shown below the privacy threshold; number of independent blocklists reduced to one floor plus surface rules.

What I'd Tell the VP#

"Search suggestions are the highest-traffic thing our search product does, and every one of them is something we say to users before they've asked. Today six products generate suggestions with six different safety processes, and the last removal request took six hours. I'm proposing one shared suggestion platform with a common safety floor and a 10-minute removal guarantee, while each product keeps control of its own ranking. It costs about four engineers for a year plus round-the-clock trust-and-safety coverage we partly have already. The return is that the next problem suggestion is gone in minutes instead of in the news, and new products get autocomplete in weeks instead of building their own."

Principal Interview Signals#

Staff answers that L7 interviewers find insufficient:

• "We'll add an override layer for removals." — correct, but silent on the clients and other surfaces that don't use it.
• "Trending is gated on distinct users." — right mechanism, but no owner for the thresholds and no per-locale review capacity.
• "We'll replicate the index to every region." — sound serving design that never asks where the query logs may legally be processed.

Appendices

for query q in suggestible_queries(locale):
    s = score(q)                                  # decayed count + CTR term
    for i in 1..min(len(q), L):
        p = q[0:i]
        heap[p].push((s, q)) keep top N           # bounded heap per prefix

for p in heap:
    emit(p, sorted(heap[p]))                      # sorted key order for FST

score(q) = Σ_d count(q, d) × 0.5^((today - d) / half_life)
half_life: 7 days (general), 1–2 days (news), 30 days (stable catalogs)

# Latency and load
suggest.e2e_latency_p95{country}        # client-measured, keystroke to render
suggest.p99{stage}                      # lookup, merge, override, serialize
edge.hit_rate{region}
edge.origin_requests

# Quality
suggest.ctr{locale,surface}
suggest.keystrokes_saved{locale}
suggest.empty_response_rate{locale}

# Freshness
index.age_hours{locale}
trending.overlay_age_seconds
trending.rejected_by_gate{reason}

# Safety
override.propagation_seconds{layer}
tns.report_to_removal_minutes
synthetic_probe.violations_total        # must be zero