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 Technical Screen rounds at Bytedance.

What role is this question designed for?

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

Find LCA With Parent Pointers | Bytedance Coding Question

Find LCA With Parent Pointers

Company: Bytedance

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given two nodes in a rooted tree, find their lowest common ancestor. Each node has a pointer to its parent. You are not given the root of the tree. Define the lowest common ancestor as the deepest node that is an ancestor of both input nodes. A node may be considered an ancestor of itself. Implement: ```text Node lowestCommonAncestor(Node a, Node b) ``` Requirements: - Return the lowest common ancestor of `a` and `b`. - Use `O(1)` extra space. - Aim for `O(h)` time, where `h` is the height of the tree. - You may assume both nodes belong to the same tree.

Quick Answer: This question evaluates understanding of tree data structures and ancestor relationships, focusing on lowest common ancestor reasoning with parent pointers and attention to time and space complexity constraints.

You are given two nodes in the same rooted tree and need to find their lowest common ancestor (LCA). Each node only knows its parent; you are not given the root directly. A node may be considered an ancestor of itself. For this coding version, the tree is represented by an array parents where parents[i] is the parent of node i, and -1 marks the root. This models a tree where every node has a parent pointer. Return the index of the lowest common ancestor of nodes a and b. Your solution should use O(1) extra space and aim for O(h) time, where h is the height of the tree.

Constraints

1 <= len(parents) <= 200000
parents[i] is either -1 or an integer in the range [0, len(parents) - 1]
There is exactly one root, and its parent is -1
0 <= a, b < len(parents)
Both nodes belong to the same tree

Examples

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

Expected Output: 1

Explanation: Node 3 goes 3 -> 1 -> 0 and node 4 goes 4 -> 1 -> 0, so their lowest common ancestor is 1.

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

Expected Output: 1

Explanation: Node 1 is an ancestor of node 5, and a node is considered an ancestor of itself.

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

Expected Output: 1

Explanation: Node 6 goes 6 -> 5 -> 3 -> 1 -> 0 and node 4 goes 4 -> 1 -> 0, so the deepest shared ancestor is 1.

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

Expected Output: 0

Explanation: Node 5 is in the subtree of 2 and node 4 is in the subtree of 1, so they first meet at the root 0.

Input: ([-1,0,0,1], 3, 3)

Expected Output: 3

Explanation: Both inputs are the same node, so that node is its own lowest common ancestor.

Input: ([-1], 0, 0)

Expected Output: 0

Explanation: In a single-node tree, the only node is the LCA of itself.

Hints

Think of the path from each node up to the root as a singly linked list. The LCA is where those two lists first intersect.
There is an O(1) space linked-list intersection trick: when one pointer reaches the end, restart it from the other node.

Quick Overview

This question evaluates understanding of tree data structures and ancestor relationships, focusing on lowest common ancestor reasoning with parent pointers and attention to time and space complexity constraints.