# Where the Buck Stops > A pile of reporting lines, no order to them. Somewhere in the bag sits the one with no boss. Canonical URL: Domain: Python · Difficulty: hard · Seniority: L5 ## 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. ## 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. > **The one move that cracks it** > > The root is the single name that manages someone but is never anyone's report. That is a set difference: all managers minus all reports. Compute it from the data and the pair order stops mattering entirely. Everything else is bookkeeping. **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** ```python 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.* > **The seed-the-leaf line people drop** > > Skipping children.setdefault(report, []) works right up until a leaf needs to be visited. When subtree recurses into a report that never appeared as a manager, children[report] raises a KeyError. Seeding an empty list for every name in the same pass makes leaves first-class and the recursion total. > **What signals seniority here** > > The tell is whether you ask about ordering before you code. A strong candidate says out loud: the pairs are unsorted, so the root cannot come from position, and confirms whether the bag is one tree or a forest. Reaching for pairs[0] without flagging the assumption is the exact thing this question is built to expose. > **Where this bites in production** > > Reporting-line, category, and dependency exports almost never come sorted parent-first. Code that assumes they do passes review on the sample fixture and then mis-roots the first real dump, silently reparenting a whole subtree. Deriving the root from set membership is the difference between a job that is robust to export order and one that is a latent incident. ## Common follow-up questions - The export can now contain several independent org charts. Return a list of trees instead of one. _(Generalizes root-finding from one root to every manager not appearing as a report; tests whether the set-difference insight was understood or memorized.)_ - How would you detect a cycle (someone transitively reporting to themselves) instead of trusting the input to be a valid tree? _(Pushes toward tracking visited nodes during the walk and reasoning about malformed input.)_ - The input is 50 million pairs. Does the recursive nesting still hold up, and what would you change? _(Probes recursion depth limits and an iterative or explicit-stack rewrite for deep hierarchies.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/where_the_buck_stops) - [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.