Find the nearest common manager of K employees in a reporting tree
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
A company's reporting structure forms a tree. Employees are numbered `0` to `n - 1`. Every employee except one has exactly one direct manager; the remaining employee is at the top of the hierarchy and has no manager.
Given the reporting structure and a list of `k` distinct employees, return their nearest common manager: the employee farthest from the top who appears in the management chain of every listed employee.
### Function Signature
```python
def nearest_common_manager(manager: list[int], employees: list[int]) -> int:
```
### Rules
- `manager[i]` is the direct manager of employee `i`, or `-1` if employee `i` is the top of the hierarchy.
- The chain of employee `e` is `e` itself, then `manager[e]`, then that employee's manager, and so on up to the top employee.
- An employee `x` is a common manager of the list when `x` is in the chain of every listed employee. Because each chain starts with the employee, if one listed employee is above all the others (directly or indirectly), the answer is that listed employee.
- The top employee is in every chain, so a common manager always exists. All common managers lie on one path to the top, so exactly one of them is farthest from the top. Return its number.
### Constraints
- `2 <= n <= 100000`, where `n = len(manager)`
- Exactly one index `i` has `manager[i] == -1`. Every other `manager[i]` is in `[0, n - 1]`, and following managers from any employee reaches the top employee without revisiting anyone.
- `2 <= k <= n`, where `k = len(employees)`
- The values in `employees` are distinct, and each is in `[0, n - 1]`.
- The hierarchy may be a single chain, so an employee can be up to `n - 1` levels below the top.
### Examples
**Example 1**
```text
Input: manager = [-1, 0, 0, 1, 1, 2, 3], employees = [6, 4]
Output: 1
```
Employee 6's chain is 6, 3, 1, 0 and employee 4's chain is 4, 1, 0. Employees 1 and 0 appear in both chains, and 1 is farther from the top.
**Example 2**
```text
Input: manager = [-1, 0, 0, 1, 1, 2, 3], employees = [6, 4, 5]
Output: 0
```
Employee 5's chain is 5, 2, 0, so the only employee in all three chains is the top employee 0.
**Example 3**
```text
Input: manager = [-1, 0, 0, 1, 1, 2, 3], employees = [3, 6]
Output: 3
```
Employee 3 is the direct manager of employee 6, and 3 is the first entry of its own chain, so 3 is the nearest common manager.
Overview: Given a company reporting tree in which every employee except the top one has a single direct manager, find the nearest manager shared by a list of K employees, counting each employee as part of their own chain. Tests tree reasoning, ancestor chains and very deep hierarchies.
A company's reporting structure forms a tree. Employees are numbered `0` to `n - 1`. Every employee except one has exactly one direct manager; the remaining employee is at the top of the hierarchy and has no manager.
You are given the array `manager` and a list `employees` of `k` distinct employee numbers. Return their nearest common manager: the employee farthest from the top who appears in the management chain of every listed employee.
### Rules
- `manager[i]` is the direct manager of employee `i`, or `-1` if employee `i` is the top of the hierarchy. The top employee is not necessarily employee `0`.
- The chain of employee `e` is `e` itself, then `manager[e]`, then that employee's manager, and so on up to the top employee.
- An employee `x` is a common manager of the list when `x` is in the chain of every listed employee. Because each chain starts with the employee itself, if one listed employee is above all the others (directly or indirectly), the answer is that listed employee.
- The top employee is in every chain, so a common manager always exists. All common managers lie on one path to the top, so exactly one of them is farthest from the top. Return its number as an integer.
Every input value and the answer lie in `[-1, 100000]`, so they all fit in a 32-bit signed integer.
### Constraints
- `2 <= n <= 100000`, where `n = len(manager)`
- Exactly one index `i` has `manager[i] == -1`. Every other `manager[i]` is in `[0, n - 1]`, and following managers from any employee reaches the top employee without revisiting anyone.
- `2 <= k <= n`, where `k = len(employees)`
- The values in `employees` are distinct, and each is in `[0, n - 1]`.
- The hierarchy may be a single chain, so an employee can be up to `n - 1` levels below the top.
### Example 1
```text
Input: manager = [-1, 0, 0, 1, 1, 2, 3], employees = [6, 4]
Output: 1
```
Employee 6's chain is 6, 3, 1, 0 and employee 4's chain is 4, 1, 0. Employees 1 and 0 appear in both chains, and 1 is farther from the top.
### Example 2
```text
Input: manager = [-1, 0, 0, 1, 1, 2, 3], employees = [3, 6]
Output: 3
```
Employee 3 is the direct manager of employee 6, and 3 is the first entry of its own chain, so 3 is the nearest common manager.
Constraints
- 2 <= n <= 100000, where n = len(manager)
- Exactly one index i has manager[i] == -1. Every other manager[i] is in [0, n - 1], and following managers from any employee reaches the top employee without revisiting anyone.
- 2 <= k <= n, where k = len(employees)
- The values in employees are distinct, and each is in [0, n - 1].
- The hierarchy may be a single chain, so an employee can be up to n - 1 levels below the top.
Examples
Input: ([-1, 0, 0, 1, 1, 2, 3], [6, 4])
Expected Output: 1
Explanation: Source example: chains 6, 3, 1, 0 and 4, 1, 0 share 1 and 0, and 1 is farther from the top.
Input: ([-1, 0, 0, 1, 1, 2, 3], [3, 6])
Expected Output: 3
Explanation: Source example: 3 directly manages 6 and starts its own chain, so the listed employee 3 is the answer.
Hints
- Every chain ends at the top employee, so the top is always a common manager; the question is how far below the top you can go while staying in every chain.
- An employee x is a common manager exactly when every listed employee is x itself or somewhere below x.
- The hierarchy can be a single chain n - 1 levels deep, so prefer work that does not grow the call stack with the depth.