Report Chain

Role: Software Engineer

Problem Overview

You are given an org chart as a list[list[str]].

Each inner list has the form:

python

[manager, report_1, report_2, ...]

For example:

python

[
    ["A", "B", "C"],
    ["B", "E"],
    ["C", "D"],
]

means:

A manages B and C
B manages E
C manages D

This produces the report chain:

text

A
....B
........E
....C
........D

This interview commonly has three main parts, and some interviewers add a fourth follow-up.

Assume:

The input represents a valid management tree
There is exactly one top-level manager
Child order should match the order given in the input
Four dots (....) represent one indentation level

Part 1: Print The Full Report Chain

Problem Statement

Build the org tree and print the full hierarchy using the indentation format above.

Example

python

relations = [
    ["A", "B", "C"],
    ["B", "E"],
    ["C", "D"],
]

Output:

text

A
....B
........E
....C
........D

Part 1 Solution

Build a children adjacency list and find the root, then do a DFS render.

python

from collections import defaultdict

def build_children(relations: list[list[str]]) -> tuple[dict[str, list[str]], str]:
    children: dict[str, list[str]] = defaultdict(list)
    parent: dict[str, str] = {}
    all_people = set()

    for row in relations:
        manager, *reports = row
        all_people.add(manager)
        children[manager]

        for report in reports:
            all_people.add(report)
            children[manager].append(report)
            children[report]
            parent[report] = manager

    roots = [person for person in all_people if person not in parent]
    if len(roots) != 1:
        raise ValueError("Expected exactly one root")

    return children, roots[0]

def render_full_chain(relations: list[list[str]]) -> str:
    children, root = build_children(relations)
    lines: list[str] = []

    def dfs(node: str, depth: int) -> None:
        lines.append(f"{'....' * depth}{node}")
        for child in children[node]:
            dfs(child, depth + 1)

    dfs(root, 0)
    return "\n".join(lines)

Part 2: Emit All Skip-Level Pairs

Problem Statement

As a manager of managers, you may want to hold skip-level meetings with employees who are exactly two levels below you.

Return all valid (manager, employee) skip-level pairs.

Using the same tree:

A can skip over B to meet E
A can skip over C to meet D

Output can be returned in any convenient format as long as the pairs are correct.

Example

python

[("A", "E"), ("A", "D")]

Part 2 Solution

Once you have the tree, every valid skip-level pair is just a (manager, grandchild) relationship.

python

def all_skip_level_pairs(relations: list[list[str]]) -> list[tuple[str, str]]:
    children, root = build_children(relations)
    pairs: list[tuple[str, str]] = []

    def dfs(node: str) -> None:
        for child in children[node]:
            for grandchild in children[child]:
                pairs.append((node, grandchild))
            dfs(child)

    dfs(root)
    return pairs

Part 3: Given A Person, Print Only Their Chain

Problem Statement

Given a target employee, print:

the single management path from the root down to that employee
all descendants under that target employee

The output must use the same indentation format as Part 1.

Example

For target B, using:

python

relations = [
    ["A", "B", "C"],
    ["B", "E"],
    ["C", "D"],
]

output:

text

A
....B
........E

If the target is C, the output is:

text

A
....C
........D

Part 3 Solution

This is the part that usually trips people up. You need both:

the path from the root down to the target
the full subtree under the target

The cleanest way is to keep a parent map so you can reconstruct the upward chain, then render only the target's descendants afterward.

The key detail is that the target should appear exactly once:

print the target as part of the root-to-target path
then DFS only the target's children, not the target again

python

from collections import defaultdict

def build_graph(
    relations: list[list[str]],
) -> tuple[dict[str, list[str]], dict[str, str], str]:
    children: dict[str, list[str]] = defaultdict(list)
    parent: dict[str, str] = {}
    all_people = set()

    for row in relations:
        manager, *reports = row
        all_people.add(manager)
        children[manager]

        for report in reports:
            all_people.add(report)
            children[manager].append(report)
            children[report]
            parent[report] = manager

    roots = [person for person in all_people if person not in parent]
    if len(roots) != 1:
        raise ValueError("Expected exactly one root")

    return children, parent, roots[0]

def render_chain_for(relations: list[list[str]], target: str) -> str:
    children, parent, _root = build_graph(relations)
    if target not in children:
        raise ValueError(f"Unknown employee: {target}")

    path = [target]
    current = target
    while current in parent:
        current = parent[current]
        path.append(current)
    path.reverse()

    lines: list[str] = []
    for depth, name in enumerate(path):
        lines.append(f"{'....' * depth}{name}")

    def dfs_subtree(node: str, depth: int) -> None:
        lines.append(f"{'....' * depth}{node}")
        for child in children[node]:
            dfs_subtree(child, depth + 1)

    for child in children[target]:
        dfs_subtree(child, len(path))

    return "\n".join(lines)

