How should I practice Cheapest Common Ancestor?

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

Is Cheapest Common Ancestor associated with Google?

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

Cheapest Common Ancestor

Google● MediumNEW GRADONSITE INTERVIEW

Learn

Problem statement

A parent array describes a forest of rooted trees. Node i has parent parent[i], or -1 when it is a root. Every node also has a non-negative price prices[i].

A node is considered its own ancestor. Given nodes first and second, return their common ancestor with the smallest price. Break a price tie by the smaller node index. Return -1 when the nodes belong to different trees and have no common ancestor.

Function

cheapestCommonAncestor(parent: int[], prices: int[], first: int, second: int) → int

Examples

Example 1

parent = [-1,0,0,1,1,2]prices = [9,5,2,7,4,6]first = 3second = 4return = 1

Nodes 1 and 0 are common ancestors; node 1 is cheaper.

Example 2

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

Node 1 is its own ancestor and is cheaper than root 0.

Example 3

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

The nodes are in different trees.

Constraints

1 <= parent.length = prices.length <= 200000.
parent[i] is -1 or a valid node index.
The parent pointers contain no cycle.
0 <= prices[i] <= 1000000000.
first and second are valid node indices.