Katkat
Back

Find smallest common organization for employees

AtlassianSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to navigate hierarchical structures and find the Lowest Common Ancestor (LCA) in a tree or a directed acyclic graph representing organizational reporting lines.

Problem Statement

You are given the organizational structure of a company represented as a list of direct reporting relationships. Each employee has a unique ID, and the hierarchy is guaranteed to be a tree (one root, no cycles). You are tasked with writing a function that finds the ID of the 'Lowest Common Manager' for two given employees. The Lowest Common Manager is defined as the lowest-level employee in the hierarchy who manages (directly or indirectly) both target employees.

Function Signature

def find_lowest_common_manager(reports, emp1, emp2)

  • reports: A dictionary where keys are manager IDs and values are lists of direct report IDs.
  • emp1, emp2: The IDs of the two employees.

Constraints

  • The number of employees N is up to 10^5.
  • The hierarchy is always a single tree.
  • emp1 and emp2 are guaranteed to exist in the organization.

Example 1

Input: reports = {1: [2, 3], 2: [4, 5], 3: [6]}, emp1 = 4, emp2 = 5 Output: 2 Explanation: 2 is the direct manager of both 4 and 5.

Example 2

Input: reports = {1: [2, 3], 2: [4, 5], 3: [6]}, emp1 = 4, emp2 = 6 Output: 1 Explanation: 1 is the lowest manager who is an ancestor of both 4 and 6.

Hints

Hint 1

Consider reversing the graph to map every employee to their direct manager to simplify upward traversal.

Hint 2

For each employee, create a path to the root and compare the paths, or use a hash set to store the ancestors of the first employee.

Hint 3

Can you solve this in O(N) time and O(N) space where N is the total number of employees?

Follow-up questions

  • How would your solution change if the organizational structure was a Directed Acyclic Graph (DAG) rather than a tree (e.g., an employee can have multiple managers)?
  • If you had to perform this query 1 million times for the same organization, how would you optimize the solution to achieve O(1) or O(log N) per query?
  • What are the implications for your algorithm if the organization has an extremely deep hierarchy (e.g., a linked list of 10^5 employees)?