core practice · implementation task
Build an inverted index
From a list of documents, build a term → sorted posting list map. Support a boolean AND query by intersecting posting lists. Track document frequency per term.
The mechanism
An inverted index flips documents inside out: instead of doc → terms, you store term → list of docs (postings). Query answering becomes intersecting/merging sorted posting lists.
Expected evidence
Query 'quick fox' returns docs containing both terms, found by list intersection.
Try this drill in the practice workspace →
Hints when you need them
- Keep posting lists sorted by doc id so intersection is linear.
- Store document frequency now — ranking needs it later.
Watch for these mistakes
- Storing postings unsorted, making intersection O(n*m)
- Forgetting document frequency, which ranking later needs
- Not separating the dictionary from the postings on disk