Part 3 · Data Structures · Graded project

Project 3: Autocomplete Engine

Build the search box of an online store from first principles: a trie for prefixes, a heap for ranking, an LRU cache for speed, and a pruned edit-distance search for typos. Every structure from Part 3 earns its place.

⏱ ~8–12 hoursPrerequisites: M24, M25, M27

The scenario

You have joined the search team at VoltMart, a fictional electronics store with a catalog of tens of thousands of products. Product managers want a search box that behaves like the ones shoppers already know:

A sorted list plus bisect could answer prefix queries, and a dict could answer exact lookups, but neither gives you all of the above together. You will assemble the right structures yourself, which is exactly what Part 3 prepared you for.

Learning goals and feature spec

Trie

insert(word, score), contains/in, starts_with, delete (prunes dead branches), len, iteration in lexicographic order, items(prefix), words_with_prefix.

Ranking

score, add_score, and top_k(prefix, k) with heapq: highest score first, ties alphabetical.

LRU cache

LRUCache[K, V] with O(1) get/put, keys() (most recent first), hits/misses, clear. No OrderedDict.

Typo tolerance

levenshtein, within_distance, and fuzzy_search(trie, query, max_distance) that prunes while walking.

Engine facade

AutocompleteEngine: add_term, remove_term, load_csv, complete, suggest, record_selection, stats().

Normalization

normalize(text): NFC, casefold, collapse whitespace, so every entry point agrees on what a term is.

OperationTarget costWhy
insert, contains, deleteO(L)One node per character of the term.
top_k(prefix, k)O(L + m log k)Walk to the prefix node, then heap-select among m matches.
cached completeO(L + k)Normalize, one dict lookup, copy the list.
LRUCache.get/putO(1)Dict finds the node; linked list relinks it.
fuzzy_searchO(nodes visited × |query|)Pruning keeps the visited set small for d ≤ 2.

Architecture

The engine is a facade: callers see one class, and the class coordinates the structures behind it. Each module is independently testable, which is how the grading tests are organized.

flowchart LR
  U[Shopper keystrokes] --> N[normalize]
  N --> E[AutocompleteEngine]
  E -- "(prefix, k)" --> C[LRUCache]
  C -- miss --> T[Trie.top_k]
  T --> H[heapq selection]
  E -- "fewer than k" --> F[fuzzy_search]
  F --> T2[Trie nodes + DP rows]
  CSV[catalog.csv] --> E
  S[record_selection] --> E
  E -- "any update" --> X[cache.clear]
·ap ep l→e (apple 50)l→y (apply 10) ape · 5app · 80
Green nodes end a stored term and carry its score. top_k("ap", 2) walks to the p node, gathers the four terms beneath it, and heap-selects app (80) and apple (50).

Getting started with Pixi

pixi run projects            # list every project and its status
pixi run start p03           # copy the starter into work/p03_autocomplete/
pixi run grade p03           # run all 68 tests against your work/ copy

The starter contains the full public API with type hints, docstrings, and TODO(milestone N) comments; every body raises NotImplementedError, so every test fails at first. Work milestone by milestone and watch the failure count fall. Open work/p03_autocomplete/ in your editor; the tests live in projects/p03_autocomplete/tests/ and you can read them for the exact contract.

Milestones

Milestone 1: the Trie (trie.py)

Each TrieNode holds a children dict, an is_word flag, and a score. Write a private _find(prefix) helper that returns the node at the end of a path or None; most methods are three lines on top of it. Iteration must be lexicographic, which means visiting children in sorted key order and yielding a node's own word before its descendants.

  • insert creates nodes on demand, rejects the empty string, and counts only new terms
  • contains distinguishes words from mere prefixes; in works and rejects non-strings
  • delete returns a bool and prunes nodes that no longer lead to any word
  • items, words_with_prefix, and iter are sorted regardless of insertion order
  • Unicode terms (日本語, café) work without special cases
Hint: pruning on delete

Record (parent, char) pairs on the way down. After unmarking the final node, walk that list backwards: delete parent.children[char] while the child is neither a word nor has children; stop at the first node that is still needed.

Hint: iterative sorted DFS

With an explicit stack, push children in reverse sorted order so the smallest pops first. Yield the current node's word when you pop it, before its children are pushed.

