Index it for instant exact lookups
Continues from the last build: a linear-scan engine that is too slow
Rung 1 left you with a search that works only because nobody has tried a real corpus on it yet.
What you'll build
An index-backed engine where lookup(index, term) answers in roughly constant time regardless of corpus size, a benchmark table proving it on 1k, 10k and 100k documents, a tiny hash table you built by hand to see the collision worst case with your own eyes, and every dict-related trap (mutable default arguments, rebuild-per-query, average vs worst case) fixed in your own code, not just read about.
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:
"""The rung 1 baseline: linear scan over every document.
This is the code that got too slow. We keep it here only to benchmark
against the new hash index built in this rung.
"""
from __future__ import annotations
def scan_search(term: str, documents: dict[int, str]) -> list[int]:
"""Return doc ids whose text contains term. O(n) per call."""
term = term.lower()
hits: list[int] = []
for doc_id, text in documents.items():
if term in text.lower():
hits.append(doc_id)
return hits
Reading this file
def scan_search(term: str, documents: dict[int, str]) -> list[int]:Same signature as before. This is the function you will race against your new index.O(n) per call.Every call walks the whole corpus, regardless of whether the term exists once or not at all.for doc_id, text in documents.items():This loop is the cost center: it repeats in full for every single query.
The rung 1 baseline, kept only to benchmark against.
That's 1 of 8 explained code blocks in this single project.
The build, milestone by milestone
- 1
Build the term-to-doc-ids hash index
4 guided stepsA hash table trades a one-time O(n) build cost for O(1) average lookups afterward. That trade only pays off if you actually build the index once and reuse it, which is the whole point of this rung.
- 2
Dedup postings with a set and fix the mutable-default trap
4 guided stepsA list-based postings structure would need manual dedup logic and grows unbounded with repeated terms; a set gives you dedup and O(1) average membership for free. The mutable-default bug is unrelated to hash tables but shows up constantly in code that builds up dict/set state incrementally, exactly the shape of this rung's code.
- 3
Benchmark scan vs index on a growing corpus
4 guided stepsBig-O reasoning is only a hypothesis until you measure it. This is the moment you prove, with real numbers on your own machine, that scan time grows with the corpus while index lookup time does not.
- 4
Prove average case with a controlled worst case
4 guided stepsPython's real dict actively defends against this (resizing, a randomized hash seed for str), so you almost never see its worst case in practice. Building your own toy table with no such defenses lets you force and measure the worst case honestly instead of just asserting it exists.
- 5
Wire the index into the CLI without rebuilding it per query
4 guided stepsThe single most common way to accidentally throw away everything this rung bought you is calling build_index() inside the query loop. That silently turns every query back into an O(n) rebuild, and it is an easy mistake to make once the build call is buried a few lines into a bigger function.
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