Find nearest common manager for multiple employees
Company: Atlassian
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Given an organizational hierarchy modeled as a rooted tree, build the tree from (employee, manager) pairs and implement a function that, for k ≥ 2 employees, returns their nearest common organization node (i.e., the lowest common ancestor for multiple nodes). Specify and implement APIs to construct the tree, validate input (detect cycles/disconnected components), and compute LCA for a set of nodes efficiently. Discuss and implement approaches for preprocessing (e.g., parent pointers with depths, binary lifting, or Euler tour + RMQ) and analyze time/space complexity. Include clear unit tests for typical and edge cases (employees in different subtrees, missing employees, and the root case).
Quick Answer: This question evaluates proficiency in tree and graph algorithms (lowest common ancestor), input validation for hierarchical data (cycle and disconnected component detection), API design for constructing and querying trees, and algorithmic time/space complexity analysis.