Manager K Levels Up in an Org Chart
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 <= 10000parent[0] == -1, and0 <= parent[i] < parent.lengthfor everyi >= 1- The manager links form one tree with employee 0 at the top (no loops).
1 <= queries.length <= 5000queries[j] = [node, k]with0 <= node < parent.lengthand1 <= k <= parent.length
More Rippling Phone Screen questions
- Filter, Sort, and Deduplicate Scheduled TasksPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Stateful Log Transform and SearchPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Dependency-Aware Task SchedulerPHONE SCREEN · Seen Nov 2026
- Delivery Cost Tracker with Effective-Dated RatesPHONE SCREEN · Seen Nov 2026
- Camel CardsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Best and Worst Camel Card CompletionsPHONE SCREEN · Seen Nov 2026
- Corporate Card Expense RulesOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- In-Memory Priority Task SchedulerPHONE SCREEN · Seen Oct 2026
- Limit an Organization Tree's HeightPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Median Across N Sorted ArraysPHONE SCREEN · Seen Oct 2026
Similar questions at other companies
- Minimum Cameras to Monitor a Binary TreeOYO Rooms · PHONE SCREEN
- Lowest Common Manager for Employee GroupsAmazon · PHONE SCREEN
- Minimum Stores for a Shopping ListWhatNot · PHONE SCREENWhatNot interview questions
- File Encryption Tree OptimizationDatabricks · PHONE SCREEN · ONSITE INTERVIEWDatabricks interview questions
- Assign Distinct Letter Values to Minimize XORWayfair · PHONE SCREENWayfair interview questions
- Lowest Common Manager for Employee GroupsGoogle · PHONE SCREENGoogle interview questions
- Minimum Distance Matching in a ForestScale AI · PHONE SCREEN · ONSITE INTERVIEWScale AI interview questions
- Maximum Words in Disjoint Grid PathsIndeed · PHONE SCREENIndeed interview questions
- Maximum Path Sum Between Marked NodesDoorDash · PHONE SCREENDoorDash interview questions
- Minimum Semesters with a Course LimitSnowflake · PHONE SCREENSnowflake interview questions
Interview reports that mention this question
Rippling interview experiences
- Rippling No-Level Older Reports: 31 Experiences (Part 6 of 6)
- Rippling No-Level Onsite Loops: 24 Experiences (Part 5 of 6)
- Rippling No-Level Screens and Loops: 18 Experiences (Part 4 of 6)
- Rippling No-Level Coding Screens: 37 Experiences (Part 3 of 6)
- Rippling No-Level Design, Screens: 30 Experiences (Part 2 of 6)