FastPrep
Problem · Tree

Chain of Command

Learn this problem
● MediumUberINTERNOA
See Uber hiring insights

Problem statement

An organization is made up of n people. The organizational structure can be represented as a tree, with each person representing a node in the tree. All but the root node has a single parent, representing the node's upstream reporting line. A node may have zero or more children, representing those people who report into them.

If person 1 is the root of the tree, we can represent this structure in an array parent, where parent[i] represents the parent of node i + 1. Note that parent[0] = -1 to indicate no parent.

Within this organization, directives may be issued from a person to all people reporting into them, including all descendants in the tree. These directives propagate as follows:

  • A person sends the directive to its direct child nodes in ascending order of their indices.
  • If a node has more than one child, the node waits for propagation to complete fully to each child's subtree before issuing the directive to the next child.
  • Each child node propagates the directive to its subtree using the same process.
  • The propagation stops when all nodes in the subtree have received the directive.

For a single directive, determine who was the kth person to receive it. This query can be modeled as a tuple [startNode, k], where startNode is the person issuing the directive.

If k is greater than the total number of people receiving the directive, including direct reports and descendants of their direct reports, return -1 to indicate that no kth person exists.

For a given organization, evaluate all queries independently and return an integer array whose element at each position is the answer to the corresponding query.

Function

chainOfCommand(parent: int[], queries: int[][]) → int[]

Examples

Example 1

parent = [-1, 1, 1, 1, 3, 5, 3, 5, 7]queries = [[1, 5], [7, 2], [9, 2], [3, 6]]return = [6, 9, -1, 9]

The array parent represents the tree shown in the source. If person 1 issues a directive, people receive it in the following order: [1, 2, 3, 5, 6, 8, 7, 9, 4].

If person 3 issues a directive, people receive it in the following order: [3, 5, 6, 8, 7, 9].

If person 7 issues a directive, people receive it in the following order: [7, 9].

If person 9 issues a directive, people receive it in the following order: [9].

Processing the queries:

  1. queries[0] = [1, 5]: if person 1 issues a directive, the 5th person receiving it would be 6.
  2. queries[1] = [7, 2]: if person 7 issues a directive, the 2nd person receiving it would be 9.
  3. queries[2] = [9, 2]: if person 9 issues a directive, there is no 2nd person to receive it.
  4. queries[3] = [3, 6]: if person 3 issues a directive, the 6th person receiving it would be 9.

Hence, the array returned is [6, 9, -1, 9].

Example 2

parent = [-1, 1, 1, 2, 2]queries = [[1, 3], [2, 3]]return = [4, 5]

If person 1 issues a directive, people receive it in the following order: [1, 2, 4, 5, 3].

If person 2 issues a directive, people receive it in the following order: [2, 4, 5].

For queries[0] = [1, 3], the 3rd person to receive the directive is person 4. For queries[1] = [2, 3], the 3rd person to receive the directive is person 5.

Hence, the array returned is [4, 5].

Constraints

  • 2 <= n <= 10^5
  • 1 <= parent[i] <= n for all nodes except the root node, where parent[0] = -1
  • 1 <= q <= 2 * 10^5
  • 1 <= queries[i][0] <= n
  • 1 <= queries[i][1] <= n

More Uber problems

drafts saved locally
public int[] chainOfCommand(int[] parent, int[][] queries) {
  // write your code here
}
parent[-1, 1, 1, 1, 3, 5, 3, 5, 7]
queries[[1, 5], [7, 2], [9, 2], [3, 6]]
expected[6, 9, -1, 9]
checking account