Search Autocomplete#

Q: Why use a trie for autocomplete?

A trie indexes prefixes in O(prefix length) lookup and lets you precompute the top-K completions per prefix node, so the request returns by walking one path.

Q: How do you keep autocomplete under 100 ms?

Precompute top-K per prefix, serve from an in-memory trie close to the user, fan out queries in parallel, and avoid touching disk on the hot path.

Q: How does autocomplete handle typos?

Layer a fuzzy lookup using edit-distance tries, n-gram indexes, or a learned model that maps typo prefixes to canonical ones, then merge with exact-match results.

Q: How is the suggestion index updated?

Aggregate query logs in a streaming job, recompute top-K per prefix, and ship deltas to the serving trie. Trending boosts come from a separate short-window aggregation.

Q: How do you personalize autocomplete?

Blend global top-K with a per-user history and recent queries at query time. A learning-to-rank model reorders the merged list using context signals like location.

Problem statement (interviewer prompt)

Design the autocomplete that powers a search box. As the user types, return the top 5-10 suggestions in <100ms p99. Handle typos, multilingual queries, trending boost, personalization, and an index that updates near-real-time as new queries come in.

flowchart LR
  U([User keystrokes])
  API[Suggest API]
  T[Trie / Cache<br/>top-k per prefix]
  L[(Top-k Store)]
  AGG([Aggregator<br/>query logs -> trends])
  Q[(Query logs)]
  U --> API --> T
  T --> U
  Q --> AGG --> L --> T

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class U client;
    class API service;
    class T,L,Q datastore;
    class AGG compute;

flowchart TB
  subgraph Client[Client]
    BR([Browser / App])
    DBN[Debounce 100ms<br/>cancel on new key]
    CACHE[Client cache<br/>per session]
  end

  subgraph Edge
    GW[API Gateway / CDN edge]
    RL([Rate limit per user])
  end

  subgraph Serve[Suggest Service]
    PARSE[Normalize: lowercase,<br/>diacritics, language]
    SPL[Speller / fuzzy match<br/>edit distance ≤ 2]
    LOOK[Top-k Lookup]
    PERS([Personalize<br/>user history + locale])
    RANK([Ranker])
    AB[A/B exp]
  end

  subgraph Store[Index Store]
    TRIE[(Compressed Trie / DAWG<br/>per-prefix top-k materialized)]
    REDIS[(Redis Sorted Sets<br/>key = prefix, score = freq)]
    ES[(Elasticsearch<br/>edge_ngram fallback)]
  end

  subgraph Build[Offline Build Pipeline]
    QL[(Query logs - Kafka)]
    BATCH([Spark / Flink job<br/>n-gram counts, daily])
    DECAY[Time decay + spike detection]
    TRENDS[[Trending topics signal]]
    FILT[Safety / profanity filter]
    DEPLOY[Blue/green index swap]
  end

  subgraph Personal[Personalization]
    HIST([User history KV])
    LOC[Geo / language]
    SES[Session intent]
  end

  BR --> DBN --> CACHE
  CACHE -. miss .-> GW --> RL --> Serve
  Serve --> PARSE --> SPL --> LOOK
  LOOK --> TRIE
  LOOK --> REDIS
  LOOK -. fallback .-> ES
  PERS --> RANK
  HIST --> PERS
  LOC --> PERS
  SES --> PERS
  LOOK --> RANK --> AB --> BR
  BR -.queries+clicks.-> QL
  QL --> BATCH --> DECAY --> FILT --> DEPLOY
  TRENDS --> DEPLOY
  DEPLOY --> TRIE
  DEPLOY --> REDIS

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class BR,RL,PERS,HIST client;
    class GW edge;
    class DBN,PARSE,SPL,LOOK,AB,DECAY,FILT,DEPLOY,LOC,SES service;
    class TRIE,ES,QL datastore;
    class CACHE,REDIS cache;
    class TRENDS queue;
    class RANK,BATCH compute;

Trie design#

Each node: char + top-k results (id + score) materialized.
Lookup = walk N chars (N ≈ query length), return top-k at terminal node.
Update via offline batch (recompute) - cheap reads, daily/hourly refresh.

Latency target#

< 100 ms end-to-end (UI feels instant).
Debounce ≥ 80 ms in client; cache on client too.

Spell correction#

Symspell / BK-tree precomputed; runtime fuzzy match within edit distance ≤ 2.

Real-time stream finds spikes (e.g. breaking news) → boost score immediately via Redis overlay.

Index swap#

Build new trie / Redis snapshot offline; atomic swap by flipping a pointer / namespace.

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag	Concept	What it is	Page
`HLD`	CDN	edge caching for static assets	cdn
`HLD`	API gateway / BFF	single ingress, auth, rate limit, routing	api-gateway
`HLD`	Pub/Sub & message brokers	topics, consumer groups, delivery semantics	pub-sub-pattern
`HLD`	Batch & stream processing	Lambda vs Kappa, watermarks, windows	batch-stream-processing
`LLD`	Data structures & complexity	Big-O, common DS, latency numbers	data-structures-complexity
`LLD`	Concurrency primitives	mutex, semaphore, RW lock, atomic, CAS	concurrency-primitives

Quick reference#

Functional#

For a typed prefix, return top-k suggestions ordered by score.
Multi-language, diacritic-insensitive, fuzzy tolerant.
Personalize by user/locale.
Reflect trending queries.

Non-functional#

p99 latency < 100 ms incl. network.
10× read amplification of search QPS (1 query = 5-10 suggest calls).
Update freshness: 1 hr for popularity, seconds for trending.

Capacity#

100M DAU × 50 searches/day × 8 suggest calls = 40B/day = 460k/s avg, 2M/s peak.
Trie footprint: 100M queries × 30 B → 3 GB raw, ~1 GB compressed.
Per-prefix top-k (5): a few hundred MB; fits per shard in RAM.

API#

GET /suggest?q=ne&user=...&locale=en-US -> [{text, score}, ...]

Data model#

Offline: (query, frequency) from logs, decayed by time.
Per-prefix top-k materialized.
Optional: per-user query history.

Trade-offs#

Trie is fast but memory-heavy; works great when materialized top-k.
Elasticsearch edge_ngram simpler, slower.
Real-time updates vs offline batch: hybrid is common.
Personalization can leak privacy (typing) - anonymize and minimize.

Refs#

Twitter typeahead, Etsy autocomplete, Pinterest autocomplete blog, Lucene completion suggester, ByteByteGo "Design typeahead".

FAQ#

Why use a trie for autocomplete?#