The Mirror Index

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L4
Asked in
Meta

Problem

A log search index d holds one entry per document: the document id and the single term that document matched. Most terms are text, but numeric tokens such as status codes are stored as integers. Lookups need the reverse direction. That reverse index is written out as JSON, so every term key is a string. Return a dict mapping each term to the sorted list of document ids that matched it.

Every value remembers who pointed to it.

Example 1

Input:

d = {"a":1,"b":2,"c":1,"d":3,"e":2}

Output:

{"1":["a","c"],"2":["b","e"],"3":["d"]}

Example 2

Input:

d = {"x":"hello","y":"hello","z":"world"}

Output:

{"hello":["x","y"],"world":["z"]}

Worked solution and explanation

The collision is the whole problem

This is a one-to-many grouping problem wearing a dict-inversion costume. Flipping keys and values is the easy half that everyone writes; the trap is the collision. The moment two keys share a value, a naive inverted[value] = key throws away everything seen before, so {'a':1,'c':1} silently collapses to {'1':['c']} and 'a' is gone. What separates a real answer: you accumulate a list per value instead of a scalar, and you remember the output keys are stringified because the result serializes to JSON.

Break down the requirements

Step 1: Group keys under each value

Walk every key-value pair once. The value becomes the bucket; the key gets dropped into that bucket. The first time you see a value, the bucket does not exist yet, so you have to create the empty list before appending or every collision blows up.

Step 2: Stringify each value to form the output key

The result is serialized as a JSON object, whose keys must be strings. Use str(value) as the bucket key so an integer value like 1 lands under the key "1" and matches the expected output. Skip this and an int-valued dict fails the very first test even though the grouping logic is correct.

Step 3: Sort each bucket

Dict iteration order is not something you want leaking into the answer. Sort each bucket so 'c' and 'a' come back as ['a','c'] regardless of insertion order, which is what makes the output deterministic and testable.

The solution

Value-to-key grouping with sorted lists
def invert_dict(d: dict) -> dict:
    inverted = {}
    for key, value in d.items():
        out_key = str(value)
        if out_key not in inverted:
            inverted[out_key] = []
        inverted[out_key].append(key)
    for out_key in inverted:
        inverted[out_key] = sorted(inverted[out_key])
    return inverted

Common follow-up questions