# The Shortest Path Home

> Every leaf remembers the road it came from. Bring them all back on one line.

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

Domain: Python · Difficulty: medium · Seniority: L3

## Problem

API responses arrive as dicts nested arbitrarily deep, and the warehouse needs them as single-level rows. Collapse `nested` into a flat dict whose keys are the full path down to each leaf, joined by `separator`, where any value that is not itself a dict is a leaf. An empty inner dict contributes no key, so that branch simply disappears from the result.

## Worked solution and explanation

### What this really is

This is recursion carrying a breadcrumb. The skill being probed: can you remember the path you walked down so far and stitch it onto each leaf, without dribbling a separator onto the front of every root key? Everyone writes the recursive descent. The candidates who stumble are the ones who concatenate prefix, separator, and key unconditionally and hand back keys like '_user_name' with a stray leading underscore on every top-level entry.

---

### Break down the requirements

#### Step 1: Recurse with an accumulating prefix

Thread a prefix string through a recursive helper. When you descend into a sub dict, append the current key to the prefix using the separator. The recursion bottoms out the moment a value is not itself a dict: that value is a leaf and gets written under the full joined path.

#### Step 2: Respect the separator parameter

Default to '_' per the spec, but never hard code it inside the recursion. Threading the separator through the helper keeps the function reusable for dotted '.' notation or any custom delimiter, which is exactly the kind of reuse an interviewer probes with a follow-up.

#### Step 3: Handle the empty prefix correctly

On the first call there is no prefix yet, so the joined key is just the current key, not '_foo'. The guard `f'{prefix}{separator}{key}' if prefix else key` produces clean root keys and avoids leaking a leading separator into every output key.

---

### The solution

**Recursive walker with key path accumulator**

```python
def flatten_json(nested: dict, separator: str = '_') -> dict:
    flat = {}

    def _walk(obj, prefix):
        for key, value in obj.items():
            new_key = f'{prefix}{separator}{key}' if prefix else key
            if isinstance(value, dict):
                _walk(value, new_key)
            else:
                flat[new_key] = value

    _walk(nested, '')
    return flat
```

> **Cost Analysis**
>
> Time is O(n) where n is the number of leaf entries, because each key is visited once. Space is O(n) for the output plus O(d) recursion frames where d is the maximum nesting depth. Building the prefix incrementally keeps the string work amortized cheap; you never rescan a path you already walked.

> **Interviewers Watch For**
>
> Whether you avoid a leading separator on root keys, whether the separator is parameterized rather than baked in, and whether an empty inner dict drops its branch cleanly instead of crashing or emitting a half-formed key. An empty input dict should return an empty dict, not raise.

> **Common Pitfall**
>
> Concatenating prefix, separator, and key on every level (`prefix + separator + key`) yields '_user_name' for top-level entries. Guard the empty prefix or the whole output ends up wearing stray underscores, and the diff against the expected result is one silent character per key.

---

## Common follow-up questions

- How would you also flatten lists by index, like items_0_name? _(Extend the recursion to handle isinstance(value, list) and append the index to the prefix. Discuss whether the index should reuse the separator or switch to bracket notation.)_
- How would you reverse the operation and unflatten? _(Split each key on the separator, walk into a fresh dict creating sub dicts as needed, and assign the leaf. Talk through what happens when a key path collides with an existing leaf.)_
- What if two paths collide after flattening? _(For example {'a_b': 1, 'a': {'b': 2}} with '_' separator both produce a_b. Either raise on collision or pick a deterministic winner, but surface the choice rather than silently overwrite.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_shortest_path_home)
- [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.