Typeahead / Search Autocomplete

What is Typeahead Search?

As a user types a query, the system returns the top-k most likely completions in real time (< 100ms). Used in Google Search, YouTube, Amazon product search.

Key operations:

• Suggest: Given prefix, return top-k completions ranked by popularity
• Log: Record actual search queries for future ranking
• Update: Periodically rebuild trie from query logs

Functional

• Return top 5 suggestions for any prefix
• Suggestions ranked by search frequency
• Update suggestions based on recent trends (within 24h)
• Support 100+ languages (optional)

Non-Functional

• Latency: < 100ms end-to-end
• Scale: 10M queries/sec (Google scale)
• Availability: 99.99%

Capacity

• 10M queries/sec × average 5 keystrokes per query = 50M requests/sec
• Trie for top 1M terms: ~100MB in memory per server
• CDN caches top 10K prefixes — covers ~80% of traffic

Data Structure: Trie

A trie (prefix tree) stores strings character by character. Each node represents a character, and each leaf (or marked node) represents a complete term.

Prefix lookup in O(p) where p = prefix length. At each node, store top-k terms for that prefix (pre-computed).

Two separate concerns

1. Serving (hot path): Prefix → top-k suggestions. Must be < 100ms. Use in-memory trie or Redis.
2. Building (cold path): Aggregate query logs → rank terms → rebuild trie. Can run hourly as a batch job.

CDN for top prefixes

Top 1,000 prefixes ("th", "wh", "ho") account for most traffic. Cache at CDN edge — zero backend hit for common prefixes.

Serving Flow

1. User types "ap"
2. Check CDN cache for prefix "ap" → hit? Return immediately
3. CDN miss → API Gateway → Suggestion Service
4. Suggestion Service looks up trie: find node at "ap" → return pre-computed top-5 terms

Trie Node

{
  "prefix": "ap",
  "top_suggestions": [
    { "term": "apple",   "score": 9800000 },
    { "term": "app",     "score": 7200000 },
    { "term": "apply",   "score": 3100000 }
  ]
}

Trie Update Pipeline

1. Search queries logged to Query Log DB
2. Batch job (hourly): count term frequencies over 7-day window
3. For each trie node, compute top-k children
4. Serialize updated trie → publish to Redis / push to servers

Trie vs Ternary Search Tree vs Redis

• Trie in memory: fastest (O(p)), ~100MB for 1M terms
• Redis Sorted Sets: ZRANGEBYLEX for prefix search. Simple ops, slight overhead vs pure trie
• Elasticsearch: overkill for pure prefix; good if you need fuzzy match

Personalization

Blend global frequency with per-user query history:

final_score = 0.7 × global_freq + 0.3 × user_affinity_score

Trending Terms

Recent spike in "earthquake" should surface quickly. Use a sliding 1-hour window with higher weight than the 7-day average.

What Interviewers Look For

1. Trie explanation — clearly explain prefix lookup and pre-computed top-k at each node
2. Separate read/write paths — serving (real-time) vs building (batch)
3. CDN caching — top prefixes cached at edge
4. Ranking — not just alphabetical, frequency-weighted
5. Update freshness — how quickly do trending terms appear?

Common Mistakes

• Linear scan through all terms for each prefix
• Not storing top-k at each trie node (recomputing every time)
• Forgetting about CDN for high-traffic prefixes