Inverted Index

Task

Implement inverted_index(documents: list[list[str]], query_tokens: list[str]) -> list[int]. Build an inverted index over tokenized documents and return the document indices that contain every query token.

Requirements

• documents is a list of already-tokenized documents; use each document's zero-based position as its document index.
• Map each exact token to the document indices in which it occurs.
• Store a document index at most once in a token's posting list, even when that token repeats within the document.
• Keep every posting list in ascending document order by scanning documents from left to right.
• Treat query_tokens as a conjunctive AND query: a result must contain every distinct query token.
• Repeated query tokens do not change the result.
• Return matching document indices in ascending order.
• Return an empty list for an empty query, an empty corpus, or a query containing an unknown token.
• Token matching is exact and case-sensitive; do not lowercase, split, stem, or otherwise normalize tokens.
• Do not mutate documents or query_tokens.

Example

inverted_index(
    [["red", "fox", "red"], ["blue", "fox"], ["red", "bird"]],
    ["red", "fox"],
)
# [0]