Kth Employee Reached in an Ordered Hierarchy
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
# Kth Employee Reached in an Ordered Hierarchy
Implement `kth_recipients(boss, queries)`.
Employees are numbered `0` through `n - 1`. `boss[0] == -1`; for every other employee `i`, `boss[i]` is the direct manager of `i`, and the array forms one rooted tree.
When data is sent to `start`, that employee receives it first. They then pass it recursively through their organization in depth-first preorder, visiting each employee's direct reports in ascending employee-number order.
Each query is `(start, k)`, where `k` is one-indexed. Return the employee who is the `k`th recipient within `start`'s subtree, or `-1` if the subtree has fewer than `k` employees.
## Constraints
- `1 <= n <= 200,000`
- `1 <= len(queries) <= 200,000`
- The hierarchy is a valid rooted tree.
- Query starts are valid indices and `k >= 1`.
## Example behavior
If employee `2` directly manages employees `4` and `7`, and `4` manages `5`, transmission from `2` visits `2, 4, 5, 7` before any later sibling subtree.
## Candidate clarifications
Confirm whether the start employee counts as recipient one, whether traversal is depth-first, the sibling ordering, and out-of-range behavior.
Quick Answer: This tree-algorithms interview question evaluates practical understanding of ordered hierarchy traversal and repeated subtree selection queries. It is commonly used to assess traversal semantics, preprocessing judgment, scalability, and careful handling of indexing and out-of-range cases.
Employees at a company are numbered `0` through `n - 1` and organized as one rooted tree. You are given an integer array `boss` of length `n`:
- `boss[0] == -1`, so employee `0` is the root of the hierarchy.
- For every other employee `i`, `boss[i]` is the direct manager of `i`.
When data is handed to an employee, that employee receives it first. They then forward it through their own organization in depth-first preorder, visiting each employee's direct reports in ascending employee-number order. A report's entire subtree is fully visited before the next report of the same manager receives anything.
For example, if employee `2` directly manages employees `4` and `7`, and employee `4` manages employee `5`, then a transmission starting at employee `2` reaches `2, 4, 5, 7` in that order.
You are also given `queries`, where `queries[j] = [start, k]` and `k` is one-indexed. For each query, return the employee who is the `k`th recipient of a transmission that starts at employee `start`. Employee `start` is recipient number `1`. If `start`'s subtree contains fewer than `k` employees, the answer for that query is `-1`.
Implement `kth_recipients(boss, queries)`.
Output format: return a list of integers of length `len(queries)`, where entry `j` is the answer to `queries[j]` and the entries appear in exactly the order the queries were given. Every entry is either an employee number in `[0, n - 1]` or `-1`. The ascending sibling rule fixes a single transmission order, so each query has exactly one correct answer and no tie-breaking is required.
Example 1
Input: `boss = [-1, 0, 0, 1, 1, 2]`, `queries = [[0, 1], [0, 4], [1, 3], [2, 2], [5, 2]]`
Output: `[0, 4, 4, 5, -1]`
Employee `0` manages `1` and `2`; employee `1` manages `3` and `4`; employee `2` manages `5`. A transmission from `0` reaches `0, 1, 3, 4, 2, 5`, so the 1st recipient is `0` and the 4th is `4`. From `1` the order is `1, 3, 4`, so the 3rd is `4`. From `2` the order is `2, 5`, so the 2nd is `5`. Employee `5` has no reports, so a 2nd recipient does not exist and the answer is `-1`.
Example 2
Input: `boss = [-1, 0, 0, 0, 2, 4, 0, 2]`, `queries = [[2, 1], [2, 2], [2, 3], [2, 4], [2, 5]]`
Output: `[2, 4, 5, 7, -1]`
Employee `2` manages `4` and `7`, and employee `4` manages `5`. A transmission from `2` reaches `2, 4, 5, 7`: employee `4`'s whole subtree (`4`, then `5`) is drained before sibling `7`, because `4 < 7`. Employee `2`'s subtree holds only 4 employees, so `k = 5` has no answer.
Constraints
- 1 <= n <= 200,000, where n == len(boss)
- 1 <= len(queries) <= 200,000
- boss[0] == -1, so employee 0 is the root
- 0 <= boss[i] <= n - 1 for every i in [1, n - 1], and boss forms one valid rooted tree: no cycles, and every employee is reachable from employee 0
- queries[j] == [start, k] with 0 <= start <= n - 1
- 1 <= k <= 10^9; k may exceed the number of employees in start's subtree, in which case the answer for that query is -1
- The hierarchy can be a single chain, so the traversal depth can reach 200,000
Examples
Input: ([-1, 0, 0, 1, 1, 2], [[0, 1], [0, 4], [1, 3], [2, 2], [5, 2]])
Expected Output: [0, 4, 4, 5, -1]
Explanation: Worked example 1. Transmission from 0 reaches 0, 1, 3, 4, 2, 5. Query [5, 2] asks past the end of a one-employee subtree, so the answer is -1.
Input: ([-1, 0, 0, 0, 2, 4, 0, 2], [[2, 1], [2, 2], [2, 3], [2, 4], [2, 5]])
Expected Output: [2, 4, 5, 7, -1]
Explanation: Worked example 2 from the prompt: employee 2 manages 4 and 7 and employee 4 manages 5, so a transmission from 2 reaches 2, 4, 5, 7. Sibling 4 is fully drained before sibling 7 starts.
Hints
- Answering each query with its own traversal costs O(n) per query, which is too slow when both n and the number of queries reach their limits. Ask what a single traversal of the whole hierarchy could precompute once.
- In a depth-first preorder, the employees of any subtree occupy a contiguous stretch of the traversal. If you knew where each subtree's stretch begins and how long it is, what would a query cost?
- Depth can reach 200,000, so language-level recursion will overflow its stack. Drive the traversal with an explicit stack instead, and push each manager's reports so that the smallest-numbered one is processed first.