[Google foobar] Level 2 Ion Flux Relabeling

Google foobar challenge level 2 - Ion Flux Relabeling

Description

Ion Flux Relabeling

Oh no! Commander Lambda’s latest experiment to improve the efficiency of the LAMBCHOP doomsday device has backfired spectacularly. The Commander had been improving the structure of the ion flux converter tree, but something went terribly wrong and the flux chains exploded. Some of the ion flux converters survived the explosion intact, but others had their position labels blasted off. Commander Lambda is having her henchmen rebuild the ion flux converter tree by hand, but you think you can do it much more quickly — quickly enough, perhaps, to earn a promotion!

Flux chains require perfect binary trees, so Lambda’s design arranged the ion flux converters to form one. To label them, Lambda performed a post-order traversal of the tree of converters and labeled each converter with the order of that converter in the traversal, starting at 1. For example, a tree of 7 converters would look like the following:

7
3 6
1 2 4 5

Write a function solution(h, q) - where h is the height of the perfect tree of converters and q is a list of positive integers representing different flux converters - which returns a list of integers p where each element in p is the label of the converter that sits on top of the respective converter in q, or -1 if there is no such converter. For example, solution(3, [1, 4, 7]) would return the converters above the converters at indexes 1, 4, and 7 in a perfect binary tree of height 3, which is [3, 6, -1].

The domain of the integer h is 1 <= h <= 30, where h = 1 represents a perfect binary tree containing only the root, h = 2 represents a perfect binary tree with the root and two leaf nodes, h = 3 represents a perfect binary tree with the root, two internal nodes and four leaf nodes (like the example above), and so forth. The lists q and p contain at least one but no more than 10000 distinct integers, all of which will be between 1 and 2^h-1, inclusive.

Languages

To provide a Java solution, edit Solution.java
To provide a Python solution, edit solution.py

Test cases

Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.

— Java cases —
Input:
Solution.solution(5, {19, 14, 28})
Output:
21,15,29

Input:
Solution.solution(3, {7, 3, 5, 1})
Output:
-1,7,6,3

— Python cases —
Input:
solution.solution(3, [7, 3, 5, 1])
Output:
-1,7,6,3

Input:
solution.solution(5, [19, 14, 28])
Output:
21,15,29

Idea

문제를 간단히 표현하자면 높이가 주어진 Full Binary Tree에서 후위 순회로 방문하는 N번째 노드의 부모 노드가 몇번째 방문할지를 찾는 문제이다.

후위순회에서 부모 노드의 인덱스는 자식노드로 부터 아래와 같이 구할 수 있다.

left child : index of left child + power(2, left child level) - 1
right child : index of right child + 1

이제 타겟 노드의 인덱스를 찾아 레벨과 왼쪽, 오른쪽 여부만 알 수 있으면 위 공식을 적용해서 구할 수 있다. 높이가 최대 30이므로 최대 2³⁰ 개의 노드가 있기 때문에 미리 모든 노드의 인덱스를 구할 수는 없다. 이 경우 이진 탐색을 통해서 노드의 레벨과 위치를 구해야 한다.

시작은 루트로부터 시작하므로 한쪽 자식 노드의 총 노드의 개수는 2^(level-1)-1 공식으로 구할 수 있다. 그렇다면 후위 순회로 시작할때 오른쪽 하위 노드 중 먼저 만나는 노드의 인덱스는 current node - 2^(level-1) + 1 로 구할 수 있다. 이제 이 값을 통해 왼쪽으로 이동할지 오른쪽으로 이동할지를 판단하여 타겟 노드의 레벨과 위치 정보를 계산할 수 있다.

Time Complexity : O(nlogn)
Space Complexity : O(1)

Code

public class Solution {
    private static int[] dp = new int[31];
    private static class Node {
        private int level;
        private boolean leftChild;

        public Node(int level, boolean leftChild) {
            this.level = level;
            this.leftChild = leftChild;
        }

        public int getLevel() {
            return level;
        }

        public boolean isLeftChild() {
            return leftChild;
        }
    }

    private static Node getNode(int level, int node, int target, boolean leftChild) {
        if(node == target) return new Node(level, leftChild);

        int rightChildStart = node - dp[level-1] + 1;
        if(rightChildStart <= target) {
            return getNode(level - 1, node - 1, target, false);
        } else {
            return getNode(level - 1, rightChildStart - 1, target, true);
        }
    }

    public static int[] solution(int h, int[] q) {
        final int root = (1<<h) - 1;
        dp[0] = 1;

        for(int i = 1; i <= h; i++) {
            dp[i] = dp[i - 1]<<1;
        }

        for(int i = 0; i < q.length; i++) {
            if(q[i] != root) {
                Node node = getNode(h, root, q[i], false);
                if(node.leftChild) {
                    q[i] = q[i] + dp[node.level];
                } else {
                    q[i] = q[i] + 1;
                }
            } else {
                q[i] = -1;
            }
        }

        return q;
    }
}