# The Dictionary Inverter

> Flip the dict. Group what used to be values.

Canonical URL: <https://datadriven.io/problems/the_dictionary_inverter>

Domain: Python · Difficulty: easy · Seniority: L4

## Problem

Given a dict d, return a new dict whose keys are the distinct values of d. Each key's value is a sorted list of original keys that had that value. Return the result as a dict; if the input values are integers they become string keys in the test harness (JSON convention).

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **dict inversion with grouping**, a common indexing pattern. It probes whether a candidate can handle the one-to-many relationship that arises when multiple keys share the same value.

---

### Break down the requirements

#### Step 1: Iterate through the original dict

For each key-value pair, add the key to the list associated with the value in the inverted dict.

#### Step 2: Sort the lists

Each group of original keys should be sorted for deterministic output.

---

### The solution

**Value-to-key grouping with sorted lists**

```python
def invert_dict(d: dict) -> dict:
    inverted = {}
    for key, value in d.items():
        if value not in inverted:
            inverted[value] = []
        inverted[value].append(key)
    for value in inverted:
        inverted[value] = sorted(inverted[value])
    return inverted
```

> **Time and Space Complexity**
>
> **Time:** O(n log n) in the worst case due to sorting each group, where n is the number of entries.
> 
> **Space:** O(n) for the inverted dict.

> **Interviewers Watch For**
>
> Whether you produce sorted lists. Unsorted output makes the inverted index non-deterministic and harder to test.

> **Common Pitfall**
>
> Assuming values are unique and inverting to a simple key-value mapping. When multiple keys share a value, the last one overwrites the others.

---

## 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_dictionary_inverter)
- [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). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.