FastPrepManager K Levels Up in an Org Chart

Manager K Levels Up in an Org Chart

Rippling logoRippling● HardFULLTIMEPHONE SCREEN

Updated

Problem statement

A company's org chart has n employees numbered 0 to n - 1. parent[i] is the manager of employee i. Employee 0 is at the top and has no manager, so parent[0] = -1. A manager's number can be bigger or smaller than the employee's number.

Each query [node, k] asks: who is k levels above employee node? One level up is the direct manager, two levels up is that manager's manager, and so on. If the chain reaches the top before k steps, the answer is -1.

Return an array with the answer to each query, in query order.

Function

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

Examples

Example 1

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

Employee 6 reports to 5, 5 to 3, 3 to 1 and 1 to 0. So 1 level up from 6 is 5, 3 levels up is 1 and 4 levels up is 0. Going 5 levels up passes the top, so the answer is -1. From 4, 2 levels up is 0 (4 to 1 to 0). From 2, 2 levels up passes the top: -1.

Example 2

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

A manager can have a bigger number than the employee. The chain is 1 to 3 to 2 to 0. From 1, 3 levels up is 0 and 4 levels up is -1. From 3, 1 level up is 2.

Example 3

parent = [-1]queries = [[0,1]]return = [-1]

Employee 0 is at the top and has no manager, so 1 level up is -1.

Constraints

  • 1 <= parent.length <= 10000
  • parent[0] == -1, and 0 <= parent[i] < parent.length for every i >= 1
  • The manager links form one tree with employee 0 at the top (no loops).
  • 1 <= queries.length <= 5000
  • queries[j] = [node, k] with 0 <= node < parent.length and 1 <= k <= parent.length

More Rippling Phone Screen questions

Similar questions at other companies

Interview reports that mention this question

Rippling interview experiences

All Rippling interview questionsSee Rippling hiring insights
Saved
class Solution {
    public int[] getKthAncestor(int[] parent, int[][] queries) {
        // Write your code here.
    }
}
Checking account…