Search Autocomplete with Top-3 Ranked Suggestions

Problem Statement

Build a search autocomplete system. As a user types a prefix, return the top 3 most frequently searched queries that start with that prefix, ranked by search frequency (ties broken alphabetically).

Support:

• search(prefix) — return top 3 matching historical queries
• record(query) — log that a query was searched (increases its frequency)

Constraints

• Up to 10^5 distinct queries
• Queries are lowercase words/phrases
• search should be fast even with millions of stored queries
• Ties in frequency broken alphabetically (ascending)

Example

record("apple")      x5
record("application") x3
record("apply")       x8
record("apricot")     x2

search("app") → ["apply", "apple", "application"]
              (freq: 8, 5, 3 — top 3 by frequency)
search("ap")  → ["apply", "apple", "application"]
              (apricot freq 2 is 4th, excluded)

The Insight — Trie + Ranked Retrieval

A HashMap scan would be O(n) per search (check every query against the prefix). The elegant structure is a Trie, where the prefix walk is O(prefix length) regardless of dataset size.

Two design choices for the ranking:

Option A — Collect + heap at query time: Walk to the prefix node, DFS the subtree to gather all completions, then use a min-heap of size 3 (or partial sort) to get the top 3. Simple, good when subtrees are small.

Option B — Cache top-K at each node (the pro move): Store, at every trie node, a precomputed list of the top 3 completions passing through it. On record, update the caches along the path. Now search is O(prefix length) — instant, no subtree DFS.

The "aha": autocomplete is a prefix problem (Trie) fused with a ranking problem (heap/top-K). Recognizing you can push the ranking INTO the trie nodes (Option B) is what separates a working solution from a production one — it's how real search boxes feel instant.

Follow-ups

1. What's the trade-off between computing top-K at query time vs caching it at each node?
2. How do you keep the cached top-3 correct when a query's frequency changes?
3. How would you handle typo tolerance (fuzzy autocomplete)?
4. How would you scale this to a distributed system with sharded tries?