Lowest common manager in an org chart: Frontier Interview's solution

Question: Lowest common manager in an org chart

Companies: Amazon

Difficulty: Medium

Problem statement

A company's reporting structure is a rooted tree. Each person is an Employee with a unique name and a list reports of the people who report to them directly. The root is the CEO, and every other employee has exactly one direct manager.

Implement:

def lowest_common_manager(root: Employee, a: Employee, b: Employee) -> Employee

Return the lowest common manager of a and b: the employee farthest from the CEO whose reporting tree contains both of them. An employee counts as part of their own reporting tree, so if a manages b (directly or through others), the answer is a.

Constraints

1 <= number of employees <= 10^5. The tree may be very deep (a long single chain), so be careful with recursion depth.
Each employee has any number of direct reports.
Ask your interviewer whether a and b are guaranteed to be in the tree. If not, return None when either is missing.

Example 1

            Maya
          /  |   \
      Omar  Lin   Ravi
      /  \          |
   Ines  Theo      Kofi

lowest_common_manager(Maya, Ines, Theo) returns Omar.
lowest_common_manager(Maya, Theo, Kofi) returns Maya.

Example 2

Using the same tree, lowest_common_manager(Maya, Omar, Ines) returns Omar, because Omar manages Ines and counts as part of his own reporting tree.

Expect follow-ups such as finding the common manager of a whole group of employees, or answering many queries quickly on the same org chart.

Approach

The org chart is a rooted n-ary tree, so the lowest common manager is the
lowest common ancestor (LCA) of the two employees. "Lowest" means deepest:
of all the people who have both employees in their reporting chain, pick the
one farthest from the top. An employee counts as being in their own chain, so
if one employee manages the other (directly or indirectly), the manager is
the answer.

Brute force: compare chains of command. Walk the tree once to record each
employee's manager, build the chain from each target up to the root, put one
chain in a set, and walk the other upward until it hits a member of the set.
That is O(n) time and O(n) extra space for the parent map. It is a fine first
answer and it is the right shape when queries repeat (see follow-ups).

Optimal single pass: count targets per subtree. Do one post-order DFS. Each
call returns how many of the targets live in its subtree (itself included).
The first node, in post-order, whose count reaches the number of targets is
the answer. Post-order guarantees that children finish before their parent,
so the first node to see both targets is the deepest one. Once the answer is
set, every ancestor also sees the full count, but we only keep the first.

Invariants:

count(node) = number of distinct targets in node's subtree.
The answer is set exactly once, at the deepest node with count == k.
If the full count is never reached, a target is not in the tree, and we
return None instead of a wrong manager. This is the trap in the binary
LCA "return the node if it matches" shortcut: it assumes both targets exist.

Counting (instead of the classic "return the node you found") generalizes for
free to any number of employees, which is the usual part 2.

Real org charts can be thousands of levels deep in a bad case (a long chain),
so the code uses an explicit stack rather than Python recursion.

Code

from __future__ import annotations

from dataclasses import dataclass, field
from typing import Iterable, Optional


@dataclass(eq=False)
class Employee:
    name: str
    reports: list[Employee] = field(default_factory=list)


def lowest_common_manager(
    root: Optional[Employee], targets: Iterable[Employee]
) -> Optional[Employee]:
    """Deepest employee whose subtree contains every target (a node is in its own subtree).

    Returns None if the tree is empty, no targets are given, or any target is missing.
    """
    wanted = {id(t) for t in targets}
    if root is None or not wanted:
        return None

    counts: dict[int, int] = {}
    answer: Optional[Employee] = None
    # Iterative post-order: (node, children_done)
    stack: list[tuple[Employee, bool]] = [(root, False)]
    while stack:
        node, done = stack.pop()
        if not done:
            stack.append((node, True))
            for child in node.reports:
                stack.append((child, False))
            continue
        total = 1 if id(node) in wanted else 0
        for child in node.reports:
            total += counts.pop(id(child))
        counts[id(node)] = total
        if answer is None and total == len(wanted):
            answer = node
    return answer


def lcm_pair(root: Optional[Employee], a: Employee, b: Employee) -> Optional[Employee]:
    """The classic two-employee form of the question."""
    return lowest_common_manager(root, [a, b])


def lcm_by_chain(root: Employee, a: Employee, b: Employee) -> Optional[Employee]:
    """Brute force: build a parent map, then intersect the two chains of command."""
    parent: dict[int, Optional[Employee]] = {id(root): None}
    stack = [root]
    while stack:
        node = stack.pop()
        for child in node.reports:
            parent[id(child)] = node
            stack.append(child)
    if id(a) not in parent or id(b) not in parent:
        return None

    seen: set[int] = set()
    cur: Optional[Employee] = a
    while cur is not None:
        seen.add(id(cur))
        cur = parent[id(cur)]
    cur = b
    while cur is not None:
        if id(cur) in seen:
            return cur
        cur = parent[id(cur)]
    return None  # unreachable: both chains end at root


