Where the Buck Stops

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

Domain
Python
Difficulty
hard
Seniority
L5
Asked in
Airbnb

Problem

A directory export gives you reporting lines as (manager, report) pairs in no particular order, and you need the org chart back. Return the reporting hierarchy as nested dictionaries, with the one person nobody reports to at the top.

A pile of reporting lines, no order to them. Somewhere in the bag sits the one with no boss.

Example 1

Input:

pairs = [["Hana","Kit"],["Gus","Hana"],["Gus","Ivy"]]

Output:

{"Gus":{"Ivy":{},"Hana":{"Kit":{}}}}

Example 2

Input:

pairs = [["Ada","Bo"],["Ada","Cy"],["Bo","Di"]]

Output:

{"Ada":{"Bo":{"Di":{}},"Cy":{}}}

Worked solution and explanation

What this problem really is

This is a tree reconstruction from an unordered bag of edges, wearing an org-chart costume. Everyone builds the nesting fine; the whole thing turns on one question the business framing hides: which name is the root? The trap is to assume the export is sorted top-down and grab pairs[0][0] as the CEO. It usually looks right on a tidy example and then quietly betrays you, because a directory export has no ordering guarantee. A report can appear in an earlier pair than its own manager. Trust the order and you build a perfectly shaped tree hanging off the wrong node.

Trust the order (breaks)
root = pairs[0][0], then nest as you scan. Feed it [["Hana", "Kit"], ["Gus", "Hana"], ...] and it crowns Hana, even though Gus sits above her. Correct shape, wrong root.
Derive the root (correct)
Collect every name that appears as a report into a set, then the root is the one manager not in that set. Now the pairs can arrive in any order and the answer is identical.

Building it

Step 1: Index reports by manager in one pass

Walk the pairs once. For each (manager, report), append the report to children[manager] and also seed children[report] to an empty list so leaves are represented. Appending as you go preserves the input order of reports under each manager, which is the ordering the visible tests lock in.

Step 2: Isolate the root by set difference

While scanning, add every report to a reports set. The root is any key in children that is not in reports: the person who manages but is never managed. This is the load-bearing line. It reads the answer off the data instead of the input order, so a scrambled export resolves the same as a tidy one.

Step 3: Nest recursively from the root

A small recursive helper turns the adjacency map into nesting: each person becomes a dict mapping each of their reports to that report's own subtree. Leaves bottom out at an empty dict because their children list is empty. Return a single-entry dict keyed by the root.

Reconstruct the hierarchy
def build_tree(pairs: list[tuple[str, str]]) -> dict:
    children: dict[str, list[str]] = {}
    reports = set()
    for manager, report in pairs:
        children.setdefault(manager, []).append(report)
        children.setdefault(report, [])
        reports.add(report)

    roots = [person for person in children if person not in reports]
    if not roots:
        return {}

    def subtree(person: str) -> dict:
        return {report: subtree(report) for report in children[person]}

    return {roots[0]: subtree(roots[0])}

One pass to index and to find the root, then a recursive walk. Linear in the number of pairs.

Common follow-up questions