I'm doing a practice coding test problem and I have no idea how to solve this. Am I just moronic or is this supposed to be very difficult?
I'm doing a practice coding test problem and I have no idea how to solve this. Am I just retarded or is this supposed to be very difficult?
what's difficult about it? It's fairly trivial. Go through the array in segments of size 1, 2, 4, 8, etc. Then count the value of each node towards the side they are on. For example
3 -> it's root, ignore
[6, 2] -> add 6 to left, 2 to right
[9, -1, 10, -1] -> add 9 to left, 10 to right
and so on. In the end you have a sum for left and a sum for right. Compare and print an answer.
I don't understand how it even makes sense for a binary tree to be represented as an array or how you're supposed to traverse it. I've spent an hour trying to make sense of it and I don't see it.
Go from root node thru children R->L then the nodes of those children R->L
What I don't understand is how you even know what position in the array is what depth in the tree, since you can have an arbitrary number of nodes at each depth. How does it makes any sense to represent this kind of data structure as an array?
This is your brain on web dev.
Well this was a coding test categorized under "frontend", which makes no sense because I've been a frontend dev for years and I've never had to do anything even remotely like this in my day to day work.
Yeah its pretty dumb man
It's a terrible representation of the data structure, but it makes sense.
Assume we count from 1. Array value 1 is the root. Array values 2 and 3 are the next branch down, left to right. Array values 4 through 7 are the next branch down, left to right. Array values 8 through 15 are the next branch down, left to right.
Within each chunk, the "left" half of the tree is the first half of the values; the "right" half of the tree is the right half of the values.
Go through each chunk, cut it in half, add up the halves, repeat until done. Then compare the sums. Be sure to ignore the -1's.
So if there's no node it's always going to be represented as a -1? The question doesn't make that clear at all because in the example it just ends at 10 instead of -1 for the missing node after it.
Leetcode? Shitty pajeet platform where everyone copy pastes shared submissions.
No this is on hired.com
Spend your shekels elsewhere if a introductory problem is this gay
yeah that's the confusing part. The last item in the array should be -1. I guess we can assume that if the last layer abruptly ends, the rest of it is all -1s.
It's represented as an array in chunks. First element in the array is the root. Next two elements are the first layer of the tree. Next four elements are the second layer of the tree, etc.
>Next four elements are the second layer of the tree, etc.
not op. there's only 3 elements in the example tree second layer. if it was always 1248 then that's easy. but 3 makes no sense to me either.
they're just truncating the array when the final elements would be blank nodes. it's to save memory, otherwise you could end up wasting additional space simply to represent nothing.
[3, 6, 2, 9, -1, 10] is equivalent to [3, 6, 2, 9, -1, 10, -1]
The array represents the value of each node in breadth first traversal, with missing nodes represented as -1.
Starting at depth 0, we add the root to the array. This gives us [3]
Next at depth 1, we add the two children of our root. There are no missing nodes, so we have [3, 6, 2]
At depth 2, things get interesting. We could have up to 4 nodes here, but we only have 2. So working from left to right, we first add 9, then we add -1 to account for the fact that there is no right child from the node labeled 6. The -1 represents the missing space. Then going to the right side of the tree (the children of 2, we add 10 next. If we had any more nodes to go below this (i.e. a depth 3), we could add a -1 after this, but we don't, so we just leave the array as is.
This should make the final array [3, 6, 2, 9, -1, 10]
Read https://en.wikipedia.org/wiki/Binary_heap#Heap_implementation.
How do you know that 5 was split in two but 3 only has 1 branch?
The children of the element at index i are at indices 2i+1 and 2i+2. So the children of (3) at index 2 are at indices 5 and 6. Since index 6 doesn't exist, there is no right child.
Seriously, read the wiki article.
I got that but what if the tree is deeper, do you leave a blank spot for the missing index?
The questions says -1 means no node.
uh oh. you did not read the books
You just traverse the branches and compare the sizes? How is it hard?
all you gotta do is run a pre-order on that tree, add values until you get back to the root, save that value, then do the same for the other side
Couldn't you start at [1], split the arrays into two more arrays (left and right) based upon every other one (off even index after [0], and then subtract left from right. If you have a positive number, or a negative number would tell you left or right
The absolute state of code bootcampers
you have to learn it, unironically. Despite what CStards claim it's not an IQ test, they all just grind hundreds of questions and more or less memorize the approaches. It's like how the chinese learn math, just constant practice
>Despite what CStards claim it's not an IQ test, they all just grind hundreds of questions and more or less memorize the approaches
that's how iq tests work too, so it kind of is one.
Does "larger" here mean "more nodes" or does it mean "the sum of the values in the nodes is larger"?
Are nodes guaranteed to have values >=0? If not, how do I distinguish a node with value "-1' from an empty node?
Question sucks.
It means the sum is larger because in the example they gave, the output is Left.
function solution(nums) {
if(nums.length < 2)
return "";
const left = (e,i) => {
const depth = Math.floor(Math.log2(i+1));
const position = i + 1 - Math.pow(2,depth);
return position < Math.pow(2,depth)/2;
}
const sum = (acc, e) => acc + e;
const arr = [0, ...nums.slice(1).map(e => e==-1?0:e)];
const all_sum = arr.reduce(sum, 0);
const left_sum = arr.filter(left).reduce(sum, 0);
const right_sum = all_sum - left_sum;
if(left_sum == right_sum)
return "";
return left_sum > right_sum? "LEFT" : "RIGHT"
}
console.log(solution([3,6,2,9,-1,10]));
Inefficient recursive solution
function subtreeSize(array, i)
{
if (i >= array.length)
return 0;
if (array[i] == -1)
return 0;
let sum = 0;
sum += array[i];
sum += subtreeSize(array, 2*i + 1);
sum += subtreeSize(array, 2*i + 2);
return sum;
}
function largerBranch(array)
{
const left = subtreeSize(array, 1);
const right = subtreeSize(array, 2);
if (left > right)
return "Left";
if (right > left)
return "Right";
return "";
}
+RAPE DICK+
+LEFT FOOT ZAPPER+
>this will be your competition in 5 years
good to know i've got job security
Simple linear scan. The first half of each row of nodes is added to the left sum, the second to the right.
function largerBranch(array)
{
let left = 0;
let right = 0;
// rowStart..rowEnd is row of all nodes at current depth
// rowStart..rowMid belong to the left branch
// rowMid..rowEnd belong to the right branch
let rowMid = 2;
let rowEnd = 3;
for (let i = 1; i < array.length; i++)
{
if (i === rowEnd) {
// Advance to next row
rowMid = 2*rowMid + 1;
rowEnd = 2*rowEnd + 1;
}
if (array[i] === -1)
continue;
if (i < rowMid)
left += array[i];
else
right += array[i];
}
if (left > right)
return "Left";
if (right > left)
return "Right";
return "";
}