How should I practice Lowest Common Ancestor with Parent Pointers?

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

Is Lowest Common Ancestor with Parent Pointers associated with Adobe?

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

Problem · Tree

Lowest Common Ancestor with Parent Pointers

Learn this problem

● Easy

AdobeFULLTIMEONSITE INTERVIEW

Problem statement

A rooted tree is represented by an integer array parent, where parent[i] is the parent index of node i and the root has parent -1. Given two node indices first and second, return their lowest common ancestor.

The input is a valid rooted tree, and both node indices are valid. Use O(1) auxiliary space: determine both depths by following parent links, lift the deeper node until the depths match, and then move both nodes upward until they meet.

Function

lowestCommonAncestorWithParents(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 both direct children of node 1.

Example 2

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

The two nodes lie in different root subtrees, so their lowest common ancestor is node 0.

Constraints

1 <= parent.length <= 100000.
parent describes one valid rooted tree: exactly 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.