cswork / libraryOpen practice workspace

Coding questions · Amazon

Lowest Common Manager of a Group of Employees in an Org Chart

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.

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

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:

ava
    ben
        dan
            gus
            hal
        eli
    cara
        fay

Example 1

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

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

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.

Lowest Common Manager of a Group of Employees

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:

ava
    ben
        dan
            gus
            hal
        eli
    cara
        fay

Example 1

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

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.

Hints

  1. Consider every person whose team contains all the listed employees. How are those people arranged relative to one another in the chart?
  2. 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.
  3. The answer can be the CEO or one of the listed employees themselves.

Approach

Give every person an integer id (the CEO gets 0) and link each report to its manager. A breadth-first traversal from the CEO with an explicit queue (no recursion, because the chart can be a chain of 10^5 people) lists everyone in non-decreasing distance from the CEO. Mark each distinct listed employee with 1, so repeats count once, and let k be the number of distinct listed employees. Walking that order backwards and adding each person's count into their manager's leaves count[v] equal to the number of distinct listed employees in v's team, so v's team contains every listed employee exactly when count[v] == k. The qualifying people form the path from the CEO down to the answer: if v qualifies so does v's manager, and two people at the same distance have disjoint teams, so at most one person per level qualifies (k >= 1). The last qualifying person in breadth-first order is therefore the one farthest from the CEO, which is the answer. Edge cases: n = 1 (empty reports) returns the CEO; a single distinct employee returns that employee; when a listed employee manages all the others, its count already equals k and no one below it qualifies, so it is returned; pairs given in any order work because ids are assigned in a first pass before the tree is linked. With m = len(employees), the work is O(n + m) hash operations on names of at most 20 characters, and the arrays use O(n) memory.

  • Time complexity: O(n + m)
  • Space complexity: O(n)