Capstone: A Tiny Word Index

You've now met every core tool in this book: slices and maps, strings and structs, sorting, errors, tests. Time to make them work together. Our finale is a miniature of a genuinely important data structure: the inverted index — the thing at the heart of every search engine.

The problem

Given a collection of documents:

docs := []string{
	"the quick brown fox",   // document 0
	"the lazy dog",          // document 1
	"The Fox and the Dog",   // document 2
}

we want to answer "which documents contain the word fox?" instantly. A plain scan works but re-reads everything on every query. The inverted index flips the data around once, up front: instead of document → words, store word → documents:

map[string][]int{
	"the":   {0, 1, 2},
	"fox":   {0, 2},
	"dog":   {1, 2},
	// ...
}

Now every lookup is one map access.

Design decisions

Small program, real decisions — three of them.

What's a word? We'll split on whitespace with strings.Fields, which handles runs of spaces, tabs, and newlines gracefully and returns nothing for an all-whitespace string. (A production index would also strip punctuation — we'll leave that out.)

Case. "Fox" in document 2 and "fox" in document 0 should be the same word — a search for fox should find both. So we normalize: lowercase everything with strings.ToLower before it enters the index.

Duplicates. "the" appears twice in document 2, but the postings list for "the" should mention document 2 once. Each document index appears at most once per word — and the lists stay sorted ascending so results are deterministic and easy to compare.

Sketching the algorithm

The shape follows from the output type, map[string][]int:

func buildIndex(docs []string) map[string][]int {
	index := make(map[string][]int)
	for i, doc := range docs {
		// for each word in doc (lowercased):
		//   record that word appears in document i — but only once
	}
	return index
}

The subtle part is "only once". Appending i blindly gives "the": {2, 2} for document 2. The idiomatic fix is a per-document seen set — a map[string]bool created fresh for each document:

seen := make(map[string]bool)
for _, w := range strings.Fields(strings.ToLower(doc)) {
	if !seen[w] {
		seen[w] = true
		// append i to index[w]
	}
}

Two maps cooperating: the outer one is the answer we're building, the inner one is scratch state that lives for a single loop iteration. This pattern — a throwaway set guarding a growing collection — comes up constantly.

And the sorting? Here's the pleasant surprise: if you process documents in order (i = 0, 1, 2, ...) and append each index at most once, every postings list comes out already sorted — you never append a smaller i after a bigger one. The design gives you the invariant for free; noticing that kind of thing is what design is.

Edge cases, spec-style

Think like the test author from lesson one:

• Empty docs slice → an index with no entries.
• A document that's empty (or all whitespace) contributes nothing — strings.Fields returns an empty slice, so the loop body never runs.
• Case folding: "Go" and "go" must land in the same entry.

That's the whole design. The exercise below is the implementation — maybe fifteen lines — and it's graded, of course, by a table-driven test.