Inverted Index

Problem

Build an inverted index from tokenized documents.

docs is a list of token lists and document ids are their 0-based positions. Return a dict mapping each term to the sorted list of document ids that contain it.

Hint

Iterating document ids in order keeps each posting list sorted automatically.

Test cases

case 1

in: [[["a","b"],["b","c"],["a"]]]

expected: {"a":[0,2],"b":[0,1],"c":[1]}

case 2

in: [[["x"]]]

expected: {"x":[0]}

case 3

in: [[[],[]]]

expected: {}

case 4

in: [[["a","b"],["a","b"]]]

expected: {"a":[0,1],"b":[0,1]}

Starter codePython

def build_inverted_index(docs):
    # Your code here
    pass

4 test cases · run your code against them in the editor