Quick 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.

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

A rooted tree has `n` nodes labeled `0` to `n - 1`, and a node can have any number of children. Given two nodes `p` and `q`, return their lowest common ancestor: the deepest node that has both `p` and `q` in its subtree. A node counts as its own ancestor, so if `p` lies in the subtree of `q`, the answer is `q`. The report describes this round as a variant of a known ancestor task in which every node carries a link to its parent and only the two nodes are handed over, with the binary tree replaced by a tree whose nodes can have any number of children. Here the parent links are given as an array. ### Function Signature ```python def lowest_common_ancestor(parent: list[int], p: int, q: int) -> int: ``` ### Rules - `parent[i]` is the label of the parent of node `i`, or `-1` if node `i` is the root. - Exactly one entry of `parent` is `-1`, and following parent links from any node reaches the root, so the array describes a single tree with no cycles. - `p` and `q` may be equal. - Return the label of the lowest common ancestor of `p` and `q`. ### Constraints - `1 <= n == len(parent) <= 10^5` - `-1 <= parent[i] <= n - 1` and `parent[i] != i` - `0 <= p, q <= n - 1` - The tree can be a single path, so its height can be as large as `n - 1`. ### Examples All three examples use this tree: ```text parent = [-1, 0, 0, 0, 1, 1, 3, 6] 0 / | \ 1 2 3 / \ \ 4 5 6 | 7 ``` **Example 1** ```text Input: parent = [-1, 0, 0, 0, 1, 1, 3, 6], p = 4, q = 5 Output: 1 ``` Nodes 4 and 5 are both children of node 1. **Example 2** ```text Input: parent = [-1, 0, 0, 0, 1, 1, 3, 6], p = 4, q = 7 Output: 0 ``` The ancestors of 4 are 4, 1 and 0; the ancestors of 7 are 7, 6, 3 and 0. The deepest node on both lists is 0. **Example 3** ```text Input: parent = [-1, 0, 0, 0, 1, 1, 3, 6], p = 3, q = 7 Output: 3 ``` Node 7 lies in the subtree of node 3, and node 3 is its own ancestor.

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.

A rooted tree has `n` nodes labeled `0` to `n - 1`, and a node can have any number of children. The tree is given as an array `parent` of parent links: `parent[i]` is the label of the parent of node `i`, or `-1` if node `i` is the root. Exactly one entry of `parent` is `-1`, and following parent links from any node reaches the root, so the array describes a single tree with no cycles. Given two nodes `p` and `q`, return the label of their **lowest common ancestor**: the deepest node that has both `p` and `q` in its subtree. A node counts as its own ancestor, so if `p` lies in the subtree of `q`, the answer is `q` (and if `q` lies in the subtree of `p`, the answer is `p`). `p` and `q` may be equal. Because the tree has one root and no cycles, the answer is always exactly one node. Implement `lowest_common_ancestor(parent, p, q)`, which returns that node's label as an integer. ### 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. - `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 (each label, `-1` and the answer) fits in a 32-bit signed integer; none can exceed 2^31 - 1. ### Example 1 ```text parent = [-1, 0, 0, 0, 1, 1, 3, 6] 0 / | \ 1 2 3 / \ \ 4 5 6 | 7 ``` ```text Input: parent = [-1, 0, 0, 0, 1, 1, 3, 6], p = 4, q = 5 Output: 1 ``` Nodes 4 and 5 are both children of node 1. ### Example 2 ```text Input: parent = [-1, 0, 0, 0, 1, 1, 3, 6], p = 4, q = 7 Output: 0 ``` The ancestors of 4 are 4, 1 and 0; the ancestors of 7 are 7, 6, 3 and 0. The deepest node on both lists is 0.

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

  1. A node counts as its own ancestor, so the answer can be p or q itself, including when p equals q.
  2. The ancestors of a node are the nodes you reach by following parent links up to the root; Example 2 compares two such lists.
  3. The tree can be a single path of height n - 1 (up to 10^5), so plan for very deep chains.

Lowest Common Ancestor in a Parent-Array Tree

mediumGoogleSoftware Engineer

A rooted tree has n nodes labeled 0 to n - 1, and a node can have any number of children. The tree is given as an array parent of parent links: parent[i] is the label of the parent of node i, or -1 if node i is the root. Exactly one entry of parent is -1, and following parent links from any node reaches the root, so the array describes a single tree with no cycles.

Given two nodes p and q, return the label of their lowest common ancestor: the deepest node that has both p and q in its subtree. A node counts as its own ancestor, so if p lies in the subtree of q, the answer is q (and if q lies in the subtree of p, the answer is p). p and q may be equal. Because the tree has one root and no cycles, the answer is always exactly one node.

Implement lowest_common_ancestor(parent, p, q), which returns that node's label as an integer.

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.
  • 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 (each label, -1 and the answer) fits in a 32-bit signed integer; none can exceed 2^31 - 1.

Example 1

parent = [-1, 0, 0, 0, 1, 1, 3, 6]

          0
        / | \
       1  2  3
      / \     \
     4   5     6
               |
               7
Input:  parent = [-1, 0, 0, 0, 1, 1, 3, 6], p = 4, q = 5
Output: 1

Nodes 4 and 5 are both children of node 1.

Example 2

Input:  parent = [-1, 0, 0, 0, 1, 1, 3, 6], p = 4, q = 7
Output: 0

The ancestors of 4 are 4, 1 and 0; the ancestors of 7 are 7, 6, 3 and 0. The deepest node on both lists is 0.

Examples

Example 1
Input
([-1, 0, 0, 0, 1, 1, 3, 6], 4, 5)
Output
1
Notes
Source Example 1: nodes 4 and 5 are both children of node 1.
Example 2
Input
([-1, 0, 0, 0, 1, 1, 3, 6], 4, 7)
Output
0
Notes
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.

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

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def lowest_common_ancestor(parent: list[int], p: int, q: int) -> int:
Sample call
lowest_common_ancestor([-1, 0, 0, 0, 1, 1, 3, 6], 4, 5)
Language
Case 1
Input
([-1, 0, 0, 0, 1, 1, 3, 6], 4, 5)
Expected
1
Case 2
Input
([-1, 0, 0, 0, 1, 1, 3, 6], 4, 7)
Expected
0

Browse More Questions

Show the approach

Approach

Mark the ancestors of p, then walk up from q. Starting at p, follow parent links until reaching -1 and mark every node visited, including p itself and the root; the marked set is exactly the ancestors of p (a node counts as its own ancestor). Then start at q and follow parent links, stopping at the first marked node. Walking up from q visits q's ancestors from deepest to shallowest, so the first one that is also an ancestor of p is the deepest node with both p and q in its subtree, which is the lowest common ancestor by definition. The second walk always stops before -1 because the root is an ancestor of every node and is marked. Edge cases: if p == q, or q is an ancestor of p, q itself is marked and is returned immediately; if p is an ancestor of q, the walk from q stops at p; a single-node tree returns 0; the root may sit at any index. Both walks are loops rather than recursion, so a single path of height n - 1 (up to 10^5) needs no deep call stack. Each walk visits at most n nodes and the marker array holds n flags.

Time complexity:
O(n)
Space complexity:
O(n)