Search Autocomplete

Functional Requirements

1. Real-time Suggestions: As the user types each character, return top-k autocomplete suggestions within 100ms.
2. Top-K Retrieval: Return the K most relevant suggestions per prefix (K typically 5–10).
3. Multi-language Support: Handle English, Chinese, Hindi, Arabic, emoji, and mixed-script queries.
4. Personalization: Optionally boost suggestions based on user search history.
5. Trending Boost: Promote recently trending queries higher in results.

Non-Functional Requirements

Requirement	Target
Latency (p99)	< 100ms
Throughput	100K+ QPS
Availability	99.99%
Freshness	Suggestions updated every 1–4 hours
Scalability	Handle billions of unique prefixes

Data Collection Pipeline

The foundation of autocomplete is a robust data collection and aggregation pipeline:

User Types Query
      │
      ▼
┌─────────────┐    ┌──────────────┐    ┌──────────────┐
│  Search API  │───▶│  Query Logger │───▶│  Kafka Topic  │
└─────────────┘    └──────────────┘    └──────┬───────┘
                                              │
                                              ▼
                                     ┌──────────────┐
                                     │  Aggregation  │
                                     │  (MapReduce)  │
                                     └──────┬───────┘
                                            │
                                            ▼
                                     ┌──────────────┐
                                     │ Frequency Map │
                                     │ (prefix →     │
                                     │  top queries) │
                                     └──────────────┘

Step-by-step collection process:

1. Log every search query with timestamp, user ID (anonymized), locale, and result clicked.
2. Buffer logs in Kafka for durability and decoupling.
3. Aggregate periodically (every 1–4 hours) via a batch job (Spark/MapReduce):
   • Count query frequencies over a rolling window (e.g., last 7 days).
   • Decay older queries: score = frequency × e^(-λ × days_old).
   • Filter out offensive/abusive queries using a blocklist.
   • Group by prefix and retain top-K queries per prefix.
4. Build trie from the aggregated frequency map.
5. Deploy trie to serving tier (in-memory caches).

Frequency Map Schema

{
  "prefix": "amaz",
  "top_queries": [
    {"query": "amazon prime", "score": 98420},
    {"query": "amazon jobs", "score": 72100},
    {"query": "amazonaws", "score": 54300},
    {"query": "amazon rainforest", "score": 41200},
    {"query": "amazon appstore", "score": 28900}
  ]
}

Handling Multi-Language

• Segment by locale: Build separate tries per locale (en, zh, hi, ar) to avoid cross-contamination.
• Transliteration handling: Map phonetic variants ("youtube" ↔ "youtub") to the same canonical form.
• Unicode normalization: Apply NFKC normalization before indexing.
• Right-to-left scripts: Arabic and Hebrew queries stored normally; display handled by client.

Blocklist & Safety

• Maintain a blocklist of offensive queries updated daily.
• Use ML-based toxicity detection for borderline queries.
• Log flagged queries for human review.

Trie Data Structure

A trie (prefix tree) is the canonical data structure for autocomplete. Each node stores a character, and the path from root to node represents a prefix. Leaf/internal nodes store the top-K queries for that prefix.

                    root
                  /   |   \ 
                a     b     c
               /     |      \
              m      a       a
             / \     |        \
            a   o    t         r
           /   |     |          \
          z    s     t           e
         /     |     |            \
        o      h     o            s
       /              |            \
      n              p             s
                        \
                         e

Trie Node Structure:

class TrieNode:
    def __init__(self):
        self.children = {}        # char → TrieNode
        self.top_queries = []     # List[(query, score)]  # top-K for this prefix
        self.is_end = False
        self.frequency = 0        # total frequency of this exact prefix

Key operations:

Operation	Time Complexity	Description
Insert	O(L)	L = length of query
Search Prefix	O(L)	Find node for prefix
Top-K for Prefix	O(K)	Retrieve pre-stored top-K
Delete	O(L)	Remove query from trie

Prefix Search with Top-K Retrieval

def autocomplete(prefix: str, k: int = 5) -> List[str]:
    node = root
    for char in prefix:
        if char not in node.children:
            return []
        node = node.children[char]
    # node.top_queries already contains pre-computed top-K
    return [(q, s) for q, s in node.top_queries[:k]]

Why pre-compute top-K at each node?

• During offline aggregation, for every prefix that appears in any query, we compute and store the top-K suggestions.
• At serving time, we just traverse to the prefix node and return stored results — O(L) time, no DFS needed.
• Trade-off: more memory (each node stores K query strings), but serving is instant.

DFS with Priority Queue (Alternative)

If memory is constrained, store only exact-query frequencies and compute top-K on-the-fly:

