Home / Blog / System Design Autocomplete: Interview Talk Track

System Design Autocomplete: Interview Talk Track

Published 2026-10-16 · Luna Interview

"Design autocomplete" (typeahead / search suggestions) is a classic system design prompt because it mixes prefix search, ranking, low latency, and large dictionaries. The risk is diving into trie minutiae and never covering ranking or scale. This system design autocomplete interview talk track keeps you organized for about 45 minutes.

Formats differ by company and level. Ask whether they want a client-server product design or a deep dive on the index.

1. Clarify requirements (5 minutes)

Scope out loud:

"I'll design prefix-based suggestions as the user types: return top-k completions quickly, ranked by popularity, with optional personalization later. I'll treat full search results pages as out of scope unless you want that."

Functional

• User types a prefix; system returns top-k suggestions
• Suggestions update as the prefix grows
• Support a large dictionary of phrases/queries
• Optionally boost personalized or trending terms

Non-functional

• Latency: tens of milliseconds for suggestions
• High read QPS; writes (new queries / counts) can be slightly delayed
• Availability over perfect freshness for counts
• Multilingual / unicode if mentioned—ask

Ask: "k is 5–10? Do we need typo tolerance in v1?"

2. Back-of-envelope (3 minutes)

Keep assumptions explicit:

"Assume 100 million unique queries, average length 20 characters, and 50,000 suggestion requests per second at peak. The hot path is reads by prefix; count updates can be batched."

Estimate index size at a high level (trie nodes or prefix→list entries) so you show you're thinking about memory.

3. High-level architecture (8 minutes)

Name components:

1. Client — debounced keystrokes, cancel in-flight requests
2. API / suggest service — auth, rate limits, fetch top-k
3. Prefix index — trie, sorted prefix table, or search engine prefix fields
4. Ranking data — query frequency, recency, maybe ML scores
5. Cache — popular prefixes at the edge or in Redis
6. Offline pipeline — aggregate logs into counts and rebuild/merge index

Flow: keystroke → suggest service → cache → index → rank → return k strings.

4. Core data structure discussion (10 minutes)

Compare options out loud:

A strong interview default:

"I'll store, for each prefix (up to a max length), a precomputed top-k list by frequency. At query time we look up the prefix—O(1) or O(length)—and return the list. An offline job refreshes the lists from aggregated search logs."

Mention tries if the interviewer wants algorithmic depth; mention precomputed top-k if they want systems depth. Often both: trie or prefix map pointing to top-k.

5. Ranking (5 minutes)

Start simple:

• Frequency of the full query over a time window
• Break ties by lexicographical order or recency
• Later: personalization (user history), locale, trending boosts

Say how scores get into the index: batch jobs every few minutes/hours, not on every keystroke.

6. Caching and latency (5 minutes)

• Cache top prefixes ("a", "ap", "app") aggressively
• Client debouncing (e.g. 50–100 ms) to cut QPS
• Limit prefix length stored (e.g. first 20 chars)
• CDN/edge cache for anonymous popular prefixes if product allows

7. Scaling and failure modes (5 minutes)

8. Closing tradeoffs

End with two explicit tradeoffs:

"Precomputing top-k per prefix optimizes read latency at the cost of memory and slower visibility of brand-new viral queries. A pure trie with dynamic heaps per node is more flexible but harder to operate at this QPS."

Soft practice note

System design interviews reward structured narration under time pressure. If you want a structured way to rehearse talk tracks and stay composed, Luna Interview is built for rehearsal and prep—before the interview, not as a way around the rules during one.

45-minute checkpoint table

Stay at the depth your interviewer steers toward. Autocomplete is won by clear prefix→top-k reasoning, not by naming every possible data structure.

Rehearse with an AI interview copilot, then browse commonly reported interview questions.