Organization Reporting Chain

Coding Software Engineer Reported Apr, 2026 High Frequency

Problem Overview

You receive an organizational hierarchy as a list[list[str]].

Every nested list follows this layout:

[manager, report_1, report_2,...]

For instance:

[
    ["R", "S", "T"],
    ["S", "V"],
    ["T", "U"],
]

represents the following relationships:

• R is the manager of S and T
• S is the manager of V
• T is the manager of U

The resulting reporting layout is:

R
....S
........V
....T
........U

This question generally contains three core stages, although certain interviewers include a fourth extension.

Assume all of the following:

• The provided data forms a valid reporting tree
• Exactly one person has no manager above them
• Reports must be displayed in the order in which they occur in the input
• One depth level is shown with four dots (....)

Follow-Up: Lowest Common Manager

Some interviewers continue with this extension:

For two employees, determine their lowest shared manager.

For the same hierarchy:

lowest_common_manager("T", "V") == "R"

Follow-Up Solution

Because the parent mapping is already available, the lowest-common-manager extension is direct to implement:

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")

    ancestor_names = set()
    name = employee1
    ancestor_names.add(name)

    while name in parent:
        name = parent[name]
        ancestor_names.add(name)

    name = employee2
    while name not in ancestor_names:
        name = parent[name]

    return name

Full Reference Implementation

If additional extensions keep arriving, it is usually preferable to consolidate the behavior in a reusable OrgChart class.

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

relations = [
    ["R", "S", "T"],
    ["S", "V"],
    ["T", "U"],
]

chart = OrgChart(relations)

print(chart.render_full_chain())
# R
#....S
#........V
#....T
#........U

print(chart.all_skip_level_pairs())
# [('R', 'V'), ('R', 'U')]

print(chart.render_chain_for("S"))
# R
#....S
#........V

print(chart.lowest_common_manager("T", "V"))
# R

Complexity

Let n denote the employee count.

• Graph construction: O(n)
• Part 1 rendering: O(n)
• Part 2 skip-level-pair generation: O(n)
• Part 3 selected-chain rendering: O(h + s)
  • h is the root-to-target height
  • s is the number of nodes in the target's subtree
• Lowest common manager lookup: O(h)
• Memory usage: O(n)

Starter Code

def render_full_chain(relations: list[list[str]]) -> str:
    pass