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 Salesforce onsite interview problems in FastPrep.

Is Lowest Common Ancestor with Parent Pointers associated with Salesforce?

FastPrep tags this as a Salesforce 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

● Medium

SalesforceFULLTIMEONSITE INTERVIEW

See Salesforce hiring insights

Problem statement

You are given a forest of nodes numbered from 0 through n - 1. For each node i, parents[i] is its parent index, or -1 when i is a root.

Return the lowest common ancestor of nodes first and second. A node is considered an ancestor of itself. If the two nodes belong to different trees, return -1.

Use O(1) auxiliary space. The forest is supplied directly through parent links; no root reference is provided.

Function

lowestCommonAncestor(parents: int[], first: int, second: int) → int

Examples

Example 1

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

Nodes 3 and 4 share node 1 as their nearest ancestor.

Example 2

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

Node 1 belongs to the tree rooted at 0, while node 4 belongs to the tree rooted at 2.

Constraints

1 <= parents.length <= 100000.
Every parent is -1 or a valid node index.
The parent links contain no cycle.
first and second are valid node indices.