Design LCA with flexible inputs and rule
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Design a function to find the lowest common manager of two employees in an organizational tree. Support two input models:
(A) nodes store a list of children and you are given the root plus nodes a and b;
(B) nodes store a parent pointer and you are given only nodes a and b. Provide both a top-down solution from the root and a bottom-up solution using parent pointers. Additional rule: if one node is an ancestor of the other (e.g., b is a descendant of a), return the ancestor’s manager (the parent of that ancestor) rather than the ancestor itself. Specify data structures, algorithms, time/space complexity, and how to handle cases like missing nodes, nodes from different trees, or an undefined manager for the root.
Quick Answer: This question evaluates a candidate's understanding of tree algorithms and lowest common ancestor concepts, including handling both child-list (root-provided) and parent-pointer input models as well as special ancestor-as-manager rules and edge-case handling.
