Skip to content
Tutorials Center
My learning

Topics

Lesson 45 of 65 ยท Core Algorithms and Data Structures for Design

Tries and Top-K

Build search autocomplete and trending lists: tries for prefix lookup, heaps for top-K, Space-Saving heavy hitters and sliding windows, with runnable Python examples.

Two small questions appear in many system designs. Given the first few letters a user typed, which suggestions should I show? And which K items are the most popular right now? Search autocomplete, trending topics, "top 10 songs this week" and "most visited pages" are all variations of them. The tools are the trie (prefix tree) for prefix lookup, and the heap plus counting techniques for top-K.

The trie

A trie stores strings as paths in a tree. Each edge is a character; a node marks whether a word ends there. All words that share a prefix share the same path, so finding every word that starts with "ca" means walking down c, a and collecting what lies below.

flowchart TB
  R((root)) --> c((c))
  c --> a((a))
  a --> r((r*))
  a --> t((t*))
  r --> d((d*))
  a --> b((b*))

Words stored: car, card, cat, cab. A star marks the end of a word.

Lookup of a prefix costs O(L) where L is the prefix length, independent of how many words are stored. Compare this with scanning a list of millions of strings, or with a database LIKE 'ca%' query, which is fast only with the right index.

Python A trie with prefix search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Autocomplete at scale

Returning all completions is not useful: for the prefix "a" that is millions of strings. A search box needs the top few by popularity, in a few milliseconds, on every keystroke. The standard trick is to cache the top-K suggestions at every trie node. Then a lookup is: walk the prefix, read the list stored on that node. No traversal of the subtree is needed.

Python Trie nodes that store their top suggestions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Design notes for a production version:

  • Build offline, serve online. A batch job aggregates query logs (every few minutes to hours), builds the trie and ships it to serving machines; fresh trends can be merged in separately. Updating a live trie on every search is rarely worth the cost.
  • Memory: compress with a radix tree (merge single-child chains into one edge) or store tries as arrays. Limit prefix length (suggestions rarely need prefixes beyond 20 characters).
  • Shard by first letters or by hash of the prefix (see Sharding and Partitioning), and cache popular prefixes in Redis or at the CDN.
  • Client side: debounce keystrokes, cache earlier responses and fetch only after 2 to 3 characters.
  • Personalization and freshness: blend global popularity with the user's history, location and trending boosts, and filter unsafe or blocked terms.
  • Typos: add edit-distance candidates or an n-gram index as a fallback (see below).

The top-K problem

Top-K asks for the K largest items in a collection or a stream. Sorting everything costs O(n log n). A min-heap of size K does it in O(n log K): keep the K best seen so far; for each new item, if it beats the smallest of the K, replace it. Memory is only K items, so it works on streams too large to store.

Python Top-K with a min-heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Top-K frequent items in a stream

"Most frequent search queries" is harder: you first need the count of each item, and a dictionary of all distinct queries may not fit in memory. Options:

  1. Exact counts, sharded: hash each item to a worker that counts its share; each worker keeps a local top-K and a coordinator merges them. Correct only if each item is routed to exactly one worker.
  2. Count-Min Sketch plus a heap: update the sketch for each item, then maintain a heap of K items by estimated count (see Counting at Scale).
  3. Space-Saving (Misra-Gries family): keep only K counters. When an unseen item arrives and the table is full, evict the item with the smallest count and let the newcomer inherit that count plus one. Frequent items stay; rare ones churn. Counts are overestimates with a known bound.
Python Space-Saving: heavy hitters with 8 counters

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Counts for the heavy hitters are close, even though only 8 counters tracked a stream with thousands of distinct items.

"Top items" almost always means "over the last hour" or "today", not "of all time". Techniques:

  • Tumbling windows: counts per fixed interval (each minute). Cheap, but abrupt at boundaries.
  • Sliding windows: the last N minutes. Keep per-minute buckets and sum the latest N; drop the oldest as time moves.
  • Exponential decay: multiply old scores by a decay factor over time so new activity naturally outweighs old.
  • Trending vs popular: rank by growth compared with a baseline, not raw count, otherwise "weather" always wins. The ratio of the current hour to the usual hour for that term is a common score.
Python Sliding window with per-minute buckets

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice "election" falls out of the window once its minutes expire, while "goal" climbs as it spikes.

Other structures worth knowing

  • Inverted index: maps each word to the documents containing it; the backbone of full-text search (Elasticsearch, Lucene).
  • N-gram index: index overlapping character chunks to support typos and substring search.
  • Skip list / sorted set: an ordered structure with O(log n) inserts and range queries; Redis sorted sets (ZADD, ZREVRANGE) are a ready-made leaderboard for top-K.
  • LRU cache: hash map plus doubly linked list for O(1) get and evict; used wherever you cache.
  • Segment tree / Fenwick tree: range queries and updates in O(log n).

For a "design autocomplete" interview: state the requirements (latency under 100 ms, top 5, freshness), then trie with cached top-K per node, offline build from logs, sharding by prefix, caching and client debounce. Mention how you would add trending terms.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the main advantage of storing top-K suggestions at each trie node?

    Precomputed top lists make each keystroke an O(prefix length) walk plus a read, which is fast enough for per-keystroke latency.
  2. 2. What is the time complexity of top-K over n items with a min-heap of size K?

    Each of the n items costs at most a heap operation of O(log K).
  3. 3. How does Space-Saving handle a new item when its counters are full?

    Frequent items keep their counters while rare ones churn, so heavy hitters are tracked with bounded memory.
  4. 4. Which approach best ranks 'trending' rather than 'popular' terms?

    Trending measures unusual increase, otherwise always-popular terms would dominate.

Summary

  • A trie finds all strings with a given prefix in time proportional to the prefix length.
  • Autocomplete caches top-K suggestions on each node, is built offline from logs, sharded by prefix and cached.
  • A min-heap of size K finds top-K in O(n log K) with O(K) memory.
  • Heavy hitters in a stream use sharded counts, Count-Min plus heap, or Space-Saving.
  • Use windows or decay for "right now" rankings and rank trends by growth over a baseline.

Next: System Design