Prove it fast: analyze, benchmark, and ship the library
Continues from the last build: Eleven working rungs of Lexi: linear scan, hash index, binary search, recursion, trie, heap, inverted index, phrase window, graph-based suggest, edit distance, and backtracking search, each one built to fix the last rung's slowness but never pulled into a single package, never measured against each other, and never proven to actually be fast.
Eleven rungs in and Lexi finally does everything a real autocomplete engine should: exact search, prefix completion, typo tolerance, ranked suggestions.
What you'll build
A single lexi package with a stable public API (index_document, search, autocomplete, suggest), a COMPLEXITY.md table backed by real timed benchmarks at n, 10n, and 100n that visibly confirm each Big-O claim, a profiling pass that found and fixed a real hot path in autocomplete, a test suite covering empty queries, absent terms, and duplicate documents, and a README a stranger could clone and trust.
See how we teach, before you sign up
You don't just get code dumped on you. Every starter file and every solution is explained line-by-line, in plain English. Here's one real file from this project:
from __future__ import annotations
import re
from collections import defaultdict
import heapq
class TrieNode:
__slots__ = ("children", "is_end", "freq")
def __init__(self) -> None:
self.children: dict[str, "TrieNode"] = {}
self.is_end: bool = False
self.freq: int = 0
def tokenize(text: str) -> list[str]:
return re.findall(r"[a-z0-9]+", text.lower())
def edit_distance(a: str, b: str) -> int:
# TODO: port the edit-distance table from the backtracking rung
raise NotImplementedError
class LexiIndex:
def __init__(self) -> None:
self.inverted: dict[str, set[int]] = defaultdict(set)
self.doc_terms: dict[int, list[str]] = {}
self.trie_root = TrieNode()
self.term_freq: dict[str, int] = defaultdict(int)
self.vocabulary: set[str] = set()
def index_document(self, doc_id: int, text: str) -> None:
# TODO: tokenize, then update inverted, trie, vocabulary, term_freq
raise NotImplementedError
def search(self, query: str) -> list[int]:
# TODO: intersect postings for every query term, return sorted ids
raise NotImplementedError
def autocomplete(self, prefix: str, limit: int = 5) -> list[str]:
# TODO: walk the trie to the prefix node, return top-limit by freq
raise NotImplementedError
def suggest(self, term: str, limit: int = 5, max_distance: int = 2) -> list[str]:
# TODO: scan vocabulary, keep words within max_distance edits
raise NotImplementedError
Reading this file
def tokenize(text: str) -> list[str]:Shared tokenizer every method must reuse instead of re-splitting textraise NotImplementedErrorFour methods stubbed, this is the whole surface you must fill inclass LexiIndex:One class replaces eleven separate scripts
That's 1 of 9 explained code blocks in this single project.
The build, milestone by milestone
- 1
Unify eleven rungs into one importable package
4 guided stepsA pile of scripts is not a library. Nobody can build on Lexi, benchmark it fairly, or trust its behavior until it is one class with one contract.
- 2
Write the complexity table before you trust any benchmark
4 guided stepsA benchmark without a prediction is just a number. Writing the expected complexity first means the benchmark can actually confirm or falsify something, instead of becoming decoration.
- 3
Build a growth benchmark that actually confirms Big-O
4 guided stepsA benchmark on one input size proves nothing. Growing the input 100x and watching naive search's time scale with it while indexed search stays flat is what actually confirms the complexity table.
- 4
Profile first, optimize second
4 guided stepsOptimizing without profiling first is how people spend an hour speeding up code that was never the bottleneck. The profile tells you exactly which function is eating the time, and it is rarely the one you assumed.
- 5
Cover the edges nobody covers
4 guided stepsHappy-path tests only prove the demo works. Empty queries, absent terms, and duplicate documents are the inputs that actually break libraries in production, and they are cheap to test now.
- 6
Ship the README so the next person trusts the numbers
4 guided stepsA library nobody can onboard to in five minutes will not get reused, and a complexity table buried in a separate file nobody opens does not build trust. The README is the artifact a stranger judges the whole rung by.
What's inside when you start
You'll walk away with
This is portfolio-grade. Build it free.
Sign up to unlock every milestone step-by-step, the code skeletons, full reference solutions, and checkable tasks, with your progress saved as you build.
Start building