Lowest Common Manager of a Group of Employees in an Org Chart
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A company's org chart is a tree. The CEO is at the top, and every other person reports directly to exactly one manager. A person's team is that person together with everyone who reports to them, directly or indirectly.
Given the org chart and a list of employees, return their lowest common manager: the person whose team contains every listed employee and who sits lowest in the chart, that is, farthest from the CEO.
The interview first asked for two employees, then followed up with a list of any number of employees. Solve the general version; the original question is the case of a list of length 2.
### Function Signature
```python
def lowest_common_manager(ceo: str, reports: list[tuple[str, str]], employees: list[str]) -> str:
```
Each pair `(manager, report)` in `reports` means that `report` reports directly to `manager`.
### Rules
- The people in the org chart are `ceo` and every name that appears in `reports`. Each name identifies exactly one person.
- `ceo` never appears as the second element of a pair. Every other person appears as the second element of exactly one pair. Following managers upward from any person always reaches `ceo`, so the org chart is a single tree with no cycles.
- Every name in `employees` is a person in the org chart. A name may appear more than once in `employees`; repeats are treated as a single occurrence.
- The answer is the person whose team contains every name in `employees` and whose distance from `ceo` (the number of reporting links between them) is largest. Exactly one person satisfies this.
- The answer can be one of the listed employees: for example, when one listed employee manages all the others directly or indirectly, or when `employees` contains a single distinct name.
### Constraints
- `1 <= n <= 10^5`, where `n` is the number of people, and `len(reports) == n - 1`.
- `1 <= len(employees) <= 10^5`
- Every name is 1 to 20 characters long and consists of lowercase English letters and digits.
- The org chart can be a single chain of `n` people, so its depth can reach `n - 1`.
### Examples
All three examples use this org chart, with each person indented under their manager:
```text
ava
ben
dan
gus
hal
eli
cara
fay
```
**Example 1**
```text
Input: ceo = "ava",
reports = [("ava", "ben"), ("ava", "cara"), ("ben", "dan"), ("ben", "eli"),
("cara", "fay"), ("dan", "gus"), ("dan", "hal")],
employees = ["gus", "eli"]
Output: "ben"
```
The people whose teams contain both `gus` and `eli` are `ben` and `ava`. `ben` is lower in the chart.
**Example 2**
```text
Input: ceo = "ava",
reports = [("ava", "ben"), ("ava", "cara"), ("ben", "dan"), ("ben", "eli"),
("cara", "fay"), ("dan", "gus"), ("dan", "hal")],
employees = ["gus", "hal", "fay"]
Output: "ava"
```
`gus` and `hal` are both in `dan`'s team, but `fay` belongs only to the teams of `fay`, `cara` and `ava`, so only `ava`'s team contains all three.
**Example 3**
```text
Input: ceo = "ava",
reports = [("ava", "ben"), ("ava", "cara"), ("ben", "dan"), ("ben", "eli"),
("cara", "fay"), ("dan", "gus"), ("dan", "hal")],
employees = ["hal", "dan", "hal"]
Output: "dan"
```
The repeated `hal` counts once. `dan`'s team is `dan`, `gus` and `hal`, so it contains both listed names, and no person lower in the chart has a team that does.
Overview: Given a company org chart as manager and report pairs plus a list of employees, return their lowest common manager, the lowest person whose team includes every listed employee. It tests building a tree from edge pairs, reasoning about ancestors, and generalizing a two-employee query to many employees.
Read the full Amazon Software Engineer interview experience this question came from
A company's org chart is a tree. The CEO is at the top, and every other person reports directly to exactly one manager. A person's team is that person together with everyone who reports to them, directly or indirectly.
Given the org chart and a list of employees, return their lowest common manager: the person whose team contains every listed employee and who sits lowest in the chart, that is, farthest from the CEO. The list can hold any number of employees; the two-employee version of the question is the case of a list of length 2.
Implement `lowest_common_manager(ceo, reports, employees)`:
- `ceo` (string): the CEO's name.
- `reports` (list of pairs): each pair `[manager, report]` means that `report` reports directly to `manager`. The whole list is one argument: a list of two-element string lists (`String[][]` in Java, `std::vector<std::vector<std::string>>` in C++). The pairs come in no particular order.
- `employees` (list of strings): the listed employees.
- Return the lowest common manager's name as a string.
### Rules
- The people in the org chart are `ceo` and every name that appears in `reports`. Each name identifies exactly one person.
- `ceo` never appears as the second element of a pair. Every other person appears as the second element of exactly one pair. Following managers upward from any person always reaches `ceo`, so the org chart is a single tree with no cycles.
- Every name in `employees` is a person in the org chart. A name may appear more than once in `employees`; repeats are treated as a single occurrence.
- The answer is the person whose team contains every name in `employees` and whose distance from `ceo` (the number of reporting links between them) is largest. Exactly one person satisfies this.
- The answer can be one of the listed employees: for example, when one listed employee manages all the others directly or indirectly, or when `employees` contains a single distinct name.
### Constraints
- `1 <= n <= 10^5`, where `n` is the number of people, and `len(reports) == n - 1`.
- `1 <= len(employees) <= 10^5`
- Every name is 1 to 20 characters long and consists of lowercase English letters and digits.
- The org chart can be a single chain of `n` people, so its depth can reach `n - 1`.
- No value exceeds 2^31 - 1: inputs and output are names, and any count or index fits in a 32-bit integer.
### Examples
Both examples use this org chart, with each person indented under their manager:
```text
ava
ben
dan
gus
hal
eli
cara
fay
```
**Example 1**
```text
Input: ceo = "ava",
reports = [["ava", "ben"], ["ava", "cara"], ["ben", "dan"], ["ben", "eli"],
["cara", "fay"], ["dan", "gus"], ["dan", "hal"]],
employees = ["gus", "eli"]
Output: "ben"
```
The people whose teams contain both `gus` and `eli` are `ben` and `ava`. `ben` is lower in the chart.
**Example 2**
```text
Input: ceo = "ava",
reports = [["ava", "ben"], ["ava", "cara"], ["ben", "dan"], ["ben", "eli"],
["cara", "fay"], ["dan", "gus"], ["dan", "hal"]],
employees = ["gus", "hal", "fay"]
Output: "ava"
```
`gus` and `hal` are both in `dan`'s team, but `fay` belongs only to the teams of `fay`, `cara` and `ava`, so only `ava`'s team contains all three.
Constraints
- 1 <= n <= 10^5, where n is the number of people (ceo plus every name in reports), and len(reports) == n - 1.
- 1 <= len(employees) <= 10^5
- Every name is 1 to 20 characters long and consists of lowercase English letters and digits.
- The org chart can be a single chain of n people, so its depth can reach n - 1.
- ceo never appears as the second element of a pair; every other person appears as the second element of exactly one pair; following managers upward from any person always reaches ceo.
- Every name in employees is a person in the org chart; repeated names are treated as a single occurrence.
Examples
Input: ('ava', [['ava', 'ben'], ['ava', 'cara'], ['ben', 'dan'], ['ben', 'eli'], ['cara', 'fay'], ['dan', 'gus'], ['dan', 'hal']], ['gus', 'eli'])
Expected Output: 'ben'
Explanation: Example 1: ben and ava both have gus and eli in their teams; ben is lower.
Input: ('ava', [['ava', 'ben'], ['ava', 'cara'], ['ben', 'dan'], ['ben', 'eli'], ['cara', 'fay'], ['dan', 'gus'], ['dan', 'hal']], ['gus', 'hal', 'fay'])
Expected Output: 'ava'
Explanation: Example 2 (three names): gus and hal meet at dan, but fay is only under cara, so only ava qualifies; catches logic that uses just the first two names.
Hints
- Consider every person whose team contains all the listed employees. How are those people arranged relative to one another in the chart?
- Repeated names do not change the answer, and the chart can be a single chain of 10^5 people, so a recursive walk down the chart may overflow the call stack.
- The answer can be the CEO or one of the listed employees themselves.