def autocomplete_dfs(prefix: str, k: int) -> List[str]:
    node = traverse_to_prefix(prefix)
    if not node:
        return []
    
    min_heap = []  # (score, query)
    dfs(node, prefix, min_heap, k)
    
    return sorted(min_heap, key=lambda x: -x[0])

def dfs(node, current_prefix, heap, k):
    # Add current node's accumulated queries
    for query, score in node.exact_queries:
        if len(heap) < k:
            heapq.heappush(heap, (score, query))
        elif score > heap[0][0]:
            heapq.heapreplace(heap, (score, query))
    
    for char, child in node.children.items():
        dfs(child, current_prefix + char, heap, k)

Time complexity: O(N) where N = number of nodes under prefix. This is why pre-computation is preferred for serving.

Compressed Trie (Radix Tree)

Standard tries waste memory on chains of single-child nodes. A radix tree (compressed trie) merges chains:

Standard Trie:     Radix Tree:
    a                  amaz
    │                  / \
    m              on   ing
    │              /      \
    a           on    ongkong
    │           / \
    z         e    o
    │         /      \
    o      prime    ring
    │         
    n      jobs

Memory savings: 50–80% reduction vs. standard trie.

class RadixNode:
    def __init__(self):
        self.children = {}      # prefix_string → RadixNode
        self.top_queries = []
        self.is_end = False

Memory Optimization Strategies

Strategy	Savings	Trade-off
Radix tree compression	50–80%	Slightly slower traversal
Store pointers instead of strings in top-K	30–50%	Indirection overhead
LRU eviction of cold prefixes	Variable	Rare prefixes re-computed
Memory-mapped files (mmap)	Swap to disk	Slower cold reads
Approximate counting (Count-Min Sketch)	60–70%	Approximate frequencies

Architecture Overview

┌──────────┐     ┌───────────┐     ┌──────────────────┐
│  Client   │────▶│ API Gateway│────▶│ Autocomplete API  │
│ (Browser/ │     │  (LB/WAF) │     │   (Stateless)     │
│  Mobile)  │◀────│           │◀────│                    │
└──────────┘     └───────────┘     └────────┬─────────┘
                                             │
                              ┌──────────────┼──────────────┐
                              ▼              ▼              ▼
                       ┌──────────┐  ┌──────────┐  ┌──────────┐
                       │ Trie     │  │ Trie     │  │ Trie     │
                       │ Shard 1  │  │ Shard 2  │  │ Shard N  │
                       │ (prefix  │  │ (prefix  │  │ (prefix  │
                       │  a-i)    │  │  j-r)    │  │  s-z)    │
                       └──────────┘  └──────────┘  └──────────┘
                              │              │              │
                              └──────────────┼──────────────┘
                                             ▼
                                    ┌──────────────┐
                                    │  Redis Cache  │
                                    │  (hot prefix  │
                                    │   results)    │
                                    └──────────────┘

Request flow:

1. Client sends keystroke event (debounced 100–300ms).
2. API Gateway routes to autocomplete service.
3. Service checks Redis cache for prefix.
4. Cache miss → route to correct trie shard based on prefix.
5. Trie shard returns top-K from in-memory trie.
6. Result cached in Redis and returned to client.

Scoring & Ranking Strategy

The quality of autocomplete suggestions depends on a multi-signal scoring model:

Final Score Formula:

score = w1 × frequency_score
      + w2 × recency_score
      + w3 × personalization_score
      + w4 × freshness_boost
      + w5 × trending_boost

Component	Description	Typical Weight
Frequency Score	Log-scaled total query count over 7 days	0.50
Recency Score	Weighted by time decay: e^(-λ × hours_ago)	0.20
Personalization	User's own search history boost	0.15
Freshness Boost	New/trending queries get temporary boost	0.10
Trending Boost	Queries with accelerating velocity	0.05

Frequency scoring with log scaling:

def frequency_score(count: int) -> float:
    import math
    return math.log1p(count)  # log(1 + count) to handle zeros

Time decay function:

def recency_score(timestamp_hours_ago: float, half_life: float = 168) -> float:
    import math
    return math.exp(-0.693 * timestamp_hours_ago / half_life)

Trending detection (velocity):

def trending_boost(current_count: float, previous_count: float) -> float:
    if previous_count == 0:
        return current_count > 100 ? 2.0 : 1.0
    velocity = current_count / previous_count
    return min(velocity, 5.0)  # cap at 5x boost

Personalization

• Maintain a per-user recent search history (last 50 queries) in Redis.
• When computing suggestions, boost queries that match user's past searches.
• Privacy consideration: Personalization data stored locally or in encrypted form; users can opt out.
• Cold start: New users get generic (frequency-only) suggestions.

