Practice/Spotify/Lowest Common Parent in Org Chart

Lowest Common Parent in Org Chart

CodingMust

Problem

You are given an organization chart represented as a tree structure where each node is an employee and edges represent reporting relationships. Write an algorithm to find the lowest common manager (LCM) for a given list of employees.

The lowest common manager is defined as the deepest node in the organization hierarchy that is an ancestor (or manager, directly or indirectly) of all the given employees. An employee can be an ancestor of themselves.

The organization chart is represented as a dictionary/object where each key is an employee name and the value is a list of their direct reports. You are also given the name of the CEO (root of the tree) and a list of employee names for which you need to find the LCM.

Requirements

1. Build a solution that works with an organization hierarchy represented as an adjacency list
2. Handle cases where employees are at different levels in the organization
3. Support finding the LCM for any number of employees (including just one)
4. The solution should work for any valid tree structure (no cycles)
5. Return the name of the employee who is the lowest common manager

Constraints

• 1 ≤ number of employees in organization ≤ 10,000
• 1 ≤ number of employees to find LCM for ≤ 1,000
• All employee names are unique strings
• The organization chart forms a valid tree (single root, no cycles)
• All employees in the query list exist in the organization chart
• Time complexity target: O(N) where N is the number of employees
• Space complexity target: O(N) for auxiliary data structures

Examples

Example 1:

` Organization Chart: CEO /
VP_Eng VP_Sales / \ | Alice Bob Charlie

Input: employees = ["Alice", "Bob"] Output: "VP_Eng" Explanation: Both Alice and Bob directly report to VP_Eng, making VP_Eng their lowest common manager. `

Example 2:

` Organization Chart: CEO | VP_Eng | Director /
Alice Bob

Input: employees = ["CEO", "Alice"] Output: "CEO" Explanation: CEO is an ancestor of Alice, and we need the lowest node that is an ancestor of both, which is CEO itself. `

Example 3:

` Organization Chart: CEO /
VP_Eng VP_Sales / \ | Alice Bob Charlie

Input: employees = ["Alice", "Bob", "Charlie"] Output: "CEO" Explanation: Alice and Bob are under VP_Eng, while Charlie is under VP_Sales. The lowest common ancestor for all three is CEO. `