if __name__ == "__main__":
    #            ceo
    #        /    |     \
    #     vp_a   vp_b   vp_c
    #    /   \     |
    #  m1    m2    m3
    #  / \          |
    # e1  e2        e3
    e1, e2, e3 = Employee("e1"), Employee("e2"), Employee("e3")
    m1 = Employee("m1", [e1, e2])
    m2 = Employee("m2")
    m3 = Employee("m3", [e3])
    vp_a = Employee("vp_a", [m1, m2])
    vp_b = Employee("vp_b", [m3])
    vp_c = Employee("vp_c")
    ceo = Employee("ceo", [vp_a, vp_b, vp_c])

    for f in (lcm_pair, lcm_by_chain):
        assert f(ceo, e1, e2) is m1
        assert f(ceo, e1, m2) is vp_a
        assert f(ceo, e2, e3) is ceo
        assert f(ceo, m1, e2) is m1          # manager of the other
        assert f(ceo, e3, e3) is e3          # same employee
        assert f(ceo, ceo, vp_c) is ceo
        assert f(ceo, e1, Employee("x")) is None  # not in the org

    assert lowest_common_manager(ceo, [e1, e2, m2]) is vp_a
    assert lowest_common_manager(ceo, [e1, e3, vp_c]) is ceo
    assert lowest_common_manager(ceo, []) is None
    assert lowest_common_manager(None, [e1]) is None

    # Deep chain: no recursion limit
    deep_root = cur = Employee("d0")
    nodes = [cur]
    for i in range(1, 50_000):
        nxt = Employee(f"d{i}")
        cur.reports.append(nxt)
        cur = nxt
        nodes.append(cur)
    assert lcm_pair(deep_root, nodes[30_000], nodes[-1]) is nodes[30_000]
    print("ok")

Complexity

lowest_common_manager: O(n) time, one visit per employee. O(h) for the
stack in a chain-shaped tree up to O(n) for the stack plus pending counts in
a wide tree; overall O(n) worst case. It accepts k targets at no extra cost
beyond the O(k) set.
lcm_by_chain: O(n) time and O(n) space for the parent map; the chain walk
itself is O(h).
With a prebuilt parent map and depths, each pair query is O(h) and needs no
traversal; with binary lifting it is O(log n) per query after O(n log n)
preprocessing.

Test cases

Using the tree in the code (ceo -> vp_a, vp_b, vp_c; vp_a -> m1, m2;
m1 -> e1, e2; vp_b -> m3 -> e3):

(e1, e2) -> m1 (siblings under the same manager)
(e1, m2) -> vp_a (different depths)
(e2, e3) -> ceo (different branches, meet only at the root)
(m1, e2) -> m1 (one employee manages the other)
(e3, e3) -> e3 (same employee twice)
(ceo, vp_c) -> ceo (root is one of the targets)
(e1, outsider) -> None (target not in the org)
[e1, e2, m2] -> vp_a (three employees)
Empty target list or empty tree -> None
A 50,000-level chain -> correct answer with no recursion error

Follow-ups

Any number of employees. The counting DFS already handles k targets:
the answer is the first node whose subtree count reaches k. The chain
approach generalizes by intersecting k chains, or by folding pairwise LCA
over the list (LCA is associative), which is O(k * h) with a parent map.
Many queries on the same org. Precompute parent and depth in one pass.
Then each query lifts the deeper employee to the same depth and walks both
up together: O(h). For very deep trees use binary lifting (O(log n) per
query, O(n log n) memory), or an Euler tour plus a sparse-table range
minimum for O(1) queries.
Input is a list of records, not a tree. Given rows like
(id, name, manager_id), build children and parent maps, find the root
(the one row with no manager), and reject the input if there are zero or
several roots, a cycle, or a manager id that does not exist. Then reuse the
parent-map method directly; no tree object is needed.
Lookup by name. Keep a name -> Employee dict built during the first
traversal. Handle duplicate names explicitly (error, or use ids), because
the question promises uniqueness but real data does not.
The org changes (hires, departures, re-orgs). With parent pointers a
move is O(1) and pair queries stay O(h). If queries are heavy and edits are
rare, rebuild the binary-lifting table lazily; for heavy edits on huge
trees, link-cut trees give O(log n) amortized for both, which is worth
naming but not coding.

Interviewer expectations

Mid-level (L4)

Recognizes the problem as LCA on an n-ary tree and states the definition
(deepest node, a node counts as its own descendant).
Writes a working recursive solution for two employees with O(n) time.
Tests siblings, different branches, and the "one manages the other" case.

Senior (L5)

Asks whether both employees are guaranteed to exist and returns None
correctly when they are not, instead of relying on the binary-LCA shortcut.
Uses the counting formulation so k employees falls out naturally.
Mentions recursion depth on deep or chain-shaped orgs and offers an
iterative traversal; compares the parent-map method and when it wins.

Staff (L6+)

Separates one-off queries from a query service: preprocess once
(parent/depth, binary lifting, or Euler tour + RMQ) and states the trade-offs.
Handles messy input: building the tree from records, validating a single
root, cycles, dangling manager ids, duplicate names.
Discusses keeping answers correct while the org changes, and what to cache
and invalidate.