Design LCA with flexible inputs and rule

Q: Design LCA with flexible inputs and rule

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Design LCA with flexible inputs and rule

Overview

Comments (0)