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.

What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Atlassian.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Atlassian during technical interviews.

Find LCA in a tree and extend to a DAG | Atlassian Interview Question

Q: Find LCA in a tree and extend to a DAG

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.

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.

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.

Find LCA in a tree and extend to a DAG

Quick Overview

Part A — LCA variant in a rooted tree

Part B — Follow-up: generalize to a DAG

Constraints (reasonable interview constraints)

Submit Your Answer to Earn 20XP

Find LCA in a tree and extend to a DAG

Quick Overview

Part A — LCA variant in a rooted tree

Part B — Follow-up: generalize to a DAG

Constraints (reasonable interview constraints)

Submit Your Answer to Earn 20XP