How it works
Define the suggestion contract first: complete search queries, product names, or usernames; return how many results; and rank them by what signal. Normalize indexed strings and request prefixes consistently, including Unicode and case rules, while preserving display text separately.
In a basic trie, each edge represents a character, and a path from the root spells a prefix. The strings “car,” “card,” and “cat” share the path “ca.” Looking up “car” reaches a node whose subtree contains “car” and “card”; terminal markers distinguish complete strings from prefixes.
Reaching a prefix node takes O(p) time for a prefix of length p, assuming constant-time child lookup, but enumerating its descendants can be expensive. Store a precomputed top-k list of suggestion IDs at each relevant node to return ranked results in O(p + k), excluding string retrieval and serialization. This avoids scanning a huge subtree for a short prefix such as “a.”
Build ranking data from eligible catalog records or aggregated query events. For query suggestions, normalize and deduplicate inputs, filter sensitive or abusive terms, and compute scores over a defined time window. Build versioned index snapshots, distribute them to serving replicas, and switch each replica to a complete new version atomically.
Serve requests from an in-memory index, with caching for popular prefixes when useful. If a full index fits on each replica, replicate it before adding sharding complexity. Otherwise, partition by prefix ranges or distribute terms across shards; range partitioning can create hot partitions, while term partitioning requires querying multiple shards and merging their candidates.
Control request volume with a minimum prefix length, client-side debouncing, and server-side limits. Tag requests so the client discards responses for older input. Personalization and typo tolerance are separate extensions: they need additional candidates, ranking work, or approximate matching rather than a plain prefix lookup.
A worked example
Serving five suggestions from a versioned trie
Suppose a service indexes 2 million eligible search phrases and returns five suggestions per request. A builder aggregates query counts over a rolling seven-day window and publishes a snapshot every ten minutes. Each indexed prefix stores five suggestion IDs ordered by score; serving “car” follows three edges and reads that list instead of scanning every matching phrase. If there are 8 million indexed prefix nodes, five 4-byte IDs per node alone require 160 MB, before edges, scores, strings, and allocator overhead. Measure the complete representation before deciding whether every replica can hold it. Replicas validate and load a new snapshot before switching versions. A separate suppression check blocks removed phrases between builds.
Trade-offs to say out loud
- Fast reads cost memory
- Per-node top-k lists bound lookup work but duplicate references across prefixes; compressed radix trees and compact arrays reduce overhead.
- Precomputation limits ranking flexibility
- A fixed global top-k list is efficient, but personalized or filtered ranking may need a larger candidate pool or separate indexes.
- Freshness increases update complexity
- Periodic snapshots simplify serving, while incremental updates must maintain affected prefix rankings and handle score decreases and deletions.
- Sharding changes routing and load
- Prefix partitions allow targeted routing but can be skewed, while term-based partitions spread storage at the cost of query fan-out.
- Availability can mean stale suggestions
- Serving the last complete snapshot preserves availability during build failures, but urgent removals need an independently updated suppression mechanism.
- Popularity is not sufficient eligibility
- Frequent queries can contain private information, spam, or harmful content, so candidate selection needs explicit inclusion and removal rules.
When to reach for it
- Users need ranked suggestions after typing only a few characters, with a tight response-time budget.
- The workload is read-heavy, and many requests repeat the same short prefixes.
- The candidate vocabulary is bounded enough to index, and ranking can be partly precomputed.
- Scanning database rows or enumerating all prefix matches would produce too much work per keystroke.
- Suggestions can tolerate a defined update delay, allowing a separate build pipeline and serving index.
How to bring it up in the interview
- Clarify prefix completion versus substring search, typo correction, and full-text search before proposing a trie; those requirements need different retrieval capabilities.
- Explain the expensive step explicitly: finding the prefix node is cheap, but finding its best completions is not unless ranking data is precomputed.
- Estimate vocabulary size, total characters, indexed prefix count, and top-k reference storage before choosing full replication or sharding; expect questions about pointer overhead and compression.
- Separate durable source data, ranking aggregation, index construction, and serving replicas; defend the allowed freshness lag and explain failed-build recovery.
- Be ready to explain score decreases, deleted suggestions, hot short prefixes, and personalized ranking, because each challenges a simple per-node top-k design.
Common mistakes
- Claiming autocomplete costs only O(p) while ignoring subtree traversal, result materialization, and ranking.
- Treating a trie as mandatory when an indexed prefix query or a dedicated search engine would satisfy the workload.
- Updating popularity synchronously on every keystroke instead of defining which events count and aggregating them separately.
- Assuming first-character sharding evenly distributes traffic or solves popular-prefix hot spots.
- Serving raw historical queries without privacy filtering, or assuming periodic rebuilds provide prompt removal.
Questions people ask
What is a trie data structure, and why is it useful for autocomplete?
A trie stores strings as paths that share common prefixes. It finds the node for a typed prefix without scanning every stored string, but efficient ranked autocomplete usually also needs cached top suggestions or another bounded retrieval strategy.
Do I need a trie to design a typeahead system?
No. A database index with suitable prefix-query support can be enough for a smaller workload, and a search engine can provide completion indexes or prefix search. Choose based on latency, scale, ranking flexibility, and operational cost rather than starting with a data structure.
How do you keep autocomplete suggestions fresh?
Use periodic index snapshots when bounded staleness is acceptable, or add incremental updates when new terms and score changes must appear sooner. Score decreases and deletions can require replacement candidates beyond the stored top-k list. Keep urgent removals on a faster path than routine ranking rebuilds.