Find nearest common manager for multiple employees
Company: Atlassian
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an organizational hierarchy modeled as a rooted tree, build the tree from (employee, manager) pairs and implement a function that, for k ≥ 2 employees, returns their nearest common organization node (i.e., the lowest common ancestor for multiple nodes). Specify and implement APIs to construct the tree, validate input (detect cycles/disconnected components), and compute LCA for a set of nodes efficiently. Discuss and implement approaches for preprocessing (e.g., parent pointers with depths, binary lifting, or Euler tour + RMQ) and analyze time/space complexity. Include clear unit tests for typical and edge cases (employees in different subtrees, missing employees, and the root case).
Quick Answer: This question evaluates proficiency in tree and graph algorithms (lowest common ancestor), input validation for hierarchical data (cycle and disconnected component detection), API design for constructing and querying trees, and algorithmic time/space complexity analysis.
An organization is modeled as a rooted tree. You are given:
- `edges`: a list of `[employee, manager]` pairs. Each pair means `employee` reports directly to `manager`.
- `root`: the id of the top node (the CEO), who has no manager.
- `queries`: a list of `k >= 2` employee ids.
Implement `solution(edges, root, queries)` that returns the id of the **nearest common manager** of all employees in `queries` — i.e. the lowest common ancestor (LCA) of the query nodes in the tree. A node is considered an ancestor of itself, so if one query node is an ancestor of another, that ancestor is the answer.
The input is guaranteed to form a valid rooted tree (no cycles, single connected component with `root` as the unique root). Compute the LCA efficiently by precomputing depths and folding pairwise LCA across the query set.
Example: tree where 2 and 3 report to 1; 4 and 5 report to 2; 6 and 7 report to 3. For `queries = [4, 5]` the answer is `2`. For `queries = [4, 6]` the answer is `1` (the root). For `queries = [4, 2]` the answer is `2`, since 2 is the manager of 4 (a node is its own ancestor).
Constraints
- 2 <= number of query nodes (k)
- All query node ids exist in the tree (or equal the root)
- Input forms a valid rooted tree: no cycles, single connected component, `root` has no manager
- Node ids are integers and unique
Examples
Input: ([[2, 1], [3, 1], [4, 2], [5, 2], [6, 3], [7, 3]], 1, [4, 5])
Expected Output: 2
Explanation: 4 and 5 both report to 2, so 2 is their nearest common manager.
Input: ([[2, 1], [3, 1], [4, 2], [5, 2], [6, 3], [7, 3]], 1, [4, 6])
Expected Output: 1
Explanation: 4 is under 2, 6 is under 3; their lowest common ancestor is the root, 1.
Hints
- A node is its own ancestor: if query = [4, 2] and 2 is the manager of 4, the answer is 2.
- The LCA of a set of nodes equals folding the pairwise LCA: lca(a, b, c) = lca(lca(a, b), c). Pairwise order does not matter.
- To find the LCA of two nodes, first bring the deeper one up until both depths match, then walk both upward together until they meet.
- Precompute each node's depth once by walking toward the root and memoizing. For very deep trees, binary lifting gives O(log N) per query.