How should I practice Lowest Common Ancestor in a General Tree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Scale AI onsite interview problems in FastPrep.

Is Lowest Common Ancestor in a General Tree associated with Scale AI?

FastPrep tags this as a Scale AI onsite interview coding practice problem when the problem catalog has that company and stage context.

Lowest Common Ancestor in a General Tree

Scale AI● MediumFULLTIMEONSITE INTERVIEW

Learn

Problem statement

You are given a rooted general tree whose nodes are labeled from 0 through n - 1.

The array children represents the tree: children[i] contains every direct child of node i. Given two node labels p and q, return their lowest common ancestor.

The lowest common ancestor is the deepest node that is an ancestor of both targets. A node is an ancestor of itself.

Function

lowestCommonAncestor(children: int[][], p: int, q: int) → int

Examples

Example 1

children = [[1,2,3],[4,5],[],[6],[],[],[]]p = 4q = 5return = 1

Nodes 4 and 5 are both direct children of node 1, so their lowest common ancestor is 1.

Example 2

children = [[1,2,3],[4,5],[],[6],[],[],[]]p = 4q = 6return = 0

Node 4 lies below child 1, while node 6 lies below child 3. Their paths first meet at the root, node 0.

Example 3

children = [[1,2,3],[4,5],[],[6],[],[],[]]p = 3q = 6return = 3

Node 3 is an ancestor of node 6 and of itself, so it is the lowest common ancestor.

Constraints

1 <= n = children.length <= 100000.
The node labels are exactly 0, 1, ..., n - 1, and node 0 is the root.
Every node other than 0 appears exactly once across all child lists, every listed label is valid, and all nodes are reachable from the root.
0 <= p, q < n. The targets may be equal.