## Scenario Design a low-latency typeahead service. As a user types a prefix, return up to 10 suggestions ranked by a configurable popularity score, then lexicographically for ties. Suggestions and scores change over time. Cover API behavior, normalization, offline and near-real-time updates, index structure, sharding, caching, ranking, typo policy, availability, abuse controls, and observability. No scale is supplied; identify the measurements that drive architecture. ### Constraints & Assumptions - The baseline supports prefix matching only, not arbitrary substring or fuzzy matching. - Input and indexed terms pass through the same locale-aware normalization version. - The response must be deterministic for one index version. - Empty and overly long prefixes are rejected or handled by an explicit popular-default policy. - Exact top 10 is required after score increases, score decreases, insertions, and tombstones; a base top-10 list alone cannot refill a removed result from base rank 11. ### Clarifying Questions to Ask - What query rate, corpus size, update rate, locale count, and latency target apply? - Are suggestions global, tenant-specific, personalized, or safety-filtered? - How fresh must popularity changes be? - What minimum prefix length and maximum result count protect the service? - Must ranking be explainable or versioned? ```hint Precompute top results at prefix nodes A trie or compressed finite-state structure can attach a bounded top list to each prefix, turning reads into prefix traversal plus a small result fetch. ``` ### What a Strong Answer Covers - Shared normalization and deterministic ranking. - A compact prefix index with an exact ordered refill path, a versioned build pipeline, and an incremental overlay that shadows changed or tombstoned base terms. - Prefix-aware sharding, replicated serving, cache keys, negative caching, and hot-prefix protection. - Safety filtering, rate limits, and a clear boundary for personalization or typo tolerance. - Freshness, index-version, cache, latency, and relevance metrics with rollback. ### Follow-up Questions 1. Why can hashing the complete suggestion make prefix queries difficult to shard? 2. How would you refill exactly when an overlaid base top result decreases or is deleted? 3. What changes when typo-tolerant suggestions become required?