Neural Mastery
← Practice
Build an Inverted Indexmedium

Build an Inverted Index

medium RAG & Retrieval 15–20 min

NumPy allowed · plain Python earns 10 bonus points

RAG step 1/4

A query retrieves context

Embedding similarity ranks the documents before generation.
Open lesson →
01query
02embed
03retrieve
04context
What is RAG?→ embed →top context
retrieval.md44%
rag-systems.md33%
agents.md24%

Cosine-like similarity scores ranked before context assembly

Implement the inverted index -- the classic sparse-retrieval data structure (used by BM25, Elasticsearch, and hybrid search systems) that every dense vector index is typically paired with in production RAG.

Task

Implement build_inverted_index(documents): for every unique token across all documents, list every document index (deduplicated, ascending) in which it appears.

Function Signature

build_inverted_index(documents: list[list[str]]) -> dict[str, list[int]]

Examples

Example 1: Three Short Documents
Input: documents = [['the', 'cat', 'sat'], ['the', 'dog', 'ran'], ['cat', 'and', 'dog']]
Output: {'the': [0, 1], 'cat': [0, 2], 'sat': [0], 'dog': [1, 2], 'ran': [1], 'and': [2]}
Example 2: Repeated Token in One Document
Input: documents = [['a', 'a', 'b'], ['b', 'c']]
Output: {'a': [0], 'b': [0, 1], 'c': [1]}
Explanation: Repeating "a" in doc 0 still yields a single entry [0]

Constraints

  • Libraries (standard library only -- collections, etc.) are allowed and accepted normally.
  • A plain-Python solution earns 10 bonus points.
  • Each document index must appear at most once per token, even if the token repeats within that document.
  • Document indices for each token must be sorted ascending.
  • An empty `documents` list, or documents with no tokens, should produce an empty dict for terms that never occur.
Python3Saved ✓
def build_inverted_index(documents: list[list[str]]) -> dict[str, list[int]]:
"""documents: a list of tokenized documents (each a list of string tokens).
Return a dict mapping each unique token to the sorted list of document
indices that contain it (each index appears at most once per token,
even if the token repeats within a document)."""
# Your implementation here
pass

Case 1: Three Short Documents
Input: documents = [['the', 'cat', 'sat'], ['the', 'dog', 'ran'], ['cat', 'and', 'dog']]
Expected: {'the': [0, 1], 'cat': [0, 2], 'sat': [0], 'dog': [1, 2], 'ran': [1], 'and': [2]}
Case 2: Repeated Token in One Document
Input: documents = [['a', 'a', 'b'], ['b', 'c']]
Expected: {'a': [0], 'b': [0, 1], 'c': [1]}