Highest Average-Salary Team in an Org Chart
Company: Amazon
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Highest Average-Salary Team in an Org Chart
A company's reporting structure is a single hierarchy. Every employee has a unique integer `id`, a `name`, an integer `salary`, and a `manager_id` — the `id` of the person they report to. Exactly one employee (the CEO) has `manager_id = null`, meaning they have no manager. The reporting relationships form a tree: there are no cycles, and every non-CEO employee's `manager_id` refers to another employee in the list.
For any employee `M`, define **M's team** as the set of all employees who report to `M` directly or indirectly — that is, everyone in the subtree strictly below `M`, **not** counting `M` themselves. An employee is a **manager** if their team is non-empty.
The **average salary of a team** is the sum of the team members' salaries divided by the number of team members.
Among all managers, return the `id` of the manager whose team has the **highest average salary**. If two managers tie on team average, return the one with the smaller `id`. If no employee has any reports (everyone is a leaf), return `-1`.
## Input
- `employees`: a list of records, each with the fields `{id, name, salary, manager_id}`.
- `1 <= number of employees <= 10^5`
- All `id` values are distinct integers.
- `0 <= salary <= 10^6`
- Exactly one employee has `manager_id = null`; every other `manager_id` references an existing employee, and the relationships form a valid tree.
## Output
- The integer `id` of the manager whose team (all direct **and** indirect reports) has the greatest average salary, with ties broken by smaller `id`; or `-1` if there are no managers.
## Example
```
employees = [
{id: 1, name: "Ana", salary: 100, manager_id: null},
{id: 2, name: "Ben", salary: 90, manager_id: 1},
{id: 3, name: "Cara", salary: 60, manager_id: 1},
{id: 4, name: "Dan", salary: 80, manager_id: 2},
{id: 5, name: "Eve", salary: 70, manager_id: 2}
]
```
Teams and their averages:
- Manager `1` (Ana): team = `{2, 3, 4, 5}`, salary sum `90 + 60 + 80 + 70 = 300`, average `= 75.0`.
- Manager `2` (Ben): team = `{4, 5}`, salary sum `80 + 70 = 150`, average `= 75.0`.
- Employees `3`, `4`, `5` have no reports, so they are not managers.
Managers `1` and `2` both have a team average of `75.0`, so the tie is broken by smaller `id`.
```
Output: 1
```
## Notes
- A manager's team includes reports at every depth of the subtree, not only the direct reports.
Quick Answer: This question evaluates a candidate's ability to traverse tree-structured data and perform subtree aggregation, applying recursive or bottom-up DFS techniques to compute per-node statistics. It tests understanding of hierarchical data modeling and comparison logic with tie-breaking, a common theme in coding interviews assessing tree and graph fundamentals at a practical implementation level.
You are given a company's org chart as three parallel arrays of equal length `n`:
- `ids[i]` — the unique integer id of the i-th employee.
- `salaries[i]` — that employee's salary (0 <= salary <= 10^6).
- `manager_ids[i]` — the id of that employee's direct manager, or `-1` if the employee is the CEO (no manager).
The reporting relationships form a single tree: exactly one employee has `manager_id = -1` (the CEO), and every other `manager_id` refers to an existing employee, with no cycles.
For any employee `M`, **M's team** is the set of all employees who report to `M` directly or indirectly — i.e. everyone strictly below `M` in the tree, **not counting M**. An employee is a **manager** if their team is non-empty. A team's **average salary** is the sum of the team members' salaries divided by the number of team members.
Return the id of the manager whose team has the **highest average salary**. Break ties by smaller id. If no employee has any reports (everyone is a leaf), return `-1`.
**Example**
```
ids = [1, 2, 3, 4, 5]
salaries = [100, 90, 60, 80, 70]
manager_ids = [-1, 1, 1, 2, 2]
```
- Manager 1's team = {2,3,4,5}, sum = 300, average = 75.0
- Manager 2's team = {4,5}, sum = 150, average = 75.0
- Employees 3, 4, 5 have no reports.
Managers 1 and 2 tie at 75.0, so the smaller id wins -> **Output: 1**.
Constraints
- 1 <= n <= 10^5 (number of employees)
- ids are distinct integers; salaries satisfy 0 <= salary <= 10^6
- Exactly one manager_id equals -1 (the CEO); all others reference an existing id
- The reporting relationships form a valid tree (no cycles)
Examples
Input: ([1, 2, 3, 4, 5], [100, 90, 60, 80, 70], [-1, 1, 1, 2, 2])
Expected Output: 1
Explanation: Manager 1's team {2,3,4,5} averages 75.0; manager 2's team {4,5} averages 75.0. Tie broken by smaller id -> 1.
Input: ([1], [100], [-1])
Expected Output: -1
Explanation: The only employee is the CEO with no reports, so there are no managers -> -1.
Input: ([1, 2, 3], [10, 100, 200], [-1, 1, 2])
Expected Output: 2
Explanation: A chain 1->2->3. Manager 1's team {2,3} averages 150; manager 2's team {3} averages 200. Deeper manager 2 wins.
Input: ([5, 2, 4, 1, 3], [50, 50, 50, 0, 50], [4, 1, 1, -1, 2])
Expected Output: 1
Explanation: Input is unordered. Managers 1, 2, 4 all have team average 50.0, so the smallest id 1 wins.
Input: ([1, 2], [5, 0], [-1, 1])
Expected Output: 1
Explanation: Manager 1's only report earns 0, team average 0.0; still the sole manager -> 1.
Hints
- A manager's team is the whole subtree strictly below them, not just direct reports. Compute each subtree's total salary and headcount once.
- Do a single post-order traversal: subtree_sum[M] and subtree_cnt[M] include M; the team excludes M, so use (subtree_sum[M] - salary[M]) and (subtree_cnt[M] - 1).
- Use an explicit stack instead of recursion (n can be 10^5). Compare averages with cross-multiplication (a1*c2 vs a2*c1) to avoid floating-point ties, and break exact ties by smaller id.