Follow-Up: Lowest Common Manager

Some interviewers extend the problem and ask:

Given two employees, return their lowest common manager.

For the same tree:

python

lowest_common_manager("C", "E") == "A"

Follow-Up Solution

The parent map also makes the lowest-common-manager follow-up straightforward:

python

def lowest_common_manager(
    relations: list[list[str]], employee1: str, employee2: str
) -> str:
    children, parent, _root = build_graph(relations)
    if employee1 not in children or employee2 not in children:
        raise ValueError("Unknown employee")

    ancestors = set()
    current = employee1
    ancestors.add(current)

    while current in parent:
        current = parent[current]
        ancestors.add(current)

    current = employee2
    while current not in ancestors:
        current = parent[current]

    return current

Full Reference Implementation

If the interviewer keeps adding follow-ups, it is usually better to unify everything into one reusable OrgChart class.

python

from collections import defaultdict

class OrgChart:
    INDENT = "...."

    def __init__(self, relations: list[list[str]]):
        self.children: dict[str, list[str]] = defaultdict(list)
        self.parent: dict[str, str] = {}
        self._appearance_order: list[str] = []
        seen = set()

        for row in relations:
            if not row:
                continue

            manager, *reports = row
            self._remember(manager, seen)
            self.children[manager]

            for report in reports:
                self._remember(report, seen)
                self.children[manager].append(report)
                self.children[report]
                self.parent[report] = manager

        roots = [name for name in self._appearance_order if name not in self.parent]
        if len(roots) != 1:
            raise ValueError("Input must contain exactly one root")

        self.root = roots[0]

    def _remember(self, name: str, seen: set[str]) -> None:
        if name not in seen:
            seen.add(name)
            self._appearance_order.append(name)

    def render_full_chain(self) -> str:
        lines: list[str] = []
        self._render_subtree(self.root, 0, lines)
        return "\n".join(lines)

    def all_skip_level_pairs(self) -> list[tuple[str, str]]:
        pairs: list[tuple[str, str]] = []

        def dfs(node: str) -> None:
            for child in self.children[node]:
                for grandchild in self.children[child]:
                    pairs.append((node, grandchild))
                dfs(child)

        dfs(self.root)
        return pairs

    def render_chain_for(self, target: str) -> str:
        if target not in self.children:
            raise ValueError(f"Unknown employee: {target}")

        path = self._path_from_root(target)
        lines: list[str] = []

        for depth, name in enumerate(path):
            lines.append(f"{self.INDENT * depth}{name}")

        target_depth = len(path) - 1
        for child in self.children[target]:
            self._render_subtree(child, target_depth + 1, lines)

        return "\n".join(lines)

    def lowest_common_manager(self, employee1: str, employee2: str) -> str:
        if employee1 not in self.children or employee2 not in self.children:
            raise ValueError("Unknown employee")

        ancestors = set()
        current = employee1
        ancestors.add(current)

        while current in self.parent:
            current = self.parent[current]
            ancestors.add(current)

        current = employee2
        while current not in ancestors:
            current = self.parent[current]

        return current

    def _path_from_root(self, target: str) -> list[str]:
        path = [target]
        current = target

        while current in self.parent:
            current = self.parent[current]
            path.append(current)

        path.reverse()
        return path

    def _render_subtree(self, node: str, depth: int, lines: list[str]) -> None:
        lines.append(f"{self.INDENT * depth}{node}")
        for child in self.children[node]:
            self._render_subtree(child, depth + 1, lines)

Example Usage

python

relations = [
    ["A", "B", "C"],
    ["B", "E"],
    ["C", "D"],
]

chart = OrgChart(relations)

print(chart.render_full_chain())
# A
# ....B
# ........E
# ....C
# ........D

print(chart.all_skip_level_pairs())
# [('A', 'E'), ('A', 'D')]

print(chart.render_chain_for("B"))
# A
# ....B
# ........E

print(chart.lowest_common_manager("C", "E"))
# A

Complexity

Let n be the number of employees.

Build graph: O(n)
Part 1 render: O(n)
Part 2 skip-level pairs: O(n)
Part 3 target chain render: O(h + s)
h is the height from root to target
s is the size of the target's subtree
Lowest common manager: O(h)
Space: O(n)