How should I practice First Common Ancestor with Parent Pointers?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Meta phone screen problems in FastPrep.

Is First Common Ancestor with Parent Pointers associated with Meta?

FastPrep tags this as a Meta phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Tree

First Common Ancestor with Parent Pointers

Learn this problem

● Easy

MetaNEW GRADPHONE SCREEN

See Meta hiring insights

Problem statement

A rooted tree is represented by an integer array parent. Nodes are numbered from 0 through parent.length - 1; parent[i] is the parent of node i, and the single root has parent -1. Child pointers are implied by the same tree.

Given node indices first and second, return their first common ancestor when walking upward from the two nodes. A node is considered an ancestor of itself, so if one selected node is an ancestor of the other, return that selected node. The two selected nodes may be equal.

Use O(1) auxiliary space. You may determine each depth by following parent links, lift the deeper node until both depths match, and then move both nodes upward until they meet.

Function

firstCommonAncestor(parent: int[], first: int, second: int) → int

Examples

Example 1

parent = [-1,0,0,1,1,2,2]first = 3second = 4return = 1

Nodes 3 and 4 are siblings whose nearest common ancestor is node 1.

Example 2

parent = [-1,0,0,1,1,2,2]first = 1second = 4return = 1

Node 1 is an ancestor of node 4 and counts as its own ancestor.

Example 3

parent = [-1,0,0,1,1,2,2]first = 3second = 6return = 0

The nodes lie in different child subtrees of the root, so their first common ancestor is node 0.

Constraints

1 <= parent.length <= 100000.
parent describes exactly one valid rooted tree: one entry is -1, and following parent links from every other node reaches that root.
0 <= first, second < parent.length.
The algorithm must use O(1) auxiliary space.