How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Find cheapest common ancestor in a tree

Quick Overview

This question evaluates understanding of tree data structures and ancestor concepts (such as lowest common ancestor) along with algorithmic skills for aggregating node attributes like minimum values, situating it in the Coding & Algorithms domain and testing practical application backed by conceptual understanding of ancestor relationships.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Coding You are given a rooted tree where each node has: - an integer `price` - a pointer to its `parent` (root has `parent = null`) - a list of `children` Given two **distinct** nodes `a` and `b` from the same tree, find the **common ancestor** of `a` and `b` (including a node as an ancestor of itself) that has the **minimum price**. ### Output Return the node (or its identifier) that is the cheapest among all common ancestors. ### Notes / edge cases - If `a == b`, then `a` is a common ancestor. - If multiple common ancestors have the same minimum price, you may return any one of them (or specify a tie-breaker such as returning the deepest among them). ### Constraints (assume typical interview constraints) - Up to ~10^5 nodes. - Tree may be unbalanced. - Prices can be any integers. ### What to discuss - A brute-force approach and its time complexity. - An optimal approach for a single query. - Test cases and edge cases.

Quick Answer: This question evaluates understanding of tree data structures and ancestor concepts (such as lowest common ancestor) along with algorithmic skills for aggregating node attributes like minimum values, situating it in the Coding & Algorithms domain and testing practical application backed by conceptual understanding of ancestor relationships.

You are given a rooted tree with nodes labeled from 0 to n - 1. The tree is represented by a parent array, where parent[i] is the parent of node i and the root has parent[i] = -1. Each node also has an integer price given by prices[i]. For two nodes a and b, return the identifier of the common ancestor of both nodes that has the minimum price. A node is considered an ancestor of itself. If multiple common ancestors have the same minimum price, return the deepest one (the one farthest from the root). A brute-force approach may compare ancestor chains directly, but you should aim for an O(h) solution for a single query, where h is the tree height.

Constraints

1 <= n == len(parent) == len(prices) <= 10^5
The input forms a valid rooted tree with exactly one root
-10^9 <= prices[i] <= 10^9
0 <= a, b < n
a and b belong to the same tree and may be equal

Examples

Input: ([-1, 0, 0, 1, 1, 2, 2], [10, 5, 8, 7, 2, 6, 1], 3, 4)

Expected Output: 1

Explanation: The common ancestors of nodes 3 and 4 are 1 and 0. Their prices are 5 and 10, so node 1 is the cheapest.

Input: ([-1, 0, 0, 1, 1, 2, 2], [10, 5, 8, 7, 2, 6, 1], 5, 6)

Expected Output: 2

Explanation: The common ancestors of nodes 5 and 6 are 2 and 0. Their prices are 8 and 10, so node 2 is the cheapest.

Input: ([-1, 0, 1, 1], [4, -3, 10, -3], 2, 2)

Expected Output: 1

Explanation: Since a and b are the same node, the common ancestors are 2, 1, and 0. Their prices are 10, -3, and 4, so node 1 is the cheapest.

Input: ([-1, 0, 1, 2], [5, 1, 1, 7], 3, 2)

Expected Output: 2

Explanation: The common ancestors are 2, 1, and 0. Nodes 2 and 1 both have price 1, so the tie is broken by choosing the deeper node, which is 2.

Input: ([-1, 0, 1, 2, 3], [0, 9, -5, 4, -5], 4, 1)

Expected Output: 0

Explanation: The common ancestors of 4 and 1 are 1 and 0. Their prices are 9 and 0, so node 0 is the cheapest.

Hints

A node can only be a common ancestor if it lies on both paths from a and b up to the root.
First find the lowest common ancestor by equalizing depths using parent pointers. Then only the ancestors of that node need to be checked for the minimum price.

Quick Overview