Design a Typeahead Service on an In-Memory Trie, Then Scale It Without New Services

Design a typeahead (search autocomplete) service. As a user types into a search box, the client sends the current prefix, and the service returns a short, ranked list of keywords that begin with that prefix. The interviewer framed the scale deliberately: start from a relatively low load and do not design for a very large number of concurrent users, but the service must be able to scale up as demand grows. Within that framing, build the suggestion index yourself as an in-memory trie owned by the service, rather than relying on an external search engine's built-in completion suggester. The second half of the interview asks how that trie scales out without introducing any other external service. The source gives no numbers for the starting scale, so choose and state your own. ### Clarifying Questions - How many suggestions should one response contain, and are they the same for every user or personalized? - What defines a keyword's score (search counts, recency, clicks on suggestions), and how soon after a score changes must suggestions reflect it? - Where do new keywords and score changes come from: a log of past searches, periodic batches, or direct writes? - What starting numbers should I assume for distinct keywords, peak requests per second and suggestion latency, and how much growth should the first version absorb? - Should matching be case-insensitive, and must multi-word or non-Latin keywords be supported? ### Part 1 — Requirements and scale State the functional and non-functional requirements, put rough numbers on the starting scale, and estimate whether the whole keyword index fits in one server's memory. Explain why an in-memory trie is a reasonable choice at this scale compared with a search engine's completion feature. ```hint Size the index before choosing Estimate how many trie nodes the keyword set produces and what each node has to hold; that number decides whether one process can serve everything. ``` #### What This Part Should Cover - Functional requirements, including ranking and freshness expectations - Non-functional targets: latency, availability and the growth path - A memory estimate for the index - The build-versus-buy trade-off at a low starting scale ### Part 2 — Trie internals and keyword storage Describe how the trie is implemented: what each node stores, how children are represented, how keywords and their scores are stored, and how the service returns the top suggestions for a prefix without walking the whole subtree below it. ```hint Short prefixes are the expensive ones A one-letter prefix sits above a large share of all keywords. Think about what a node could hold ahead of time so that serving it costs no more than serving a long prefix. ``` #### What This Part Should Cover - Node layout and child representation, with their memory cost - Where keyword strings and scores live, and how duplication is avoided - How the top suggestions for a prefix are produced, and the cost per query ### Part 3 — Read path, score updates, rebuild and hot swap Walk through the read path from a keystroke to the response, and the write path from a change in a keyword's popularity to updated suggestions. Explain how keyword scores are updated, when you rebuild the trie from scratch instead of updating it in place, and how you swap a freshly built trie into service without dropping or blocking requests. ```hint Readers and the writer Decide whether a request can ever see a trie that is in the middle of being modified, and what your answer costs in memory and in freshness. ``` #### What This Part Should Cover - The read path and its latency budget - Incremental score updates and their effect on the suggestions stored for each prefix - A full rebuild followed by a hot swap that does not disturb in-flight requests - Validation and rollback when a rebuild goes wrong ### Part 4 — Scaling the trie without new external services Demand has grown beyond what one server should handle. Without adding any other external service, such as a separate search cluster, cache cluster or coordination service, how do you scale the trie? Cover replication, sharding, how a request for a prefix reaches the data it needs, and uneven load across shards. ```hint Count the shards per request For each way of splitting the keywords, work out how many shards a single prefix request has to touch, and what happens to prefixes that are shorter than your split. ``` #### What This Part Should Cover - Replication for read throughput and availability - The sharding key, request routing, and the per-request cost of that choice - Skewed and hot prefixes, and how shards are split or rebalanced - How rebuilds and score updates work once the trie is sharded ### What a Strong Answer Covers - A design sized to the stated low starting scale, with a credible path to scale up - Quantitative estimates behind the memory and latency claims - Explicit freshness and consistency trade-offs: what users see while updates or swaps are in flight - Failure handling for crashed instances, bad rebuilds and overloaded shards - Observability of latency, index freshness and suggestion quality ### Follow-up Questions - A keyword must disappear from suggestions immediately, for example after a takedown request. How do you do that without waiting for the next rebuild? - How would you add per-region or personalized suggestions without multiplying memory by the number of regions or users? - At what point would you move to an external search engine's completion feature, and how would you migrate without downtime? - How would you still return useful suggestions when the typed prefix contains a typo?