Answer ancestor-walk queries on a rooted tree
Company: Others
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Take-home Project
## Problem (Tree / Parent Array Queries)
You are given a rooted tree with **n** nodes labeled **1..n**, represented by a **parent array** `par[1..n]`:
- `par[i]` is the parent of node `i`
- `par[root] = -1`
- The input guarantees this forms a valid rooted tree (exactly one root, no cycles).
Example:
- `par = [-1, 1, 1, 2, 2, 2, 2]` (meaning `par[1] = -1`, `par[2] = 1`, …)
You will be given **q** queries. Each query provides:
- a starting node `u`
- an integer `k ≥ 0` (“number of commands/steps”)
For each query, start at node `u` and **move to the parent** exactly `k` times (or until you reach the root). If you reach the root before using all steps, you remain at the root.
### Output
For each query, output the label of the final node where you stop.
### Constraints (assume large input)
Design an approach efficient for large `n, q` (e.g., up to 2e5).
Quick Answer: This question evaluates understanding of tree data structures and ancestor-walk queries, assessing competency in traversing rooted trees, interpreting parent arrays, and designing efficient query-processing methods for large n and q.
For each [u,k], move to the parent k times or stay at the root once reached.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([-1,1,1,2,2,2,2], [[7,2],[4,10],[3,0]])
Expected Output: [1, 1, 3]
Explanation: Ancestor walk queries stay at root if k is too large.
Input: ([-1], [[1,5]])
Expected Output: [1]
Explanation: Single root remains root.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.