Design search autocomplete

Suggest the top completions as the user types into a search box.

Why interviewers ask it

It tests data structures at scale (tries), precomputing results, caching, and separating serving from data processing.

Functional requirements

Non-functional requirements

From version 1 to the final design

  1. Version 1: an SQL query: LIKE 'prefix%' ORDER BY count LIMIT 5.
  2. Version 2: an in-memory trie, searching the subtree on each request.
  3. Version 3: top-k precomputed at every node, rebuilt by a background job.
  4. Version 4: tries split across servers, edge caching, trending updates and filtering.

The design, step by step

  1. Serving: an in-memory trie (or a prefix → top-k map in Redis); a lookup just walks the prefix.
  2. Data pipeline: log searches → count them every hour or day → rebuild the trie → swap the new one in.
  3. Client: wait for a short pause in typing before asking, and cache recent prefixes; cache common prefixes at the edge.
  4. Split the trie across servers by prefix when it gets too big.

Deep dives

Common mistakes

Not true: An autocomplete box should send a request for every single keystroke, with no pause.
In fact: Most of those requests are out of date before the reply arrives. Wait a short moment after the last keystroke, and far fewer requests are sent.

In the interview

Suggestions are served from an in-memory trie where each node already stores its top-k completions, so a lookup is just walking the prefix. Search logs feed a background job that rebuilds the trie regularly. Clients wait for a pause in typing and cache results, and popular prefixes are cached at the edge.

Part of Unit 8: High-level design questions in the free System Design course.