How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Others.

What role is this question designed for?

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

Answer k-step ancestor queries in a rooted tree

Q: Answer k-step ancestor queries in a rooted tree

This question evaluates proficiency with tree data structures and ancestor-query algorithms, focusing on reasoning about parent arrays, upward traversal, and performance under large n and q constraints.

You are given a rooted tree encoded as a parent array par[1..n] where:

Nodes are labeled 1..n .
par[i] is the parent of node i .
Exactly one node has par[i] = -1 (the root).

You must answer q queries. Each query provides a starting node u and an integer k.

Starting from u, apply the following operation exactly k times (or until you cannot move further):

If the current node has a parent, move to its parent.
If the current node is the root (parent is -1 ), you stay at the root for all remaining steps.

For each query, output the final node label after performing the moves.

Input format

n
array par[1..n]
q
q lines: u k

Output format

For each query, one line with the final node label.

Constraints (typical interview scale)

1 <= n, q <= 2 * 10^5
0 <= k <= 10^9
par[i] = -1 or 1 <= par[i] <= n

Example

If par = [-1, 1, 1, 2, 2, 2, 2] (meaning par[1]=-1, par[2]=1, ...):

Query (u=7, k=2) goes 7 -> 2 -> 1 , output 1 .
Query (u=4, k=10) ends at root 1 , output 1 .

You are given a rooted tree encoded as a parent array par[1..n] where:

Nodes are labeled 1..n .
par[i] is the parent of node i .
Exactly one node has par[i] = -1 (the root).

You must answer q queries. Each query provides a starting node u and an integer k.

Starting from u, apply the following operation exactly k times (or until you cannot move further):

If the current node has a parent, move to its parent.
If the current node is the root (parent is -1 ), you stay at the root for all remaining steps.

For each query, output the final node label after performing the moves.

Input format

n
array par[1..n]
q
q lines: u k

Output format

For each query, one line with the final node label.

Constraints (typical interview scale)

1 <= n, q <= 2 * 10^5
0 <= k <= 10^9
par[i] = -1 or 1 <= par[i] <= n

Example

If par = [-1, 1, 1, 2, 2, 2, 2] (meaning par[1]=-1, par[2]=1, ...):

Query (u=7, k=2) goes 7 -> 2 -> 1 , output 1 .
Query (u=4, k=10) ends at root 1 , output 1 .

Answer k-step ancestor queries in a rooted tree

Quick Overview

Input format

Output format

Constraints (typical interview scale)

Example

Submit Your Answer

Answer k-step ancestor queries in a rooted tree

Quick Overview

Input format

Output format

Constraints (typical interview scale)

Example

Submit Your Answer