Milestone 2: weighted completions (Trie.top_k)

Sorting all m matches costs O(m log m). A heap of size k does it in O(m log k), which matters when the prefix is one letter and m is in the thousands. The ordering rule is "highest score first, then alphabetical", which is ascending order of the key (-score, term).

  • score and add_score raise KeyError for unknown terms
  • Re-inserting a term replaces its score without changing len
  • top_k uses heapq and breaks ties alphabetically
  • Edge cases: empty prefix ranks everything, unknown prefix returns [], k=0 returns [], negative k raises
Hint: two heap strategies

heapq.nsmallest(k, self.items(prefix), key=lambda p: (-p[1], p[0])) is one line. To build it yourself, keep a min-heap of the k best seen so far keyed by a value whose smallest element is the worst of the k; replace the root when a better item arrives (heapreplace). Python 3.14's heappushpop_max family can help with the inverted order.

Milestone 3: an LRU cache from scratch (lru.py)

A dict maps keys to nodes; a doubly linked list orders nodes from most to least recently used. Two sentinel nodes (head and tail) mean you never special-case an empty list. A test reads your module's source to make sure OrderedDict and lru_cache are not used.

  • get moves a hit to the front and counts hits and misses
  • put updates existing keys in place and evicts from the back when full
  • in does not count as a use; keys() is most-recent-first
  • Capacity below 1 raises ValueError; capacity 1 works
Hint: two helpers do all the work

_unlink(node) sets node.prev.next = node.next and node.next.prev = node.prev; _push_front(node) splices it between head and head.next. A "move to front" is unlink then push. Eviction is unlink tail.prev and del self._map[node.key], which is why each node stores its key.

Milestone 4: typo tolerance (fuzzy.py)

Computing levenshtein(query, term) for every term costs O(n × L²). Instead, walk the trie and compute one DP row per node: the row for node "lap" is derived from the row for "la". Terms that share a prefix share the work. Better still, if every value in a row exceeds the bound, no extension of that prefix can come back under it, so the whole subtree is skipped.

  • levenshtein passes the classic cases (kitten/sitting = 3, flaw/lawn = 2) using two rows
  • within_distance fails fast on length gaps and stops when min(row) exceeds the bound
  • fuzzy_search matches a brute-force scan exactly, sorted by (distance, term)
Hint: the row recurrence

For trie character c and parent row prev: row[0] = prev[0] + 1, and for each query position j, row[j] = min(row[j-1] + 1, prev[j] + 1, prev[j-1] + (query[j-1] != c)). The node is a match if it ends a word and row[-1] <= max_distance.

Milestone 5: the engine facade (engine.py)

The facade makes the parts behave as one product. Normalize at every entry point, cache (normalized prefix, k) results, and clear the cache on every mutation: adding, removing, loading, and selecting. A stale cache is the classic bug here, and three tests target it.

  • normalize handles case, ß, combining accents, and whitespace
  • load_csv reads a term,score header, skips blank rows, and reports bad rows with line numbers
  • complete returns copies, so mutating a result never corrupts the cache
  • suggest tops up with typo matches ordered by distance, score, term, without duplicates
  • record_selection boosts the score, and stats() reports terms, queries, hits, misses, selections, and hit rate
  • 20,000 terms plus 21 queries finish well within the generous time bound
Hint: why copies matter

If complete returns the very list stored in the cache, a caller doing results.append("ad") changes what the next shopper sees. Store one list and return list(cached). This is the aliasing lesson from early in the course, now with consequences.

Grading and rubric

pixi run grade p03 runs 68 tests in five files, one per milestone. Passing all of them is the automated part; the rubric below is how a reviewer would judge the code.

CriterionExcellentWeight
CorrectnessAll 68 tests pass; edge cases (empty prefix, unicode, ties) handled deliberately.40%
ComplexityTrie operations O(L); top-k uses a heap; LRU is O(1); fuzzy search prunes.20%
DesignSmall helpers (_find, _unlink), a facade with no leaking internals, cache invalidation in one place.15%
Types and docsFull hints (generic LRUCache[K, V]), Google docstrings, ruff-clean.15%
RobustnessClear exceptions with useful messages; no aliasing bugs; no prints in library code.10%

Stretch goals

Reflection quiz