Design a Shopping Search Bar with Autocomplete

# Design a Shopping Search Bar with Autocomplete Design the search bar for a shopping application. As a user types, the system should return low-latency query suggestions or product completions. After submission, it should retrieve relevant products while respecting availability and other agreed filters. Explain where a trie is useful, where a search engine such as Elasticsearch is useful, and how data moves from the product catalog and search behavior into both serving paths. ### Constraints & Assumptions - Autocomplete latency is more sensitive than full search latency and may tolerate slightly stale suggestions. - Product title, category, descriptive text, availability, and searchable attributes can change independently. - Popular prefixes may create hot keys and sharp traffic bursts. - Exact catalog size, query rate, locales, ranking goals, personalization, and staleness limits should be clarified. ### Clarifying Questions to Ask - Should autocomplete suggest past queries, products, categories, brands, or a labeled mixture? - Must out-of-stock products be removed immediately from suggestions and full results? - Which filters and sort orders must full search support? - Are spelling correction, synonyms, personalization, and multiple languages in scope? - How should unsafe, manipulated, or very rare queries be handled in suggestions? ### What a Strong Answer Covers - Separate contracts for prefix suggestions and submitted-query product search, including ranking and freshness expectations. - A catalog-change pipeline that updates the search index and tracks lag, replay, and failed documents. - A search-engine mapping and query plan for analyzed text, exact attributes, filters, availability, and stable pagination. - A compact prefix-serving structure such as a weighted trie or precomputed prefix table, with bounded candidates at each node. - Suggestion generation from eligible catalog data and aggregated query behavior with normalization, abuse filtering, and versioned publication. - Multi-layer caching, hot-prefix protection, request cancellation, and graceful fallback when suggestion or search services are unavailable. - Relevance and quality evaluation for both autocomplete and full search, including stale or unavailable products. - Sharding, replication, observability, privacy boundaries, and a clear explanation of why one storage structure does not need to serve both jobs. ### Follow-up Questions 1. How do you update autocomplete rankings without rebuilding and replacing the entire trie on every query? 2. A product becomes unavailable while its title remains a highly ranked suggestion. Where should that be corrected? 3. How would you prevent the prefix `a` from becoming a cache and CPU hot spot? 4. What pagination strategy avoids duplicates if the search index changes between pages? 5. Which offline and online signals show that autocomplete improves shopping outcomes rather than merely increasing suggestion clicks?