Report Chain / Org Tree

Build an organizational reporting hierarchy from a list of (employee, manager) pairs, then answer multi-part queries against it: pretty-print the indented tree, find skip-level pairs, locate an individual's full lineage, and compute the lowest common manager. Requirements Input describes manager → direct-report chains rooted at some manager. Two input shapes appear; confirm which before coding: List-of-lists (most common): list[list[str]] where each inner list is [manager, report_1, report_2, ...]. Example: [["A","B","C"], ["B","E"], ["C","D"]]. List-of-strings: each string is a comma-joined chain, e.g. ['A,B,C', 'C,D', 'B,E'] — split on , to recover the same [manager, *reports] shape. Both describe A managing B and C, B managing E, C managing D. Assume a valid management tree: exactly one top-level manager (single root), and child order matches the order given in the input. The prompt walks through five parts; most loops cover 1–3, parts 4–5 are stretch: Part 1 — Build and print. Parse the input into a tree (single root expected). Pretty-print the tree with indentation showing depth. .... (four dots) per level is the canonical indent; the exact indent string (4 spaces, dots, dashes) is interviewer choice — confirm before coding. Part 2 — Skip-level pairs. Emit all valid (manager, employee) skip-level pairs, i.e. every (manager, grandchild) where the employee is exactly two levels below the manager. Return in any convenient format as long as the pairs are correct. Minority variant: some loops instead give two specific employees and ask whether they are in an ancestor-descendant relationship (one reports up to the other through any number of levels), returning the relationship or false — clarify before coding whether Part 2 is "enumerate all skip-level pairs" or "test two given employees". Part 3 — Person lineage. Given a target employee, print the single management path from the root down to that employee, followed by all descendants under that employee. The target must appear exactly once (as the last node of the root-to-target path). Output format mirrors the part 1 indented tree. Part 4 — Lowest common manager. Given two employees, return the lowest manager that has both in their subtree (LCA). The interviewer expects the answer in terms of node identity, not depth. Part 5 — Often skipped. Variants include serializing the org back to the input format, finding all employees at exactly N levels below a given manager, or detecting an invalid input (cycle, multiple roots). The interviewer flags two things on the rubric: clean parsing of the input format, and a clear separation between tree construction and tree querying. Mixing the two into one pass is the most common failure mode. Function signatures Build a children adjacency list plus a parent map and a single root in one pass, validating the single-root invariant: from collections import defaultdict def build_graph(relations: list[list[str]]) -> tuple[dict[str, list[str]], dict[str, str], str]: ... # returns (children, parent, root) # children[manager] -> reports in input order; parent[report] -> manager. # roots = people with no parent; raise ValueError if len(roots) != 1. def render_full_chain(relations: list[list[str]]) -> str: ... # Part 1: DFS from root, one line per node as f"{'....' * depth}{node}". def all_skip_level_pairs(relations: list[list[str]]) -> list[tuple[str, str]]: ... # Part 2: for each node, for each child, for each grandchild -> (node, grandchild). def render_chain_for(relations: list[list[str]], target: str) -> str: ... # Part 3: walk parent map up to root for the path, then DFS only target's children. # Target printed once (last of path); raise ValueError if target unknown. def lowest_common_manager(relations: list[list[str]], e1: str, e2: str) -> str: ... # Part 4: collect e1's ancestor set (including e1), walk up from e2 until a node # lands in that set; raise ValueError on unknown employee. Examples Input: ['A,B,C', 'C,D', 'B,E'] Part 1 output: A ....B ........E ....C ........D Part 2 (all skip-level pairs): [('A', 'E'), ('A', 'D')] — A skips over B to reach E, and over C to reach D. Part 3 lineage for target B: A ....B ........E Part 4: lowest common manager of C and E is A. Notes The natural representation is a Map<String, Node> plus a single root pointer. Building both in one pass over the input is correct and idiomatic. Several candidates over-engineered with a custom TreeNode class for part 1 and then ran out of time. A plain Map<String, List<String>> (employee → direct reports) is enough for parts 1–4; only build object-oriented nodes if part 5 starts demanding it. Keep a parent map from the start: it makes both Part 3's upward path and Part 4's LCA trivial. Reconstruct the root-to-target path by walking parent up and reversing. Part 3's lineage output is the most error-prone — getting the indentation correct for the upward chain (manager-of-manager going up) plus the downward subtree requires either two passes or careful pre-computation of depths. The clean pattern: emit the path nodes at depths 0..len(path)-1, then DFS the target's children starting at depth len(path) so the target is not printed twice. Lowest common manager is a textbook tree LCA: walk up from each node, collect ancestor sets, return the first common ancestor. With a parent pointer per node, the iterative two-pointer LCA also works. Common interviewer follow-up: "what if the input has thousands of entries?" Have a clean answer — the algorithm is already O(N); the bottleneck is the LCA call frequency, which can be amortized with binary lifting if asked. If the interviewer keeps stacking follow-ups — unify into one class Rather than re-parsing per query, wrap the maps in one reusable structure built once in __init__, then answer each part as a method: class OrgChart: INDENT = "...." def __init__(self, relations: list[list[str]]): ... # builds children, parent, root def render_full_chain(self) -> str: ... def all_skip_level_pairs(self) -> list[tuple[str, str]]: ... def render_chain_for(self, target: str) -> str: ... def lowest_common_manager(self, e1: str, e2: str) -> str: ... Track first-appearance order of names to pick the root deterministically (roots = [name for name in appearance_order if name not in parent]) and raise if there isn't exactly one. Complexity (per part) Let n be the number of employees, h the height from root to a target, s the size of a target's subtree. Build graph: O(n); Part 1 render: O(n); Part 2 skip-level pairs: O(n). Part 3 target chain render: O(h + s). Lowest common manager: O(h). Space: O(n). Preparation Write the parser + tree builder + indented printer end-to-end once on paper. The printer is where most loops lose time; pre-decide whether to emit indentation with "" + "....".repeat(depth) or by tracking depth in a recursive helper. Drill the two LCA variants: ancestor-set intersection (simpler, more memory) and parent-pointer two-pointer walk (cleaner, no extra structures). Pick one ahead of the round and stick with it. Practice keeping the data structure flat — a hashmap of strings to a list of strings is enough for most parts. Resist the OOP urge until part 4 explicitly demands node identity (or the interviewer stacks enough follow-ups to justify one OrgChart object built once). Time-box: 5 minutes clarification, 10 minutes parts 1+2, 15 minutes parts 3+4, 15 minutes part 5 / cleanup / tests. If part 1 takes 15+ minutes, the round is in trouble — the parser is supposed to be the easy warm-up.