Roots and Branches

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

Domain
Python
Difficulty
medium
Seniority
L5
Asked in
Airbnb

Problem

A storage indexer hands you object keys as slash-separated paths, and you need them folded into a nested dict that mirrors the directory layout: every directory segment maps to an inner dict and every file (the final segment) maps to None. Paths that share a leading directory must collapse onto the same node instead of clobbering each other, and an empty list yields an empty dict.

Flat strings carry a hierarchy. Recover it.

Example 1

Input:

paths = ["src/main.py","src/utils/helper.py","README.md","src/utils/config.py"]

Output:

{"src":{"utils":{"config.py":null,"helper.py":null},"main.py":null},"README.md":null}

Example 2

Input:

paths = ["a/b/c/d.txt"]

Output:

{"a":{"b":{"c":{"d.txt":null}}}}

Worked solution and explanation

What this really is

Under the file-system costume this is a trie insert: you thread each path into a shared prefix structure one segment at a time. Anyone can split on the slash and nest dicts. The thing that separates candidates is prefix sharing: when the second path under src/ shows up, do you reuse the src node you already created, or do you replace it with a fresh {} and silently lose the first file? Get that wrong and src/main.py vanishes the moment src/utils/helper.py is inserted.

Walking it

Step 1: Separate the directories from the file

'src/utils/helper.py'.split('/') gives ['src', 'utils', 'helper.py']. Peel the last element off as the filename and treat everything before it as the directory chain: *directories, filename = parts.

Step 2: Descend, reusing existing nodes

Start at the root dict and descend one directory at a time, calling setdefault at each level. The key move is that descent always lands on the node that is already there when one exists, so files inserted by earlier paths stay put.

Step 3: Mark the leaf file as None

Once you are standing on the deepest directory node, write the filename with a value of None. That None is what distinguishes a file from an (empty) directory dict downstream.

The solution

Iterative trie insert with setdefault
def build_file_tree(paths: list[str]) -> dict:
    tree = {}
    for path in paths:
        *directories, filename = path.split('/')
        node = tree
        for directory in directories:
            node = node.setdefault(directory, {})
        node[filename] = None
    return tree
Manual existence check
for directory in directories: if directory not in node: node[directory] = {} node = node[directory] Correct, but the create-then-descend is two statements and one stray reassignment turns it into the overwrite bug.
setdefault
for directory in directories: node = node.setdefault(directory, {}) Same compute, one line, and reuse-or-create is atomic so the bug cannot sneak in.

Common follow-up questions