GamifiedGamified challengesPracticeRaceLeaderboardPricing

Learn data structures by watching them move, then doing it yourself. Press M anytime to toggle sound.

A product of Amypo Technologies, Coimbatore.

Learn

  • All topics
  • Learning path
  • How it works
  • About dotprep

Practice

  • Practice arena
  • Daily challenge
  • Gamified challenges
  • Race mode
  • Leaderboard

Interview prep

  • Java interview
  • Coding questions
  • Company questions
  • System design
  • Jobs & careers

You

  • Dashboard
  • Settings
  • Pricing
  • Create account

© 2026 dotprep

Content last updated 20 November 2026

GamifiedGamified challengesPracticeRaceLeaderboardPricing
System designDesign search autocomplete

Design search autocomplete

Top-k suggestions per prefix with tries, precomputed results, sharding and an offline aggregation pipeline.

advanced 12 min read 4 interview questions

On this page

1/6
  1. 01Requirements and estimates
  2. 02A trie with cached top-k
  3. 03Data pipeline
  4. 04Scaling and latency
  5. 05Interview questions
  6. 06Quick check
Back to top

Requirements and estimates

  • As the user types, show the top 5–10 most popular queries starting with the prefix.
  • Respond within ~100 ms, since it fires on almost every keystroke.
  • Popularity can be a day behind; trending terms may update more often.
  • Filter offensive or unsafe suggestions.
text
10M daily users × 10 searches × ~6 keystrokes ≈ 600M requests/day ≈ 7k/s (peak ~20k/s)

A trie with cached top-k

A trie stores queries character by character, so all queries with a prefix live under one node. Walking to the prefix node is O(length of prefix). Searching the whole subtree for the most popular completions on every keystroke would be too slow, so each node stores its top-k completions, computed when the trie is built.

java
class Node {
Map<Character, Node> children = new HashMap<>();
List<String> top = new ArrayList<>(); // best k queries under this prefix, precomputed
}
List<String> suggest(String prefix) {
Node n = root;
for (char c : prefix.toCharArray()) {
n = n.children.get(c);
if (n == null) return List.of();
}
return n.top; // O(prefix length), no subtree search
}

Storing top-k at every node costs memory but turns the lookup into a short walk. Limiting prefix length (say 20 characters) and compressing chains (a radix tree) keeps it manageable.

Data pipeline

  1. Collect: search queries are logged to a stream.
  2. Aggregate: a batch job (hourly or daily) counts query frequencies, with time decay so stale terms fade.
  3. Build: workers build the trie with top-k per node and serialize snapshots.
  4. Serve: suggestion servers load the snapshot into memory and swap atomically to new versions. No writes happen on the serving path.

Scaling and latency

  • Replicate the in-memory trie across many servers; if it's too big, shard by prefix range (a–f, g–m…), splitting busy ranges further since prefixes aren't evenly popular.
  • Cache responses for short prefixes, which are few and extremely hot, at the CDN or the browser.
  • On the client: debounce keystrokes (wait ~100 ms) and reuse earlier results while the user keeps typing the same word.

Serving and building suggestions

1/5
Search boxdebouncedEdge cacheshort prefixesSuggest servicetrie in memoryQuery logsAggregatorhourly countsTrie buildertop-k per nodeSnapshots

The user types "de". The very common short prefix is answered straight from the edge cache.

See it animated

TrieRadix treeCount-min sketchBinary heap

Interview questions

Try answering out loud first, then open the model answer.

Q1Why a trie rather than a database LIKE query?intermediate

LIKE 'prefix%' on billions of rows, then sorting by popularity, is far too slow at thousands of requests per second. A trie groups every completion of a prefix under one node, and caching the top-k there makes each lookup a walk of a few characters in memory.

Q2Why precompute top-k at each node?intermediate

Without it you'd traverse the whole subtree under the prefix and sort by frequency on every keystroke, which for a short prefix like "a" means millions of nodes. Precomputing during the offline build makes reads O(prefix length) at the cost of memory and rebuild time.

Q3How do you keep suggestions up to date?intermediate

Rebuild from aggregated logs on a schedule (daily or hourly) and atomically swap the snapshot on servers. For trending topics, run a smaller fast pipeline (streaming counts over the last hour, such as a count-min sketch) and blend its results in.

Q4How would you shard the trie?advanced

By prefix: route queries by their first character or two to the servers owning that range, and split popular ranges more finely based on observed traffic. Each shard is also replicated for availability and read throughput.

Quick check

Question 1

1.Lookup cost in a trie with cached top-k is about…

Question 2

2.Where do suggestion frequencies usually get computed?

Question 3

3.Debouncing on the client reduces…

0 of 3 answered

Design a news feed
Log inStart free