Lowest Common Ancestor in an N-ary Tree Using Only Parent Links
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Overview: Google new-grad onsite coding problem: in a rooted tree whose nodes can have any number of children and know only their parent, find the lowest common ancestor of two given nodes. Tests reasoning about parent links and depth on trees that can be as tall as a single long path.
Constraints
- 1 <= n == len(parent) <= 10^5
- -1 <= parent[i] <= n - 1 and parent[i] != i
- Exactly one entry of parent is -1, and following parent links from any node reaches the root (a single tree with no cycles)
- 0 <= p, q <= n - 1, and p may equal q
- The tree can be a single path, so its height can be as large as n - 1
- Every value fits in a 32-bit signed integer
Examples
Input: ([-1, 0, 0, 0, 1, 1, 3, 6], 4, 5)
Expected Output: 1
Explanation: Source Example 1: nodes 4 and 5 are both children of node 1.
Input: ([-1, 0, 0, 0, 1, 1, 3, 6], 4, 7)
Expected Output: 0
Explanation: Source Example 2: the ancestors of 4 are 4, 1, 0 and of 7 are 7, 6, 3, 0; the deepest shared node is the root 0.
Hints
- A node counts as its own ancestor, so the answer can be p or q itself, including when p equals q.
- The ancestors of a node are the nodes you reach by following parent links up to the root; Example 2 compares two such lists.
- The tree can be a single path of height n - 1 (up to 10^5), so plan for very deep chains.