Real-time Update Strategy

Autocomplete needs fresh suggestions without redeploying the entire trie:

┌─────────────────────────────────────────────────────┐
│                Update Pipeline                       │
│                                                      │
│  ┌──────────┐   ┌───────────┐   ┌──────────────┐   │
│  │ Query    │   │ Real-time │   │ Recent Query │   │
│  │ Logger   │──▶│ Aggregator│──▶│ Cache (Redis)│   │
│  └──────────┘   │ (Flink)   │   └──────┬───────┘   │
│                  └───────────┘          │            │
│                                         ▼            │
│                                  ┌──────────────┐   │
│                                  │ Merge with   │   │
│                                  │ Batch Trie   │   │
│                                  │ (every 1-4h) │   │
│                                  └──────────────┘   │
└─────────────────────────────────────────────────────┘

Three-tier freshness model:

1. Batch layer (hours): Full trie rebuild via Spark every 1–4 hours. Handles 99% of traffic.
2. Speed layer (seconds): Flink streaming job aggregates last 1 hour of queries into a "recent" trie or Redis cache.
3. Merge strategy: At query time, merge batch trie results with recent query cache:

   def get_suggestions(prefix: str) -> List[str]:
       batch_results = trie_shard.query(prefix)  # from batch trie
       recent_results = redis.get(f"recent:{prefix}")  # from streaming
       merged = merge_and_rerank(batch_results, recent_results)
       return merged[:K]
   

Trie rebuild process:

1. New batch job reads last 7 days of query logs from Kafka/S3.
2. Builds new trie in memory (can be done in parallel shards).
3. Validates trie (correctness checks, memory bounds).
4. Atomic swap: new trie deployed to serving tier, old trie torn down.
5. Zero-downtime deployment via blue-green or rolling update.

Sharding Strategy

Option 1: Prefix-range sharding

Shard 1: a-f    Shard 2: g-m    Shard 3: n-s    Shard 4: t-z

• Pros: Range queries are efficient, easy to reason about.
• Cons: Hotspots if certain letter ranges are popular (e.g., "a" prefix is very common).

Option 2: Hash-based sharding

def get_shard(prefix: str) -> int:
    return hash(prefix[:2]) % NUM_SHARDS  # hash on first 2 chars

• Pros: Even distribution across shards.
• Cons: Range queries span multiple shards.

Recommended: Hash-based with consistent hashing for shard rebalancing.

Caching Strategy

┌────────────┐    ┌──────────┐    ┌──────────┐    ┌──────────┐
│   Client    │───▶│ CDN Edge │───▶│ Redis    │───▶│ Trie     │
│             │    │ (hot     │    │ Cluster  │    │ Shard    │
│             │    │  prefix) │    │ (warm)   │    │ (cold)   │
└────────────┘    └──────────┘    └──────────┘    └──────────┘
    Latency:          <10ms          <20ms          <50ms

Cache tiers:

Tier	Storage	TTL	Hit Rate
CDN Edge	Top 10K prefixes	5 min	~40%
Redis Cluster	Top 1M prefixes	1 hour	~50%
In-memory Trie	All prefixes	Until rebuild	~10%

Cache key format: ac:{locale}:{prefix} → JSON array of suggestions.

Edge Cases

Edge Case	Handling
Empty prefix	Return trending/popular queries
Very long prefix (>50 chars)	Truncate to 50 chars for trie lookup
Special characters (\n, \t)	Strip/control chars before indexing
Unicode/Emoji	Normalize (NFKC), store as-is in trie
Rapid typing	Debounce client-side (150–300ms)
Profanity/abuse	Filter via blocklist at serving time
Prefix with no matches	Return empty array (no fallback)

Performance Benchmarks

Metric	Target	Actual
p50 latency	< 20ms	15ms
p99 latency	< 100ms	85ms
p999 latency	< 200ms	150ms
Throughput per shard	10K QPS	12K QPS
Memory per shard	< 8GB	6GB
Trie rebuild time	< 30 min	20 min
Suggestion freshness	< 4 hours	2 hours

Interview Tips

1. Start with requirements: Clarify functional vs non-functional, latency targets, scale.
2. Draw the architecture early: Client → API → Trie → Data pipeline.
3. Discuss trade-offs: Pre-computed top-K vs DFS, batch vs real-time, hash vs range sharding.
4. Handle scale: "At 100K QPS, we shard tries by prefix hash, cache hot prefixes in Redis."
5. Discuss freshness: "Batch rebuilds every 2 hours + streaming recent queries for freshness."
6. Memory optimization: Mention radix tree compression, mmap, and LRU eviction.
7. Edge cases: Multi-language, Unicode, empty prefixes, abuse filtering.