May we use cookies so Meta, Google, LinkedIn and ChatGPT see your visit and we learn which ads work? PrivacyMay we use cookies to see which pages help, and let Meta, Google, LinkedIn and ChatGPT see your visit, so we know which of our ads work? That way we spend less on ads that do not work. We do not sell your data, and the site works the same if you decline. You can change your answer at any time under Cookie settings at the foot of the page. Privacy policy
Loading...
System Design and AI Engineering, by Roni Das. 989 interactive lessons in two courses.: 770 in System Design and 219 in AI Engineering.
Start LearningSystem design interview guide
in this guide
7 parts open to everyone · 3 with a free account · 3 with the course
You can read 7 of 13 parts. A free account opens the deep dive; the course opens all of it.
Interviewers like typeahead because it forces a candidate to reason about an extreme read-latency budget. Every keystroke is a query, so the system sees several reads per search and each read must return in the low tens of milliseconds. On top of that you have to rank: returning any matching prefix is easy, but returning the best top-k completions ordered by popularity and recency is the real problem. The candidate has to separate the read path (serve precomputed answers fast) from the write path (aggregate query logs, compute popularity, and rebuild the index) and then explain how the two stay in sync. It also opens up prefix matching at scale, sharding a large term set, caching hot prefixes, and keeping trending queries fresh, which gives an interviewer many directions to probe.
This page is the free part.
₹1,111 in India$35 everywhere elseonce, for the whole course
The System Design course covers the Search Autocomplete design across a run of lessons, not one page. These 4 alone are about 119 minutes of step-by-step reading, every one with a quiz.
Always clarify these in the first 5 minutes of the interview. Do not start drawing boxes until both lists are agreed.
This guide is built on these 5 lessons. Each one teaches one piece of the Search Autocomplete (Typeahead) design above, step by step.
Lifetime access for ₹1,111 in India or $35 elsewhere. Interactive diagrams, quizzes, and 20 capstone projects to practise on.
This one question is not enough for the interview.
Each question has why it is asked, a full answer, what the interviewer listens for, the follow-ups, the common mistakes and a diagram (268 diagrams in all). A PDF you keep, junior to staff level.
Two courses by the author of this page:
770 lessons · 18 free to read
₹1,111 in India · $35 elsewhere, once
Get System DesignYou own this course
219 lessons · 10 free to read
₹1,333 in India · $35 elsewhere, once
Get Generative AI and Agentic AIYou own this course
Save your progress and get the interview checklist PDF
Google handles on the order of 8.5 billion searches per day, and it starts suggesting completions the moment you type the first letter, usually returning fresh suggestions in a few tens of milliseconds. The per-keystroke read volume is several times the search volume because most searches involve typing many characters (search count is public, the per-keystroke multiplier is estimated).
A typeahead system suggests the most likely completions for whatever prefix a user has typed so far, and it does this on every keystroke. The read path must be extremely fast because a suggestion has to come back before the user types the next character. The core trick is a trie (prefix tree) where each node stores the precomputed top-k completions for that prefix, so a lookup is O(length of the prefix) instead of a scan. Popularity comes from an offline pipeline that mines historical query logs and rebuilds the trie on a schedule. A separate fast path layers recent trends on top so spikes show up without waiting for the next full rebuild.
Where it shows up
Asked at Google, Amazon, Meta, LinkedIn, Microsoft, and most companies that run a search box. It is one of the most common system design interview questions because almost every product has a search or lookup field.
Spec sheetSearch Autocomplete (Typeahead)
worked through below, with the maths
The hard parts of this design are taught step by step in the System Design course: Cache-Aside Pattern, Database Sharding and Load Balancing.
Cache-aside is said to degrade gracefully when the cache fails. Measured, unwrapped it answered 0.0 percent of requests, and wrapped it answered 13.0, which is exactly the database's capacity.
Splitting a database across multiple servers, the nuclear option for scaling writes, and the architecture behind Instagram, Uber, and YouTube.
How traffic actually gets spread across many servers, and what breaks when it does not.
Design systems for maximum uptime, eliminate single points of failure across every layer.
all part of
System Design Masterclass
770 lessons · about 290 hours · 18 free to read
₹1,111in India, by UPI
$35everywhere else, by card or PayPal
You own this course
Continue with Cache-Aside Patternpay once,
yours for life
Live from the course bench
Real interview questions, live diagrams and measured lab results, pulled at random from the lessons. A new set every time you come back.
Show your math. Pulling numbers from thin air signals you have not thought about the load.
Search queries per day
~8.5 billion (Google, public estimate)
Widely cited public figure for Google search volume. Used as the baseline that the per-keystroke read load is derived from.
Prefix lookups per second
~600k to 2M/sec (derived)
If a typical query is typed as 4 to 6 keystrokes that each trigger a debounced lookup, the per-keystroke read rate is several times the search rate. 8.5B searches/day is about 100k searches/sec averaged, and roughly 6x for keystrokes gives the derived range. Peak is higher than average.
Distinct terms and phrases in the suggestion set
hundreds of millions to low billions (estimated)
The head of the distribution is small, but the long tail of real queries is enormous. Most systems keep only phrases above a frequency threshold, which trims a raw multi-billion set down to a servable size.
Storage for the trie with precomputed top-k
tens to low hundreds of GB (estimated)
A trie node storing k completion pointers plus scores costs more than the raw strings, but heavy compression (shared prefixes, FST encoding) keeps a servable English index in the tens of GB range, which fits in memory across a shard set.
Query log volume ingested per day
single-digit TB/day (estimated)
Every search plus metadata (timestamp, locale, result click) is logged. At billions of events per day with a few hundred bytes each, the daily aggregation input is in the terabytes.
Rebuild / update cadence
full daily + trending every few minutes (design choice)
A full trie rebuild from aggregated logs runs once or a few times per day. A lightweight streaming path updates counts for spiking queries on the order of minutes so trends surface quickly.
The client is the first line of defense. It debounces keystrokes, usually waiting 100 to 300 ms of typing pause before firing a request, and cancels in-flight requests when the prefix changes, which cuts the request count sharply. Requests hit an edge tier where a CDN or edge cache serves the hottest short prefixes directly, since a small number of one and two character prefixes account for a large share of traffic. Cache misses go to the suggestion service, which is a stateless read tier fronting an in-memory trie. Each trie node stores the precomputed top-k completions for the prefix that ends at that node, so serving a request is a walk of the prefix followed by a read of the stored list, which is O(length of the prefix) with no ranking work at query time. The trie is sharded, commonly by prefix range, and replicated for availability and read throughput. Feeding all of this is an offline pipeline that is fully decoupled from the read path. It consumes query logs, aggregates them with a batch or streaming job to compute popularity and recency scores, prunes low-frequency phrases, applies safety filters, computes the top-k at every node, and ships a new immutable trie to the serving tier via an atomic swap. A separate fast path updates counts for recently spiking queries so trends appear within minutes rather than waiting for the next full rebuild.
In a real interview, sketch this on the whiteboard before diving into any single box.
Walk through each service. The interviewer wants to hear what each one owns, not just the names.
Runs in the browser or app. Waits for a short typing pause, cancels stale requests, and caches results for prefixes the user has already seen during the session. This removes a large fraction of would-be requests before they leave the device.
Caches suggestion responses for the hottest short prefixes with a short TTL. Short prefixes are queried by almost everyone, so a small cache absorbs a disproportionate share of read traffic and protects the origin service.
A stateless, horizontally scaled service that receives a prefix, routes to the correct trie shard, walks the prefix, and returns the precomputed top-k list. It also merges in the trending fast path and applies per-request personalization if enabled.
The in-memory index. A trie, ternary search tree, or FST where each node holds the precomputed top-k completions for its prefix along with scores. Built offline and served as an immutable, atomically swapped artifact.
A batch or streaming job that reads query logs, computes popularity and recency, prunes and filters, computes top-k at each node, and produces the new trie. This is the write path and it never blocks reads.
A lightweight streaming counter (for example over the last few hours) that tracks recently spiking queries and injects them into results so trends surface long before the next full rebuild.
Applies blocklists, policy models, and quality thresholds so offensive or unsafe phrases are removed before they enter the served trie or the trending path.
prefix_topk (served trie). The read-optimized artifact. Conceptually a map from each prefix node to its precomputed top-k completions. Stored as a compressed trie or FST in memory, not as literal…
Every table for Search Autocomplete (Typeahead), its keys, and which store fits it and why.
The trie with precomputed top-k at each node. A plain trie lets you find all completions under a prefix, but that still means walking the whole subtree and then ranking, which is far too slow for millions of lookups…
7 deep dives on the parts that break at scale: The trie with precomputed top-k at each node; Why precompute top-k instead of ranking at query time; The offline aggregation pipeline.
Precompute top-k vs rank on the fly. Precomputing gives O(prefix length) reads and shares work across billions of requests, at the cost of freshness and a heavier offline build. Ranking on the fly is always…
7 decisions an interviewer expects you to defend, each with the alternative and why it loses here.
A newly built trie turns out to be bad, for example missing a whole locale, and it has already been swapped in. How do you recover?
4 follow-up questions with model answers, the interview scorecard for this question, and a mock interview on Design Search Autocomplete (Typeahead) with the AI tutor.
Production typeahead systems lean heavily on finite state transducers (FSTs) and precomputed suggesters rather than naive tries. Lucene, which powers Elasticsearch and Solr, encodes terms in an FST, a compact automaton that shares both prefixes and suffixes and can associate an output (like a weight) with each accepted string. Elasticsearch's completion suggester builds a dedicated in-memory FST at index time specifically so prefix lookups are fast, and it stores weights so results can be returned in ranked order without scanning. Google's autocomplete, by its own description, predicts queries from real historical searches and trends, applies removal policies for unsafe or sensitive predictions, and varies suggestions by language, location, and freshness, which is consistent with a log-mining plus fast-trend design. The recurring pattern across all of them is the same: pay the ranking and structure-building cost offline over aggregated query logs, serve an immutable compact automaton in memory for O(prefix length) reads, cache the hottest prefixes, and layer a fast path for what is trending now.
If any of these topics are fuzzy, the interviewer will catch it. Each lesson is 15 to 60 minutes with diagrams, code, and a quiz.
interview readiness
Three questions from this guide. Answer them without scrolling up, the way you would have to in the room.
Pay by UPI, cards or netbanking through Razorpay. Pay by card or PayPal, in US dollars. Download at once from My packs.
NEWSystem Design Hands-On
Postgres Sharding: Complete Hands-On (PgBouncer + Citus). 2 h 36 min and 20 chapters: one PostgreSQL loaded until it breaks, then four shards behind a router you write, PgBouncer and Citus, with the 139-page slide deck. The first 15 minutes are free to watch.
Free PDF · 79 pages
25 real tech interview questions, answered in full
Five from each of our AI, GenAI, Inference, Maths for ML and Forward Deployed packs. Each with a diagram and a model answer. Free by email.
free tool
Check these numbers yourself
Put in your own guesses for Search Autocomplete (Typeahead) and see requests per second, storage, bandwidth and servers, with every sum written out.
Open the Capacity EstimatorIt is really nice and good Please join the course