Typeahead Suggestion / Autocomplete Design

Problem and Scope

Design a typeahead (autocomplete) service that returns the top-3 suggestions for the prefix the user is typing. Suggestions should be ordered by a combination of popularity (frequency) and recency. The system must provide real-time responses with very low latency, scale to large traffic, and be highly available.

Start by confirming the core user journey, exclusions, success criteria, and the constraints that materially affect the architecture.

Requirements to Clarify

A strong answer should establish scope before choosing components.

Functional requirements:

• Return up to 3 suggestions for a given input prefix.
• Order suggestions by a ranking combining frequency and recency.
• Support incremental queries as user types (very low latency).

Non-functional requirements:

• Low latency (p50 << p95, target p95 < 50ms server-side).
• High throughput and horizontal scalability.
• High availability and graceful degradation.
• Reasonable freshness of ranking (near-real-time acceptable).

Scale and Capacity

Use the workload to justify storage, partitioning, caching, and reliability decisions. Clarify or challenge these assumptions rather than treating them as unquestionable facts:

• Example corpus: Google-like 5B queries/day.
• Unique queries ~30% => 1.5B unique/day.
• Storage rough calc from prompt: 15 chars/query * 2 bytes => ~45GB/day of raw query bytes.
• Overall qps: 5B / 86400 ≈ 57,870 QPS average. With typing amplification and peaks, provision for 3x–5x peak => ~180k–290k QPS.
• Autocomplete read amplification: each character typed issues a request; average session may produce multiple requests per search; plan cache-heavy reads.
• Target cache hit rate >= 95% to meet latency targets; cold-path queries served from persistent store.

Architecture Discussion

Walk through the important read and write paths, identify ownership boundaries, and explain how the design behaves when dependencies fail. Cover these areas explicitly:

• Prefix index or trie representation, top-k materialization, and memory layout
• Popularity, recency, personalization, and ranking update semantics
• Offline aggregation plus streaming updates with bounded freshness
• Sharding, replication, multilayer caching, hot prefixes, and tail latency
• Typo tolerance, Unicode normalization, language isolation, and filtering
• Availability, stale fallback, privacy, abuse prevention, and experiment measurement

Follow-up Questions

Expect the interviewer to test the consequences of your choices. Practise answering these questions with a concrete decision, its benefit, and its cost:

• Is the top-k fixed (k=3) or configurable? (Assume fixed k=3 for the core design, but allow extension.)
  • Focus: Assess the candidate's answer to "Is the top-k fixed (k=3) or configurable? (Assume fixed k=3 for the core design, but allow extension.)" for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Are suggestions global or personalized? (Assume global by default; discuss personalization later.)
  • Focus: Assess the candidate's answer to "Are suggestions global or personalized? (Assume global by default; discuss personalization later.)" for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• What is the target tail latency (p50/p95)? (Aim for p95 < 50ms server-side.)
  • Focus: Assess the candidate's answer to "What is the target tail latency (p50/p95)? (Aim for p95 < 50ms server-side.)" for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• How fresh must popularity stats be? (Near-real-time acceptable; hourly/batched updates acceptable.)
  • Focus: Assess the candidate's answer to "How fresh must popularity stats be? (Near-real-time acceptable; hourly/batched updates acceptable.)" for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Read/write ratio and expected qps? (We’ll estimate from example traffic below.)
  • Focus: Assess the candidate's answer to "Read/write ratio and expected qps? (We’ll estimate from example traffic below.)" for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Acceptable consistency model? (Eventual consistency for popularity is fine.)
  • Focus: Assess the candidate's answer to "Acceptable consistency model? (Eventual consistency for popularity is fine.)" for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Personalization: incorporate user history and context into ranking (privacy considerations).
  • Focus: Assess the candidate's answer to "Personalization: incorporate user history and context into ranking (privacy considerations)." for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Typo tolerance: add fuzzy matching (edit distance) or include n-gram/phonetic indexes; increases compute and memory cost.
  • Focus: Assess the candidate's answer to "Typo tolerance: add fuzzy matching (edit distance) or include n-gram/phonetic indexes; increases compute and memory cost." for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Multilingual support: shard by language, normalize input with unicode normalization.
  • Focus: Assess the candidate's answer to "Multilingual support: shard by language, normalize input with unicode normalization." for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• A/B testing and online learning: test ranking variants and adapt weights.
  • Focus: Assess the candidate's answer to "A/B testing and online learning: test ranking variants and adapt weights." for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Real-time updates: if stricter freshness required, integrate an incremental streaming path that applies high-frequency updates to in-memory top-k for hot prefixes.
  • Focus: Assess the candidate's answer to "Real-time updates: if stricter freshness required, integrate an incremental streaming path that applies high-frequency updates to in-memory top-k for hot prefixes." for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Rich suggestions: include categories, snippets, icons; store metadata alongside phrase records.
  • Focus: Assess the candidate's answer to "Rich suggestions: include categories, snippets, icons; store metadata alongside phrase records." for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.

Evaluation Rubric

MockMe evaluates the answer across the following dimensions. A complete answer should connect claims to requirements and explain consequential trade-offs.

• Requirements and scope (15%): Clarifies and prioritizes the required behavior for Return up to 3 suggestions for a given input prefix; Order suggestions by a ranking combining frequency and recency; Support incremental queries as user types (very low latency). Establishes the constraints that materially affect Typeahead Suggestion / Autocomplete Design, including Low latency (p50 << p95, target p95 < 50ms server-side); High throughput and horizontal scalability. Strong evidence includes Separates the critical path from secondary features and resolves ambiguous requirements before choosing components.
• Architecture and interfaces (20%): Presents coherent ownership boundaries and end-to-end flows covering Prefix index or trie representation, top-k materialization, and memory layout; Popularity, recency, personalization, and ranking update semantics; Offline aggregation plus streaming updates with bounded freshness; Sharding, replication, multilayer caching, hot prefixes, and tail latency. Strong evidence includes Defines interfaces and traces important success, retry, and failure paths across the proposed components.
• Data and scaling (25%): Uses workload assumptions such as Example corpus: Google-like 5B queries/day; Unique queries ~30% => 1.5B unique/day to justify capacity and partitioning decisions. Explains the data, state, or model strategy for Prefix index or trie representation, top-k materialization, and memory layout; Popularity, recency, personalization, and ranking update semantics; Offline aggregation plus streaming updates with bounded freshness. Strong evidence includes Quantifies a dominant workload, identifies the first bottleneck, and explains how the design evolves as that workload grows.
• Reliability, correctness, and safety (20%): Explains concrete failure behavior, recovery, and operational safeguards for Availability, stale fallback, privacy, abuse prevention, and experiment measurement; High availability and graceful degradation. Strong evidence includes States the required correctness or consistency boundary and covers retries, partial failure, observability, and safe degradation.
• Communication and trade-offs (20%): Drives a structured discussion and compares consequential alternatives for Sharding, replication, multilayer caching, hot prefixes, and tail latency; Typo tolerance, Unicode normalization, language isolation, and filtering; Availability, stale fallback, privacy, abuse prevention, and experiment measurement. Strong evidence includes Makes assumptions explicit, answers the question asked, and explains both the benefit and cost of major decisions.