# The Mirror Index > Every value remembers who pointed to it. Canonical URL: 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. ## 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** ```python 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 ``` > **In production** > > The `setdefault` form, `inverted.setdefault(str(value), []).append(key)`, folds the existence check into one line and is what most reviewers expect to see. `collections.defaultdict(list)` is even cleaner when you can build a plain dict at the end. All three are the same O(1)-per-insert; pick the one your team reads fastest. > **Time and Space Complexity** > > **Time:** O(n log n) in the worst case, driven by sorting the buckets, where n is the number of entries. The single pass to group is O(n). > > Space: O(n) for the inverted dict. > **Interviewers watch for** > > Whether you produce sorted buckets. Unsorted output makes the inverted index non-deterministic, and an interviewer who diffs your result against theirs will see the mismatch immediately even when your grouping is right. > **Common pitfall** > > Assuming values are unique and inverting to a plain key-to-key mapping. When multiple keys share a value, the last one overwrites the rest and earlier keys vanish without an error. The second silent killer: forgetting the serialized output keys are strings, so an int value 1 must become the key "1". --- ## Common follow-up questions - What if values are not hashable? _(Tests that only hashable types can be dict keys; lists or dicts as values would need special handling.)_ - How would you invert a dict where values are lists? _(Tests flattening: each element in the value list maps back to the original key.)_ - What is the time complexity of `defaultdict(list)` vs manual checking? _(Tests that both are O(1) per insert, but `defaultdict` is more idiomatic.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/the_mirror_index) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.