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 search index d maps each document id to the single term it matched, and serving lookups needs the inverse: each term pointing back to its documents. Return a new dict whose keys are the unique terms and whose values are the sorted document ids that had that term, keyed as JSON so each term is stringified (the term 1 becomes "1").

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