Design Autocomplete / Typeahead (Frontend System Design)

Autocomplete (also called typeahead) is a feature that shows suggested completions while the user is still typing. A prefix is the first part of a word: "rea" is a prefix of "react". A query is the text the user types to search. Latency is the wait between an action and its result. A trie (said "try") is a tree of letters that makes prefix lookups fast; we build one below.

This is a classic "frontend system design" question. It suits frontend developers well, because half of the interesting choices are made in the browser.

1. Requirements

Functional

• While the user types, show a short list (5 to 10) of suggestions that match the prefix, or match roughly (a fuzzy match finds results even when the text has small mistakes, such as "raect" for "react").
• The user picks with the mouse or the keyboard. Pressing Enter starts the search.
• Highlight the part that matches. When the box is empty and has focus, show recent or popular searches.

Non-functional

• Latency (wait time): suggestions should appear within about 100 to 200 ms after a keystroke. The whole response should feel faster than 300 ms.
• Scale: imagine 100,000 people typing at the same moment, each pressing about 3 keys per second. If every keystroke sent a request, that would be 100,000 × 3 = 300,000 requests per second.
• Relevance: sort by popularity, how recent a term is, and personal history.
• Accessibility (people who use a keyboard or a screen reader can use it), resilience (it still works when something fails) and correctness. Never show results for an old query.

2. Frontend design

State and data flow

keystroke ─▶ (min length?) ─▶ debounce 150–300 ms ─▶ cache hit? ─yes─▶ show                                                         │no                                                         ▼                                          abort previous request ─▶ fetch /suggest?q=… ─▶ store in cache ─▶ show

Fewer requests

• Minimum length: do not search for 0 or 1 characters. The result lists would be huge and not useful. Often you start at 2 or 3 characters. For an empty input, show recent or popular searches from local data.
• Debounce (about 150 to 300 ms): wait until the user pauses. Debouncing is a technique that delays an action until a set time has passed with no new input, and restarts the timer on each new keystroke. Then typing "react" quickly sends one request, not five. A shorter wait feels faster but sends more traffic. Tune it with real data. (Difference in one line: debounce waits for a pause and then runs once; throttle runs at most once per time period, however much the user types.)
• Cache per query: a cache is a place where you keep answers you already have, so you can reuse them. Keep a Map (or an LRU cache, which throws away the least recently used items when it is full; see Lesson 07) of prefix → results. When the user presses backspace from "reac" to "rea", the answer is instant. You can also reuse the cache of a longer prefix. For example, if "re" returned all matches (fewer than the page size), you can filter them in the browser for "rea".
• HTTP caching: make GET /suggest?q=rea cacheable. Cache-Control: public, max-age=300 is a response header that lets any cache keep the answer for 300 seconds (5 minutes). Then the CDN (a network of servers close to users that keep copies of responses) and the browser can share popular prefixes (Browser Contract, Lesson 05).
• Prefetch (load before it is needed) the likely next results only if your data shows it helps. Usually it does not.

Correctness: always show results for the latest input

Responses can arrive in the wrong order (Debugging, Lesson 05). This is a race condition: the result depends on which request happens to finish first. The fix is to cancel old requests and ignore their results. AbortController is a browser object that cancels a fetch request; its signal is passed to fetch.

