543. Kth Ancestor Lookup

HardTreeDesignDynamic ProgrammingBinary Search3 hints
RPby Rohit Parihar

A genealogy archive stores a family tree of n people numbered 0 to n - 1. The array parent gives each person's parent, and parent[0] = -1 because person 0 is the founder with no parent. Researchers ask the same archive many questions, so the structure should answer each one quickly.

Implement the class AncestorFinder. The constructor AncestorFinder(int n, int[] parent) receives the family tree. The method getKthAncestor(int node, int k) returns the person reached by moving k steps up from node (k = 0 gives node itself, k = 1 its parent, and so on), or -1 if the chain of parents ends before k steps are completed.

Example 1

Input:
operations = ["AncestorFinder","getKthAncestor","getKthAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]arguments = [[8,[-1,0,1,1,3,4,0,6]],[5,2],[5,4],[5,5],[7,1],[2,0]]
Output:
[null,3,0,-1,6,2]
Explanation:

The ancestors of node 5 are 4, 3, 1, 0, so the 2nd is 3, the 4th is 0 and there is no 5th; node 7 has parent 6; asking for the 0th ancestor of node 2 returns 2 itself.

Example 2

Input:
operations = ["AncestorFinder","getKthAncestor","getKthAncestor"]arguments = [[1,[-1]],[0,0],[0,1]]
Output:
[null,0,-1]
Explanation:

A single node is its own 0th ancestor and has no 1st ancestor.

Constraints

1 ≤ n ≤ 5 * 104

parent[0] = -1 and for every other i, 0 ≤ parent[i] < n; the array describes a tree rooted at person 0 (a parent may have a larger index than its child)

0 ≤ node < n

0 ≤ k ≤ 109

At most 5 * 104 calls to getKthAncestor

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.
Time per case
Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms

Expected complexity

Time
O(n log n) build, O(log n) per query
Space
O(n log n)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.