How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Design LCA with flexible inputs and rule

Quick Overview

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.

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.

Input: ({'a': 'r', 'c': 'r', 'd': 'a', 'e': 'a', 'f': 'c'}, 'a', 'd')

Expected Output: 'r'

Explanation: a is an ancestor of d (d reports to a). The special rule applies, so instead of returning a we return a's manager, r.

Input: ({'a': 'r', 'c': 'r', 'd': 'a', 'e': 'a', 'f': 'c'}, 'r', 'd')

Expected Output: None

Explanation: r is the root and an ancestor of d. The special rule asks for r's manager, which is undefined, so return None.

Input: ({'a': 'r', 'c': 'r', 'd': 'a', 'e': 'a', 'f': 'c'}, 'd', 'd')

Expected Output: 'a'

Explanation: Both inputs are d. d is trivially an ancestor of itself, so the rule returns d's manager, a.

Input: ({'a': 'r', 'x': 'y'}, 'a', 'x')

Expected Output: None

Explanation: a's chain is a->r and x's chain is x->y; the two nodes live in different trees with no shared ancestor, so return None.

Input: ({'b': 'a', 'c': 'b'}, 'a', 'c')

Expected Output: None

Explanation: a is not a key (root, manager undefined). c reports up c->b->a, so a is an ancestor of c. The rule asks for a's manager, which is undefined, so return None.

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'.

Quick Overview