Design a Search Query Auto-Correction

Problem statement

Design a search query auto-correction system for a large e-commerce platform. When a user types a query such as "wireless headfones" or "iphone 15 pro max cse", the system must detect the misspelling, compute the most likely intended correction, and either silently rewrite the query or display a "Did you mean...?" suggestion — all within a latency budget that does not degrade the search experience.

This is not a standalone spell-checker bolted onto a text editor. It is a production search infrastructure component that sits in the critical path between the user's keystroke and the search results page. Every millisecond of correction latency directly delays product discovery and revenue. Amazon has publicly stated that search contributes to roughly 35% of its revenue through product discovery, and a 100 ms delay in page load has been associated with a measurable revenue impact. The correction service must therefore be fast, accurate, and resilient.

Why the problem is distinctive

A generic spell-checker operates on a static dictionary and tolerates hundreds of milliseconds of latency. An e-commerce correction service faces constraints that generic tools do not:

1. Domain vocabulary. Product names, brand names, model numbers, and seller-specific terms are absent from any standard dictionary. "Nike Air Max 270" is not a misspelling of "Nike Air Max 27O", but a naive edit-distance checker might flag the zero. The system needs a domain-aware lexicon that includes millions of product titles, brand registries, and category taxonomies.

1. Latency budget. The correction must complete within 20–50 ms at p99 to fit inside the overall search response budget of 200–300 ms. There is no time for a round trip to a large language model unless the model is cached locally or served from an edge inference endpoint.

1. Ambiguity. A query like "apple" could mean the fruit, the technology company, or a brand of headphones. The correction engine must weigh query context, category priors, and user session history before committing to a rewrite.

1. Feedback loop. Unlike a static dictionary, the correction system must learn from user behavior: did the user click the "Did you mean" link, or did they re-type the original query? This signal feeds back into the correction model.

1. Multilingual and locale-specific rules. German compound words ("Handyhülle"), French accents ("café" vs "cafe"), and Japanese transliterations each require different tokenization and distance metrics.

The four architectural planes

1. Correction plane: edit-distance computation, candidate generation, ranking, and the final accept/reject decision.
2. Lexicon plane: dictionary construction, product-name indexing, brand registries, synonym stores, and locale-specific vocabularies.
3. Learning plane: query-log mining, reformulation detection, click-through feedback, A/B testing, and model retraining.
4. Serving plane: caching, API gateway, rate limiting, multi-region deployment, and graceful degradation.

A strong interview answer keeps these planes separate. The correction plane must remain fast even when the learning plane is retraining models. The lexicon plane must be updatable without restarting the serving plane. The serving plane must degrade gracefully when the learning plane is unavailable.

Public operating baseline versus design assumptions

Google processes approximately 8.5 billion searches per day, which is roughly 99,000 queries per second. Its "Did you mean?" feature, described by Peter Norvig in the canonical essay "How to Write a Spelling Corrector," uses a combination of edit distance and query-log frequency. Amazon processes billions of product searches annually across 310 million active customer accounts. Etsy has published engineering blog posts describing its typo-tolerance pipeline using edit distance over a curated product dictionary. Walmart Labs has described query understanding as a core pillar of its search relevance stack.

For capacity planning in this answer, we assume a mid-to-large e-commerce platform with 50 million monthly active users, 10 million daily active users, 500 million search queries per day, and a 5× peak multiplier during flash sales or holiday events. Unless a number is tied to a citation, it is a stated design assumption.

What the interviewer is really testing

The interviewer wants to see whether you can separate the linguistic problem (edit distance, language models) from the systems problem (latency, caching, feedback loops, multilingual dictionaries). A candidate who only describes Levenshtein distance without addressing how to serve it at 15,000 QPS with a 50 ms p99 budget will not pass a Staff-level bar. Conversely, a candidate who draws boxes without explaining why BK-trees outperform brute-force scan for metric-space lookup will miss the algorithmic depth the question demands.