Date: 2026-06-05
Time: 14:02
This file implements a search autocomplete system — the kind of typeahead you see in Google Search. It's a system design interview implementation that demonstrates how to serve prefix-based query suggestions ranked by frequency, with time-decay so stale queries lose relevance over time.
The file owns three responsibilities:
1. Storage & retrieval of queries via a trie with per-node top-k caches (AutocompleteTrie)
2. Batched ingestion of raw search queries (QueryCollector)
3. Service-layer concerns like blocklisting offensive terms and fuzzy matching typos (AutocompleteService)
TrieNodeA dataclass representing a single node in the trie. Each node carries:
children — character-keyed map to child nodesis_end / frequency — marks whether this node terminates a complete query and its search countlast_updated — timestamp for time-decay calculationstopkcache — precomputed list of the top-k most frequent completions reachable from this node. This is the key optimization: it turns a prefix lookup from O(subtree) into O(1).AutocompleteTrieThe core data structure. Constructor takes k (cache size, default 10) and decay_factor (hourly decay multiplier, default 0.99).
Critical methods:
_walk(query) — Traverses the trie character-by-character, returning the full path of nodes visited and the terminal node (or None). Used by nearly every other method as the primitive traversal.updatecachesonpath(path, query) — The cache maintenance routine. After any mutation (insert, increment, delete), this walks the path bottom-up and rebuilds each node's topkcache by merging all children's caches plus the node's own frequency. Sorting is by descending frequency, then lexicographic for ties.insert(query, frequency, timestamp) — Sets a query to an exact frequency. Lowercases and truncates to 200 chars. Tracks _size (distinct query count).increment(query, amount, timestamp) — Adds to existing frequency (or inserts at amount if new). This is the method QueryCollector calls — it models "another user searched for X."delete(query) — Soft-deletes by setting isend=False, frequency=0. The trie nodes remain (no pruning), but the query disappears from all caches via updatecacheson_path.searchprefix(prefix, k, currenttime) — The read path. Without currenttime, returns raw cached results directly. With currenttime, applies exponential decay: rawfreq * decayfactor^hours_elapsed. This means the decay is applied at read time, not stored — raw frequencies stay clean.serialize() / deserialize() — JSON-compatible round-trip. deserialize rebuilds all caches bottom-up via rebuildall, which mirrors the logic in updatecachesonpath.QueryCollectorA write-buffer that accumulates raw (query, timestamp) records and flushes them as aggregated increments. On flush(), it groups by lowercased query, sums counts, takes the max timestamp, then calls trie.increment per unique query. This models the real-world pattern of batching analytics events before updating the trie.
AutocompleteServiceThe top-level API that composes the trie and collector. Adds:
_filter removes any result where a blocklisted term appears as a substring (not just exact match). When querying, it over-fetches by len(blocklist) * 2 to compensate for filtered results.suggest() / suggestwithscores() — Clean interface returning just query strings or (query, score) tuples.fuzzy_suggest() — Fallback when exact prefix yields nothing. Tries single-character edits on the last character: substitution, deletion, and insertion. Collects results from all variant prefixes, deduplicates, and returns top-k. This is intentionally limited to one edit distance on the last char — a pragmatic approximation, not full Levenshtein.Top-k cache per node — This is the defining design choice. Rather than DFS-ing the subtree on every query, each node maintains a precomputed list of the best completions below it. The tradeoff: writes are more expensive (every insert/increment updates caches along the entire path from root to leaf), but reads are O(prefix_length) regardless of subtree size. This matches the real-world read-heavy workload of autocomplete.
Write-time cache maintenance, read-time decay — Frequencies are stored raw; decay is computed lazily during searchprefix only when currenttime is provided. This avoids periodic background jobs to age out all entries and keeps the stored state clean.
Normalization at the boundary — Every public method lowercases and truncates queries to 200 chars immediately on entry. Internal methods can assume normalized input.
Soft deletion — delete zeroes out the node but doesn't prune the trie path. Simpler but means deleted queries leave structural residue.
Imports: Only stdlib — dataclasses for TrieNode, time for timestamps. No external dependencies.
Imported by: testsearchautocomplete.py — the test suite exercises the trie, collector, and service.
A typical lifecycle:
1. AutocompleteService is created with a k, decay factor, and optional blocklist.
2. Queries arrive via recordquery(), which buffers in QueryCollector then immediately flushes (so it's effectively unbatched in this implementation — each recordquery calls flush()).
3. flush() aggregates the buffer and calls trie.increment() for each unique query.
4. increment() walks the trie, creating nodes as needed, bumps the frequency, then calls updatecachesonpath to propagate the change bottom-up through every ancestor's cache.
5. On a read, suggest("fo") calls searchprefix, walks to the node for "fo", and returns its topk_cache (optionally with decay applied).
6. The service filters blocklisted terms and returns the final list.
updatecachesonpath is called, so topkcache is always consistent with the current subtree state. There is no lazy invalidation or dirty flag.size counts distinct queries (nodes where isend=True). It's incremented on first insert, decremented on delete — never from raw node counts.(-frequency, query) — highest frequency first, ties broken lexicographically. This order is maintained at every cache rebuild.k=max(k, 10) for the trie, giving headroom for blocklist filtering.Minimal — this is a data structure implementation, not a network service. Key behaviors:
delete() returns False if the query doesn't exist; it doesn't raise.get_frequency() returns 0 for nonexistent queries.search_prefix() returns [] for unmatched prefixes.search_prefix.frequency or amount being positive — negative values would silently corrupt state._walk returns (path, None) on miss rather than raising, so callers must null-check.search-autocomplete/testsearchautocomplete.py — See what edge cases are tested (decay behavior, blocklist substring matching, fuzzy search, serialization round-trips)search-autocomplete/searchautocomplete.py:updatecacheson_path — The heart of write-path performance; trace through a multi-level insert to see how caches propagate bottom-uptrie-pruning-on-delete — Current delete is soft (nodes remain); explore whether structural pruning would improve memory for high-churn workloadssearch-autocomplete/searchautocomplete.py:fuzzysuggest — Limited to last-char edits; compare against full edit-distance approaches and understand the latency tradeoffsearch-autocomplete/plan.md — Design rationale and interview-context decisions that shaped this implementationautocomplete-cache-consistency — Every mutation (insert, increment, delete) immediately rebuilds topkcache for all ancestor nodes on the path; caches are never stale between operationsautocomplete-decay-is-read-time — Time decay is computed at query time in search_prefix, not stored; raw frequencies in the trie are never modified by decayautocomplete-blocklist-is-substring — The blocklist filter removes results where any blocklisted term appears as a substring of the query, not just exact matchesautocomplete-delete-is-soft — Deleting a query zeroes its frequency and unsets is_end but does not remove trie nodes from the tree structureautocomplete-normalize-at-boundary — All public methods lowercase and truncate queries to 200 characters before any trie operation