Suggest related terms with a graph search
Continues from the last build: Rung 8 gave you exact phrase matching, a sliding window and two pointers confirming that terms appear together in the right order. But it only answers 'does this phrase occur', never 'what else is this like'.
Your phrase matcher can now confirm that 'binary search tree' occurs as an exact run of tokens somewhere in the corpus, but it goes silent the moment a query has no exact match to find.
What you'll build
related_terms('recursion', max_hops=2) returns a ranked, finite list of genuinely co-occurring terms in well under a second on a multi-thousand-document graph, and bench_graph.py proves BFS's O(V+E) behavior against a naive O(V^2)-trending list frontier at n, 10n and 100n terms.
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 collections import defaultdict
from typing import Dict, List
def tokenize(text: str) -> List[str]:
# TODO: split text into lowercase alphabetic tokens
raise NotImplementedError
def build_term_graph(documents: Dict[str, str]) -> Dict[str, Dict[str, int]]:
graph: Dict[str, Dict[str, int]] = defaultdict(dict)
for doc_id, text in documents.items():
terms = sorted(set(tokenize(text)))
# TODO: for every pair of terms in this document, add or increment
# an edge in both directions (the graph is undirected)
pass
return dict(graph)
Reading this file
graph: Dict[str, Dict[str, int]] = defaultdict(dict)adjacency list is a dict of dict, this is the shape you must fill interms = sorted(set(tokenize(text)))dedupe terms per document before pairing them up# TODO: for every pair of terms in this document, add or incrementthis is where the co-occurrence counting logic goesraise NotImplementedErrortokenize is the one helper you must write first
Builds the undirected, weighted co-occurrence graph. tokenize() and the pairing loop are yours to finish.
That's 1 of 8 explained code blocks in this single project.
The build, milestone by milestone
- 1
Turn documents into a co-occurrence graph
4 guided stepsGraphs model relationships that hash tables and tries cannot: a hash index tells you where a term is, a graph tells you what a term is near. That is the only structure that can answer 'related to' queries.
- 2
Traverse it with BFS, mind the visited set
4 guided stepsBFS explores a graph strictly level by level, so it is the natural fit for 'related within N hops', and it only stays correct (and fast) if you respect two invariants: a deque frontier and a visited set checked before enqueueing.
- 3
Weight the edges, and see where BFS stops being enough
5 guided stepsBFS's hop count treats every edge as equally important, but real co-occurrence strength varies a lot. Once edges have different weights, the question changes from 'how many edges away' to 'how cheap is the cheapest path', and only a cost-aware search answers that.
- 4
Wire related terms into the query pipeline
4 guided stepsA graph sitting off to the side is a toy. It only earns its place once the same query path the user already types into can call it: type 'trie' and see 'hash-tables' and 'heaps' come back as related, right next to any exact hits.
- 5
Benchmark it: BFS's O(V+E) against a slow frontier
4 guided stepsA speedup claim without a timed, growing-input benchmark is just a guess. This milestone proves BFS's O(V+E) bound holds with a deque, and shows exactly how a list frontier's O(n) pop(0) degrades that bound in practice.
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