Sort it and binary-search a range
Continues from the last build: a hash index that answers exact lookups in O(1) but has no order at all, so 'every term between cat and dog' means scanning every key
Rung 2 gave you a hash index: drop in a term, get back document ids in O(1).
What you'll build
You leave this rung with a SortedIndex that sorts its terms exactly once and answers range and prefix queries in O(log n + k) instead of O(n), backed by hand-rolled bisect_left/bisect_right functions you can defend line by line in an interview, a passing unit test suite that checks your functions against the stdlib, and a benchmark table proving the win at three corpus sizes.
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:
"""Rung 2 carryover: exact-match index. Great for O(1) lookup, useless for ranges."""
from typing import Dict, List
class HashIndex:
"""Maps each term to the list of document ids that contain it."""
def __init__(self) -> None:
self._postings: Dict[str, List[int]] = {}
def add(self, term: str, doc_id: int) -> None:
self._postings.setdefault(term, []).append(doc_id)
def lookup(self, term: str) -> List[int]:
"""O(1) average case. But there is no order: 'cat' and 'dog'
could land in any bucket, so 'everything between cat and dog'
has no meaning here."""
return self._postings.get(term, [])
def terms(self) -> List[str]:
return list(self._postings.keys())
Reading this file
def lookup(self, term: str) -> List[int]:The exact-match entry point from rung 2, unchanged here.self._postings.setdefault(term, []).append(doc_id)Builds a postings list per term, in whatever order terms happen to arrive.there is no orderThe exact limitation this rung exists to fix.Dict[str, List[int]]The type hint makes the unordered mapping explicit.
Unchanged from rung 2, kept only so you can see side by side why it cannot answer ranges.
That's 1 of 8 explained code blocks in this single project.
The build, milestone by milestone
- 1
Feel the pain: measure the naive scan
4 guided stepsYou cannot claim a speedup that you never measured. This milestone locks in the baseline so 'binary search is faster' is a fact with numbers behind it, not a slogan.
- 2
Sort the keys once at build time
4 guided stepsBinary search only works on sorted data. Paying O(n log n) once at build time is what buys O(log n) per query forever after, this milestone makes that trade explicit and measured.
- 3
Binary search from scratch
5 guided stepsBinary search is one of the most misremembered algorithms in interviews, off-by-one errors in the bounds are the single most common bug. Building it by hand once means you will recognize the failure modes forever.
- 4
Range query with two binary searches
4 guided stepsThis is the payoff milestone: the query you could not answer efficiently on rung 2 (a range, not just an exact match) now costs O(log n + k) instead of O(n).
- 5
Prefix query as a disguised range query
4 guided stepsAutocomplete-shaped queries (prefix lookups) are secretly range queries once the keys are sorted. Seeing this connection now sets up rung 5's trie as a specialized structure for the same problem, with different tradeoffs.
- 6
Benchmark the win, then contrast with stdlib bisect
4 guided stepsA speedup you have not measured is a guess. This milestone closes the loop: same growing input as milestone 1, same benchmark harness, now measuring the structure you built plus the standard library version for a reality check on constant factors.
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