Find LCA in a tree and extend to a DAG
Company: Atlassian
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Part A — LCA variant in a rooted tree
You are given a rooted tree with `n` nodes labeled `0..n-1`.
Input:
- `parent[i]` for each node `i` (`parent[root] = -1`).
- Two nodes `u` and `v`.
Task:
- Return the **lowest common ancestor (LCA)** of `u` and `v`.
Clarifications:
- The LCA is the common ancestor with the greatest depth.
- The input always forms a valid tree.
Follow-up (variant):
- Answer **multiple queries** `q` (up to ~1e5) for different pairs `(u, v)` efficiently.
## Part B — Follow-up: generalize to a DAG
Now the structure is a **directed acyclic graph (DAG)** where edges point from a node to its **parent(s)** (a node may have multiple parents).
Input:
- `parents[i]`: list of parent nodes of `i` (possibly empty).
- Two nodes `u` and `v`.
Task:
- Return the set of **lowest common ancestors** of `u` and `v` in the DAG, defined as:
- Nodes that are ancestors of both `u` and `v`, and
- Do **not** have any descendant (within the common-ancestor set) that is also a common ancestor.
Notes:
- In a DAG, there may be **multiple** lowest common ancestors.
## Constraints (reasonable interview constraints)
- `n` up to ~2e5, edges up to ~5e5.
- DAG is guaranteed acyclic.
- Aim for near-linear preprocessing for many queries when applicable.
Quick Answer: This question evaluates proficiency in graph algorithms and data structures, focusing on lowest common ancestor computation in rooted trees and its generalization to directed acyclic graphs, along with complexity analysis for preprocessing and handling many queries.
LCA in a Rooted Tree
Return the lowest common ancestor of u and v from a parent array.
Examples
Input: ([-1, 0, 0, 1, 1, 2], 3, 4)
Expected Output: 1
Explanation: Same parent.
Input: ([-1, 0, 0, 1, 1, 2], 3, 5)
Expected Output: 0
Explanation: Root LCA.
Input: ([-1], 0, 0)
Expected Output: 0
Explanation: Same node.
Lowest Common Ancestors in a DAG
Return all lowest common ancestors in a DAG whose edges point from node to parent nodes.
Examples
Input: ([[], [], [0, 1], [1], [2, 3]], 4, 2)
Expected Output: [2]
Explanation: Multiple common candidates reduced to lowest.
Input: ([[], [0], [0]], 1, 2)
Expected Output: [0]
Explanation: Root only.
Input: ([[], [0], [0], [1, 2]], 3, 1)
Expected Output: [1]
Explanation: Ancestor can be one target.