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 interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Design LCA with flexible inputs and rule states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
You are given an organizational tree where every employee reports to exactly one manager. The tree is represented as a `parent` map: each key is an employee id and its value is that employee's direct manager. The single root (top of the org) either maps to `None` or is absent from the map (its manager is undefined).
Given two employees `a` and `b`, return their **lowest common manager** — the deepest node that is an ancestor (manager, manager-of-manager, ...) of both `a` and `b`. Each node is considered an ancestor of itself.
**Special rule:** if one of the two input nodes is an ancestor of the other (for example `b` reports up through `a`), do **not** return that ancestor itself — return the ancestor's *manager* (its parent). When `a == b`, return that node's manager.
**Edge cases to handle:**
- If `a` and `b` belong to different trees (no shared ancestor), return `None`.
- If the lowest common manager would be the root and the special rule applies (so you'd need the root's manager, which is undefined), return `None`.
- Missing nodes (an id not present as a key) are treated as having an undefined manager (`None`).
Implement this with the bottom-up parent-pointer approach: collect the ancestor chain of `a` (including `a`), then walk up from `b` until you hit a node in that chain.
Constraints
- 1 <= number of employees <= 10^5
- The structure is a forest of rooted trees (each node has at most one manager); no cycles.
- A node may be its own input twice (a == b).
- An input id may be missing from the parent map, in which case its manager is undefined (None).
- Employee ids are unique strings.
Examples
Input: ({'a': 'r', 'c': 'r', 'd': 'a', 'e': 'a', 'f': 'c'}, 'd', 'e')
Expected Output: 'a'
Explanation: d and e are siblings reporting to a. The lowest common manager is a, and neither input is an ancestor of the other, so return a.
Input: ({'a': 'r', 'c': 'r', 'd': 'a', 'e': 'a', 'f': 'c'}, 'd', 'f')
Expected Output: 'r'
Explanation: d's chain is d->a->r and f's chain is f->c->r; the first shared ancestor is the root r.
Hints
- Use the parent-pointer (bottom-up) model: you can walk from any node up to the root by repeatedly following its manager.
- Collect every ancestor of a (including a itself) into a set, then walk up from b; the first node you find that is already in a's set is the lowest common ancestor.
- After finding the LCA, check the special rule separately: if the LCA equals a or b, one node is an ancestor of the other, so return that node's manager instead of the node itself.
- Returning None covers both 'different trees' (no shared ancestor) and 'the manager would be the root's undefined parent'.