function useSuggestions(query: string) {  const [state, setState] = useState<{ items: string[]; loading: boolean }>({ items: [], loading: false });  const cache = useRef(new Map<string, string[]>());  useEffect(() => {    const q = query.trim().toLowerCase();    if (q.length < 2) { setState({ items: [], loading: false }); return; }    const hit = cache.current.get(q);    if (hit) { setState({ items: hit, loading: false }); return; }    const controller = new AbortController();    setState((s) => ({ ...s, loading: true }));    const timer = setTimeout(async () => {                       // debounce      try {        const res = await fetch(`/api/suggest?q=${encodeURIComponent(q)}`, { signal: controller.signal });        if (!res.ok) throw new Error(`HTTP ${res.status}`);        const items: string[] = await res.json();        cache.current.set(q, items);        setState({ items, loading: false });      } catch (e) {        if ((e as Error).name !== "AbortError") setState({ items: [], loading: false });      }    }, 200);    return () => { clearTimeout(timer); controller.abort(); };   // a newer keystroke cancels this one  }, [query]);  return state;}

IME composition

Some users type Chinese, Japanese or Korean. Some mobile keyboards work the same way. They use an IME (input method editor), a tool that builds one character in several steps: the user types sounds, sees a list of candidates, and then picks one. It is wrong to search at every middle step. Listen for the compositionstart and compositionend events (the browser fires them when an IME starts and finishes building text). Search only when the composition is finished. In other words, treat onChange during composition as "not ready yet": keep updating the text in the input, but do not start a search until compositionend fires.

Keyboard interaction and accessibility

Autocomplete is a well-known combobox pattern (a text box combined with a list of choices). A screen reader is software that reads the page aloud for blind users. ARIA (Accessible Rich Internet Applications) is a set of HTML attributes (role, aria-*) that describe a page to assistive tools such as screen readers. Use the ARIA combobox roles so that screen readers announce it correctly. In the code, aria-activedescendant names the option that is "active" while keyboard focus stays in the input, and a live region (aria-live) is an area whose changes the screen reader announces:

<input  role="combobox"  aria-expanded={open}  aria-controls="suggest-list"  aria-autocomplete="list"  aria-activedescendant={activeIndex >= 0 ? `opt-${activeIndex}` : undefined}  value={query}  onChange={(e) => setQuery(e.target.value)}  onKeyDown={handleKeys}/><ul id="suggest-list" role="listbox">  {items.map((s, i) => (    <li key={s} id={`opt-${i}`} role="option" aria-selected={i === activeIndex} onMouseDown={() => choose(s)}>      <Highlight text={s} query={query} />    </li>  ))}</ul><div aria-live="polite" className="sr-only">{items.length} suggestions available</div>

Build these keyboard actions:

Also do these things:

• Use onMouseDown (not onClick) on the options. A click is made of mouse-down and then mouse-up. The input's blur event (the event that fires when it loses focus) happens between them and would close the list before the click is counted.
• Announce the number of results in a polite way.
• Support touch.
• Use enough colour contrast for the highlight.
• Do not trap focus (the user must be able to leave the box with the keyboard).

UI states

Design every state:

• Empty: show recent or popular searches.
• Loading: keep it quiet. To avoid flicker, show a spinner only after about 150 ms.
• No results.
• Error: fall back to a plain search. Do not block the user from searching.
• Offline.

Safe highlighting (security)

To highlight matched text, people are often tempted to use dangerouslySetInnerHTML (the React property that puts a raw HTML string into the page) with <mark>. Do not do this. Suggestion text from a database can contain markup, which can lead to XSS (cross-site scripting: an attack where a page runs a script written by the attacker). Instead, split the string into matched and unmatched text pieces. Then render <mark> elements with React. This way everything is escaped (special characters are made harmless) (Browser Contract, Lesson 07).

3. Backend design: answering prefix queries fast

The question the backend must answer is "give me the top 10 completions for this prefix". Here are the options.

Option A: a database LIKE 'prefix%'

CREATE INDEX queries_prefix ON search_queries (lower(text) text_pattern_ops);SELECT text FROM search_queries WHERE lower(text) LIKE 'rea%' ORDER BY popularity DESC LIMIT 10;

An index is an extra structure the database keeps so it can find rows without reading the whole table. A B-tree is the default index type; it keeps values in sorted order. With text_pattern_ops (a PostgreSQL option that lets a B-tree index serve LIKE 'prefix%' even when the database uses a language-aware sort order), it can find a prefix match. But sorting all matches by popularity can be slow for short prefixes, because "a%" matches a huge number of rows. This is fine for small data sets and internal tools.

Option B: a search engine

A search engine is software built to search text quickly and rank the results. Elasticsearch/OpenSearch (with its completion suggester or edge n-grams, which index the beginning pieces of each word), Typesense and Algolia already give you prefix matching, ranking, typo tolerance and filters. This is a good choice when you need fuzzy matching and rich ranking, and you do not want to build them yourself.

Option C: a trie in memory (the classic answer)

A trie (prefix tree) stores strings one character at a time. Every path from the root spells a prefix. To find the completions of rea, you walk 3 nodes and then collect the best words below them. Each node can keep its top-k suggestions (the best k, for example the best 5) by popularity, worked out ahead of time. Then a lookup takes O(length of the prefix) time, no matter how big the data set is. (O(n) notation says how the work grows with the input size n; here it grows only with the typed length, not with the number of stored words.)

class Trie {  constructor(k = 5) { this.root = { next: new Map(), top: [] }; this.k = k; }  insert(word, score) {    let node = this.root;    this._bump(node, word, score);    for (const ch of word) {      if (!node.next.has(ch)) node.next.set(ch, { next: new Map(), top: [] });      node = node.next.get(ch);      this._bump(node, word, score);          // every prefix node remembers its best completions    }  }  _bump(node, word, score) {    const i = node.top.findIndex((e) => e.word === word);    if (i >= 0) node.top[i].score = score; else node.top.push({ word, score });    node.top.sort((a, b) => b.score - a.score || a.word.localeCompare(b.word));    if (node.top.length > this.k) node.top.length = this.k;  }  suggest(prefix) {    let node = this.root;    for (const ch of prefix) {      node = node.next.get(ch);      if (!node) return [];    }    return node.top.map((e) => e.word);        // already ranked: O(prefix length)  }}const t = new Trie(3);[["react", 90], ["reactive", 40], ["read", 70], ["real", 60], ["redux", 80], ["red", 20]]  .forEach(([w, s]) => t.insert(w, s));console.log(t.suggest("rea").join(","));    // react,read,realconsole.log(t.suggest("re").join(","));     // react,redux,readconsole.log(t.suggest("red").join(","));    // redux,redconsole.log(t.suggest("zzz").length);       // 0

Memory: a plain trie with millions of strings is big, because it has many small nodes. You can make it smaller in these ways:

• Use a compressed (radix) trie, which joins chains of single-child nodes into one node that holds a whole string piece.
• Keep only the top-k per node, not every completion.
• Keep only queries that are popular enough.
• Use a finite state transducer (a compact graph that maps strings to values; Lucene, the engine inside Elasticsearch, uses it).

The simplest "built ahead of time" version is a hash map (a structure that finds a value from its key in constant time) from every prefix to its top-k list. It works well if you limit the prefix length (for example to 20).

How the data gets there

Suggestions come from query logs (records of what people really search for) and from catalogue data (such as product names).

search logs ─▶ stream/batch aggregation (count queries, decay by recency, filter spam/PII/offensive; PII is personally identifiable information, such as names and emails)            ─▶ build trie or prefix map offline (hourly/daily; incremental updates for trending terms)            ─▶ publish snapshot ─▶ suggestion servers load it in memory (swap atomically)

• Do not change the trie after every search. Count the searches and rebuild it from time to time. Add a small "trending" layer for terms that rise fast.
• Remove sensitive or unsuitable queries, such as personal data and offensive words.
• Personalisation (adjusting results to one user): mix global popularity with the user's own history. Do this by re-sorting a larger list of candidates, on the server or in the browser.

Ranking

Ranking means putting the best suggestions first. A simple score is: popularity (counted so that old searches count less, called decay) times relevance to the context (category, location, language), plus boosts for the user's own history. You can add a little randomness to try new suggestions. Keep the score easy to explain and to test.

Typos and fuzziness

An exact prefix match fails on "raect". You have these options:

• Edit-distance matching. Edit distance is the number of single-letter changes (add, delete, replace) needed to turn one word into another; "raect" to "react" is 2 changes (or 1 if swapping two letters counts as one). Limit it to 1 or 2 edits.
• n-gram indexes (indexes of short pieces of words, such as the 3-letter pieces "rea", "eac", "act").
• Phonetic keys (codes that make words that sound alike match, such as Soundex).
• A BK-tree (a tree that stores words by their edit distance to each other, so a search can skip most words).
• The fuzzy suggester of a search engine.

Use fuzzy matching only when there are few exact matches, because it costs more.

4. Scaling and delivery

• CDN and cache: popular prefixes repeat all the time. GET /suggest?q=re with Cache-Control: public, max-age=300 is served by the CDN for most of the traffic. The origin server (your own server behind the CDN) mostly sees the rare queries (the "long tail").
• Stateless suggestion servers (they keep no user data between requests, so any server can answer any request) hold the structure in memory. Add more servers behind a load balancer (a server that shares requests between them). For very big data, split the data (shard it) by the first characters or by language or tenant, and route requests to the right part.
• Hot prefixes (very common prefixes such as "a" or "the") are cached for a long time and handled at the edge (the CDN servers closest to the user).
• Rate limit (cap the number of requests allowed per time period) each client and each IP (Lesson 02). Debounce lowers the normal load. Limits stop abuse.
• Latency budget (how many milliseconds each step may use): network 30 ms + server 5 ms + render 10 ms. This is easy when the lookup is in memory.
• Failure: if the service is slow or down, fail softly. Hide the suggestions and let the user type and search as usual. Set a timeout of a few hundred ms in the client.
• Privacy: do not log full keystroke streams that are linked to a person. Log finished searches. Handle the logs of the suggest endpoint with care.

5. API

GET /v1/suggest?q=rea&limit=8&lang=en→ 200 OKCache-Control: public, max-age=300{ "query": "rea", "suggestions": [ { "text": "react", "highlight": [0, 3] }, { "text": "read", "highlight": [0, 3] } ] }

Send back the original query, so the client can check that it matches the current input. Check q and limit and cap their size. Answer 400 for abusive input.

Common mistakes

1. A request on every keystroke, with no debounce, no cache and no minimum length.
2. Not cancelling or ignoring old responses. Results then flicker or show the wrong query.
3. Ignoring IME composition. This breaks the input for Chinese, Japanese and Korean users.
4. Using onClick for options. The input's blur happens first and wins.
5. Highlighting with dangerouslySetInnerHTML.
6. No ARIA combobox roles and no keyboard support.
7. Scanning the database with LIKE '%…%' for every query.
8. Updating the suggestion index at once after every search, and letting sensitive queries become suggestions.
9. No soft failure when the suggestion service breaks.

Interview questions

Key takeaways

• Frontend: minimum length, debounce, cache by prefix, cancel old requests, handle IME, full keyboard support and ARIA combobox roles, safe highlighting, and clear states for every case.
• Backend: work out the top-k for each prefix ahead of time (trie or prefix map). Build it offline from counted logs. Serve it from memory. Cache popular prefixes at the CDN.
• Use a search engine when you need fuzzy, typo-tolerant matching. Add fuzziness only a little.
• Rank by popularity that fades with age, plus context. Filter sensitive terms. Protect the service with rate limits and fail softly.

What's next

Lesson 07: Classic Mini-Problems. We finish with four short designs that you can build in an afternoon and explain in five minutes: an LRU cache, idempotent payments, a job queue with retries and backoff, and feature flags.