An HR tool answers "who is this person's manager k levels up?" many times a second. The company has n people numbered 0 to n - 1. managers[i] is the direct manager of person i, or -1 for the one person at the top.
Write kthManagers(managers, queries) where each query is [person, k]. Return an array with, for each query, the person k levels above person (k = 0 is the person themself), or -1 if the chain isn't that long. Aim for about O(log n) per query after some preparation.
Input: managers = [-1,0,0,1,1,3,5], queries = [[6,3],[6,1],[2,2]] Output: [1,5,-1]
Above 6 are 5, 3, 1, 0, so 3 levels up is 1. Person 2 has only one manager above them.
Input: managers = [-1], queries = [[0,0],[0,1]] Output: [0,-1]
k = 0 is the person; the top person has no manager.
1 <= n <= 5 * 10^41 <= queries.length <= 5 * 10^40 <= k <= 10^5Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #373 K-th Manager Up the Chain. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.