# Google Foobar Challenge: Ion Flux Relabeling

I am currently working on a Foobar challenge, the Ion Flux Relabelling. I came up with a java solution but Google returns an OutOfMemoryError.

The prompt is, quoting the original question:

Oh no! Commander Lambda's latest experiment to improve the efficiency of her LAMBCHOP doomsday device has backfired spectacularly. She 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. She's 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, she 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 answer(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, answer(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.

The test cases provided are:

Inputs:

(int) h = 3
(int list) q = [7, 3, 5, 1]


Output:

(int list) [-1, 7, 6, 3]


Inputs:

(int) h = 5
(int list) q = [19, 14, 28]


Output:

(int list) [21, 15, 29]


I used a rather complex and dumb way to solve the problem. I created two lists, one recording every pair of children in the binary tree, the other one recording all the corresponding parents to these children in corresponding indexes. So my children list for the height 3 binary tree provided above would look like [[3, 6], [1, 2], [4, 5]], and the relevant part of my parent list would look like [7, 3, 6].

To find the parent of the elements given in array q, I just ran a loop to look for the element in the children list and, after finding it, record the corresponding parent since they have the same index.

import java.util.*;

public static int[] answer(int h, int[] q) {
int root = ((int) Math.pow(2, h) - 1);
int[] corr = new int[q.length];
List<List<Integer>> childs = new ArrayList<List<Integer>>();
List<Integer> parent = new ArrayList<Integer>();
//Loop through each "height"
for(int i = 0; i < h - 1; i++){
int index = 0;
index = parent.size();
//Loop through each element in each height
for(int l = (int) Math.pow(2, i); l > 0; l--){
int x = parent.get(index - l) - (int) Math.pow(2, h-(i+1));
int y = parent.get(index - l) - 1;
}
}
for(int​ ​i​ ​=​ ​0;​ ​i​ ​<​ ​q.length;​ ​i++){
if(q[i]​ ​==​ ​root){
corr[i]​ ​=​ ​-1;
}
for(int​ ​l​ ​=​ ​0;​ ​l​ ​<​ ​childs.size();​ ​l++){
if(childs.get(l).get(0)​ ​==​ ​q[i]​ ​||​ ​childs.get(l).get(1)​ ​==​ ​q[i]){
corr[i]​ ​=​ ​parent.get(l);
}
}
}
return corr;
}
}


Like I said, Google returns an OutOfMemoryError for my code during execution.

I totally understand that my method is not the most efficient solution. So really, I am trying to find the most effective way to solve this problem in Java. There must be something really simple that I am just not seeing.

In your own words: "I totally understand that my method is not the most efficient solution." In a sense, that's the summary of a code review for this problem.

The basic issue in your code is that you have ignored two of the clues in the question:

• "Flux chains require perfect binary trees"
• "she performed a post-order traversal"

These two clues are begging you to implement a recursive post-order traversal of a fixed depth tree.

If you know a node is missing from the flux chain, then you know that your traversal "up" from that node in a correct tree, will take you to the parent.

A complication in this problem is that you don't know the order of the disconnected flux chain nodes in the input, so you have to "search" for them in the output, but.... with a small trick, you can turn the whole problem in to a single (post-order) traversal of the ideal (correct) flux chain, and a small lookup table for the answer indices.

The above solution would be an $O(n)$ time complexity solution, and would use a small amount of memory proportional to the count of values in q.

Now, that's the solution I think they would expect in a good case.... but I suspect that there's a mathematical solution that is much faster.... I am still figuring it out... but, in the mean time, consider this code that does a post-order traversal, and identifies key nodes in the flux chain. It then uses a trick in the return value of the recursive function (negative values for missing links) and a HashMap to identify the keys, and their respective indices in the answer array. This is not my most pretty code, but it serves to show you the post-order traversal with the index lookup:

public static final int[] answer(int height, int[] nodes) {
int[] ans = new int[nodes.length];
Map<Integer, Integer> indices = new HashMap<>();
IntStream.range(0, nodes.length).forEachOrdered(i -> indices.put(nodes[i], i));
int next = postOrder(height, 0, 0, indices, ans);
if (next < 0) {
int i = indices.get(-next);
ans[i] = -1;
}
return ans;
}

private static int postOrder(int limit, int depth, int next, Map<Integer, Integer> indices, int[] ans) {
if (depth == limit) {
return next;
}
// left
int left = postOrder(limit, depth + 1, next, indices, ans);
next = left < 0 ? -left : left;
int right = postOrder(limit, depth + 1, next, indices, ans);
next = right < 0 ? -right : right;

int me = next + 1;

if (left < 0) {
int i = indices.get(-left);
ans[i] = me;
}
if (right < 0) {
int i = indices.get(-right);
ans[i] = me;
}

return indices.containsKey(me) ? -me : me;

}


You can see it running the test-cases in ideone: https://ideone.com/J0lMrf

Update:

I worked out a better solution using a binary search mechanism for locating the parent of a referenced link in the Flux chain.

It is a bit hard to describe in words, but if you inspect the post-ordered tree, you can predict which branch (left or right) to descend to find a node. You can also compute the size of the sub-trees to any node, and thus compute that node's label.

Expressed in code, you can compute the parent of any link in a tree of a given height, with the code:

private static final int parent(int height, int node) {
int size = (int)Math.pow(2, height) - 1;

if (node == size) {
return -1;
}

int before = 0;
do {
if (size == 0) {
throw new IllegalStateException();
}
// size is always odd, and halving it integer-division is also odd.
size >>>= 1;
int left = before + size;
int right = left + size;
int me = right + 1;
if (left == node || right == node) {
return me;
}
if (node > left) {
// nodes to the right have the left as offset.
before = left;
}
} while (true);

}


This makes the computation for any 1 node an $O(\log{h})$ operation... and, if there are q nodes to locate, the overall result would be an $O(q \log{h})$ one.

The "final" solution would be:

public static final int[] answerToo(int height, int[] nodes) {
return IntStream.of(nodes).map(n -> parent(height, n)).toArray();
}


I have combined this with the earlier solution, and the result is in ideone too: https://ideone.com/qiwPtR

• Updated answer with a more systematic answer related to a binary descent of the tree - this is the more mathematical answer I suspected. – rolfl Dec 21 '16 at 5:22
• I'm sorry, but can you explain the >>>= operator please? – Tiger W. Dec 21 '16 at 14:46
• After playing around with it, I have realized what it does... Also, your code took me a while to grasp but I have learned a lot from it. Thank you. – Tiger W. Dec 21 '16 at 15:59
• Thanks! I had a sense there was a mathematical answer to this problem. I ended up writing a Gist that tries to better explain how the predicting logic works. gist.github.com/dishbreak/48bca2c9c60420a53920c39e08d16c56 – Vishal Kotcherlakota Oct 2 '17 at 22:25