Katkat
Back

Find the nearest common manager of K employees in a reporting tree

GoogleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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

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

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

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

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.