Systematic designAdvanced

Autocomplete for a search box

Scenario

Design the data structure behind a search box that, after each keystroke, shows the 10 most popular completions of the current prefix. The dictionary has 10⁷ terms with popularity counts; queries arrive at 10⁴ per second; popularity counts change over time. Cover the core structure, top-k retrieval, memory, updates and caching.

Your task

Clarify: latency budget per keystroke, whether ranking is global popularity or personalized, how fresh updates must be, alphabet size.
Choose the core structure for prefix lookup and explain the alternatives (sorted array + binary search, hash map of prefixes).
Design top-10 retrieval: naive subtree walk vs precomputed per-node top-k. Discuss the cost of each and how updates interact with precomputation.
Estimate memory for 10⁷ terms and propose reductions.
Add caching and describe how invalidation works.

Systematic ReasoningCommunicationComplexity AnalysisProblem Clarification

Work it out

Write your analysis before revealing anything. The self-check below compares it against what a strong answer contains.

Reveal

Progressive — each section builds on the previous one.

Key observation

The fix

Edge cases

Complexity

What this tests

Self-check

Tick what your analysis covered. Be honest — this feeds your readiness profile.

Clarified latency, ranking basis, freshness and alphabet before designing.Chose a trie and compared it with sorted array + binary search and a prefix hash map.Explained why a per-query subtree walk is too slow and precomputed per-node top-k.Described how count updates propagate along the term path and the growing-counts assumption.Estimated memory with numbers and proposed compression (radix tree, ids instead of strings).Added an LRU/TTL cache for short prefixes with an invalidation rule.Gave O(|p| + k) query and O(|term| · k) update.Discussed offline batch rebuild and atomic snapshot swap for scale.

0/8

Related concepts

Trie Min-Heap LRU Cache Hash Map Binary Search String