Design an employee hierarchy with is_manager queries

01The design, in the six-step framework

1. Requirements and use cases

A recent Google phone screen reported this as "manager and peer relationships with is_manager queries". Relationships arrive one at a time, and the queries must reflect everything said so far, so this is a live graph behind a tiny API.

• A caller declares that a manages b.
• A caller declares that a and b are peers; peers share the same manager, and peer-of-a-peer is a peer.
• A caller asks whether a is a manager of b, directly or through a chain.
• A caller asks whether two people are peers, and lists a person's direct reports.
• The structure refuses a statement that would create a cycle or give a peer group two managers.

Out of scope: titles, dotted-line managers, multi-parent matrices, persistence. Assumptions to state: people are strings; a person has at most one manager; declaring a peer inherits the other's manager. Non-functional constraints: updates near constant time; is_manager O(depth) when writes are frequent, and O(1) when the org is read-heavy, which is the trade-off the interviewer is after.

2. Core entities and relationships

• PeerGroups: a union-find structure; each person belongs to exactly one group, and peers are merged.
• OrgChart: the public API; stores one manager per group, never per person.
• AncestryIndex: an optional precomputed snapshot of the tree (entry and exit numbers from a depth-first walk) for O(1) queries.
• Version: a counter on the chart that marks a snapshot stale.

The key modelling move is that the graph's nodes are peer groups, not people. The chart composes the union-find because it is private machinery, and the index because it is a disposable cache of the chart's own tree.

3. Interfaces and key methods

class PeerGroups:
    def find(self, x: str) -> str:
        """Representative of x's group, with path compression."""
    def union(self, a: str, b: str) -> str:
        """Merge two groups by size; return the surviving representative."""

class OrgChart:
    def set_manager(self, manager: str, report: str) -> None:
        """report's group gets manager's group as parent; raise HierarchyError on a cycle or conflict."""
    def set_peer(self, a: str, b: str) -> None:
        """Merge groups; their managers and reports merge; raise on conflicting managers."""
    def is_manager(self, a: str, b: str) -> bool:
        """True if a's group is a strict ancestor of b's group."""
    def is_peer(self, a: str, b: str) -> bool: ...
    def direct_reports(self, a: str) -> set[str]: ...

class AncestryIndex:
    def is_ancestor(self, a: str, b: str) -> bool:
        """O(1) from depth-first entry and exit numbers."""

Invariants: manager maps group representatives only; the group graph is a forest, so walking up always terminates; reports[g] is exactly the set of groups whose manager is g. Peers are not managers of each other: is_manager compares groups strictly.

4. Design patterns and the choices behind them

Peer groups collapse the graph

Modelling a peer edge per pair makes "peers share a manager" a rule to re-check everywhere. Union-find turns it into structure: there is one manager per group, so the rule cannot be broken. This is a graph hidden behind an API whose nodes were chosen to make the invariant automatic. The merge is near constant time amortised.

Walk up by default, index on demand

With writes interleaved, is_manager walks the parent chain from b: O(depth), and org depth is small, typically under fifteen. A versioned snapshot gives O(1) reads: number nodes on entry and exit of a depth-first walk, and a is an ancestor of b exactly when b's interval sits inside a's:

enter(a) < enter(b) and leave(b) < leave(a)

A rebuild is O(n), so it only pays when reads far outnumber writes. A precomputed set of all ancestors per person is the rejected option: O(n × depth) memory, painful on every reorganisation.

Refuse bad statements at the door

Cycles and double managers are caller errors, and silently overwriting would hide them. The method contract raises and leaves the state unchanged. Reading the statement "a manages b" as (manager, report) in the signature prevents the most likely argument mix-up.

5. Core flow and code

1. set_manager(a, b) finds both groups. If they are equal, or a's group is below b's, it raises.
2. It raises if b's group already has a different manager; otherwise it records the link in manager and reports, and bumps version.
3. set_peer(a, b) checks that the managers agree and that neither group manages the other, then unions, moving the manager and reports to the surviving representative.
4. is_manager(a, b) uses a fresh index if one exists, otherwise walks up from b's group.

from __future__ import annotations
from typing import Optional


class HierarchyError(Exception): ...


class PeerGroups:
    def __init__(self) -> None:
        self.parent: dict[str, str] = {}
        self.size: dict[str, int] = {}
        self.members: dict[str, set[str]] = {}

    def find(self, x: str) -> str:
        if x not in self.parent:
            self.parent[x], self.size[x], self.members[x] = x, 1, {x}
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a: str, b: str) -> str:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return ra
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.members[ra] |= self.members.pop(rb)
        return ra


class AncestryIndex:
    def __init__(self, reports: dict[str, set[str]], roots: list[str], version: int) -> None:
        self.version = version
        self.enter: dict[str, int] = {}
        self.leave: dict[str, int] = {}
        clock = 0
        for root in roots:
            stack: list[tuple[str, bool]] = [(root, False)]
            while stack:
                node, done = stack.pop()
                clock += 1
                if done:
                    self.leave[node] = clock
                    continue
                self.enter[node] = clock
                stack.append((node, True))
                stack.extend((c, False) for c in reports.get(node, ()))

    def is_ancestor(self, a: str, b: str) -> bool:
        return self.enter[a] < self.enter[b] and self.leave[b] < self.leave[a]


class OrgChart:
    def __init__(self) -> None:
        self.groups = PeerGroups()
        self.manager: dict[str, str] = {}        # group -> manager group
        self.reports: dict[str, set[str]] = {}   # group -> groups reporting to it
        self.version = 0
        self.index: Optional[AncestryIndex] = None

    def _above(self, top: str, group: str) -> bool:
        """True if top is a strict ancestor of group, walking up from group."""
        node = self.manager.get(group)
        while node is not None:
            node = self.groups.find(node)
            if node == top:
                return True
            node = self.manager.get(node)
        return False

    def set_manager(self, manager: str, report: str) -> None:
        m, r = self.groups.find(manager), self.groups.find(report)
        if m == r or self._above(r, m):
            raise HierarchyError("would create a cycle")
        current = self.manager.get(r)
        if current is not None and self.groups.find(current) != m:
            raise HierarchyError(f"{report} already has a manager")
        self.manager[r] = m
        self.reports.setdefault(m, set()).add(r)
        self.version += 1

    def set_peer(self, a: str, b: str) -> None:
        ra, rb = self.groups.find(a), self.groups.find(b)
        if ra == rb:
            return
        if self._above(ra, rb) or self._above(rb, ra):
            raise HierarchyError("a manager cannot be a peer of a report")
        ma, mb = self.manager.get(ra), self.manager.get(rb)
        if ma and mb and self.groups.find(ma) != self.groups.find(mb):
            raise HierarchyError("peers must share a manager")
        boss = ma or mb
        kids = self.reports.pop(ra, set()) | self.reports.pop(rb, set())
        for g in (ra, rb):
            self.manager.pop(g, None)
            if boss:
                self.reports.get(self.groups.find(boss), set()).discard(g)
        root = self.groups.union(a, b)
        if boss:
            self.manager[root] = self.groups.find(boss)
            self.reports.setdefault(self.manager[root], set()).add(root)
        if kids:
            self.reports[root] = kids
            for k in kids:
                self.manager[k] = root
        self.version += 1

    def is_manager(self, a: str, b: str) -> bool:
        ra, rb = self.groups.find(a), self.groups.find(b)
        if self.index and self.index.version == self.version:
            return self.index.is_ancestor(ra, rb)
        return self._above(ra, rb)

    def is_peer(self, a: str, b: str) -> bool:
        return self.groups.find(a) == self.groups.find(b)

    def direct_reports(self, a: str) -> set[str]:
        out: set[str] = set()
        for g in self.reports.get(self.groups.find(a), set()):
            out |= self.groups.members[g]
        return out

    def freeze_for_reads(self) -> None:
        """Build the O(1) snapshot; any later write makes it stale automatically."""
        groups = {self.groups.find(p) for p in list(self.groups.parent)}
        roots = sorted(g for g in groups if g not in self.manager)
        self.index = AncestryIndex(self.reports, roots, self.version)

6. Extensions, concurrency and what interviewers probe

• Peer before manager: set_peer(a, b) then set_manager(m, a) must make m manage b too. Storing the manager per group makes that automatic, and this ordering is the main test case the interviewer tries.
• Reorganisation: moving a team under a new manager is a parent change on one group, cheap in this model. In a precomputed ancestor table it rewrites every descendant.
• Removing a person: union-find does not support splitting. A leave needs a rebuild of that group, or a tombstone. If removal is a stated requirement, say so early, because it changes the structure choice.
• Snapshot staleness: the version check makes a stale index harmless, since queries silently fall back to the walk. With threads, a read-write lock lets many is_manager calls share, and note that path compression makes find a write.
• Scoring variant: a reported cousin scores people from reporting relationships; a post-order walk of the same tree computes team sizes or scores.
• Test first: transitive is_manager; peers report false both ways; a two-node cycle raises; peer-then-manager and manager-then-peer agree; the index answers the same as the walk on a random tree.
• Common mistake: storing managers per person, then having to copy on every peer merge and missing one.

02Where this question was reported

• Land the Lab · 'Manager and peer relationships with is_manager queries'
• interviewing.io · 'Employee hierarchy' scoring from reporting relationships