When Google asks you to invert a binary tree on a whiteboard...

When Google asks you to invert a binary tree on a whiteboard, are they asking for pseudo code or is there a tree and you move around the nodes? Or something else? Because I'm in my 3rd semester of community college and I know how to do both.

Why didn't he just turn the white board upside down?

What's a binary tree?

>asked to invert binary tree on white board
>i knew this would happen, so i came prepared
>pull out drill and begin removing all the screws i can find
>dragged out of building by security before i could finish

A data structure where each node has up to 2 children.

literally, what kind of reet can't do that though?

Wait I'm rusty on my data structures but inverting a binary tree would be mainly changing changing position of branches

Someone should tell that dumb cuckold that 90% of people don't have macs and he isn't entitled to a job if he can't pass the interview

I'm glad he didn't get it

It would be funny to go in and actually invert the tree for some arbitrary node rather than simply mirroring it.

So who is this fucking nobody and why should I care about his butthurt.

Had to Google this shit but he made a package manger for Macs 6 years ago and has be milking that fact ever since

I understand that he's just whining like a bitch, but how did he not get hired by Google while moot did?

>Because I'm in my 3rd semester of community college and I know how to do both.
Good on you.

90% of job interview questions come straight out of your discrete math and introduction to algorithms courses.
It's too keep out the Pajeets who can't get anything done without stackoverflow open.

moot knows how to suck better.

Is this really all that it is? How could he not do this?

Real spit, I'm not a programmer, how hard is it to invert a binary tree?

invert Empty = Empty
invert (Node v l r) = Node v (invert l) (invert r)


wow 2 seconds

When I attended my google interview I just drew a tree and said we need to go green. I got the job.

Easier than fizzbuzz

All you have to do is die your hair blue and have a vagina.

They will hire you for HR if nothing else.

>it doesn't even invert the tree
LOL

No job for you, bud!

Really? I just drew the tree with the bird nests and all upside down. They didn't like it.

Where you asked about your views on feminism?

Nice meme.

>building security tries to drag me out of the building
>i knew this would happen, so i came prepared
>pull out drill and begin drilling all the eyeballs i can find

It doesn't do anything to the tree though, idiot. Good job.

I think you have to do the individual steps

which is silly, because on a whiteboard you can just draw the completed thing really quickly

That's why I said "nice meme" instead of calling you a retard, pajeet.

But it's no meme that is retarded

Try doing this in C++, I bet none of you can

Literally less than 10 lines of code

Not doing your homework for you, rajeet

I'm a C++ programmer who was doing it as a job, and I don't know what a binary tree is, or how to invert it.

swap ‘invert r’ and ‘invert l’

>comp sci 101
>can't do it
>want to work at google
🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗🤗

Dont you just find each bottom node and then change the point so that the bottom node now points to its parent, then you move to its parent and do the same thing.

If it was explained to me exactly what inverting a binary tree means I could probably figure out how to do it but I don't know it off the top of my head.

"Inverted" is misleading. This is what it actually means.

If I was in charge of naming things I would call that flipping

This is what they meant in the interview

Think he had to write the pseudocode

Completely useless exercise of course. Interviewer self wankery. Whiteboard interviews are dumb.

????

"Reflect" seems like it would probably be a better term. However, given this case wouldn't you just recursively traverse each node of the tree and swap its left and right nodes?

pleb!

>want to work at google

>However, given this case wouldn't you just recursively traverse each node of the tree and swap its left and right nodes?
You won't get a job if you still use recursion in 2016.

Yeah
define function invert(Node head):
if head has a left child:
swap(head.left)
if head has a right child:
swap(head.right)
Node temp = head.left
head.left = head.right
head.right = temp

I was thinking the same thing. There is probably a more efficient way to do it but recursion is the first thing that comes to my mind.

Interesting, I should get a fallback unicode font.

What would be the better way?

One of the worst posts I've ever read

More than 10 lines of code, I bet you're some shitty java dev

Starting a huge company, getting a ton of job applicants, and forcing the interviewees to do it on a whiteboard.

Jokes on you, I'm already employed. Anyways, do you have a better solution to this then a recursive approach. I checked out an iterative approach but I fail to see any significant benefit to it other then some people have trouble conceptualizing recursion?

You can't use tail call optimization when inverting a binary tree, so recursion depth will still be a thing here

That's not going to lose you a job

>community college

Doesn't matter if you have a job, if you can't grasp why a recursive approach is not suitable in an age where we are handling more data, and the algorithm cannot be tail-call optimized, then you are not fit to solve the problem

I don't see what that has to do with anything

what
a common interview question is "implement factorial with recursion and then iteration"

looping is technically an abstracted type of recursion

doesn't inverting a binary tree do nothing? all the nodes are still connected to the same nodes. they are exactly the same tree

Don't talk to me or my leafs ever again

>thinks you should optimize the solution before creating it
>ultimate rookie mistake
>telling other people they aren't fit to have a job

>community college
You won't even get noticed for an interview so don't worry about it.

No it's not

>looping is technically an abstracted type of recursion
dear god

>looping is technically an abstracted type of recursion
It's not recursion in the common usage of the term, and has different effects on the stack

>thinks you should optimize the solution before creating it
This is not about optimizing a solution before creating it, it's about basic knowledge that recursion incurs recursion depth, unless tail-call optimized. That's like saying 'I can use long longs because you don't need to optimize before creating a solution'

For all the hate about recursion you sure don't seem to understand the concept of a logarithmic depth

Additionally, using iteration does not imply optimization, it's another approach, and the right approach to inverting a binary tree

>tripfag can't read
What a surprise

if(!root)
return;
invert(root->left);
invert(root->right);
std::swap(root->left, root->right);

Oh we understand, and there is no hate, but shallower depth does not imply complete protection from stack overflow

I think you're misunderstanding the point of the question. They really don't care what your initial idea is to solving a freshman level problem, they just want to see if you have an idea, and if you don't, how you would approach solving a new problem.

Yes I'm sure you're Google lmao

can someone tell me what trees are used for other than job interviews?

Great source of oxygen imo

They're used in Java and Python when you call functions to sort sometimes

Not even Google engineers write them

I literally talked to a guy with a PhD about his interview process on Monday. In fact, it was even in person and not on an anonymous image board. He is not Google, but he writes medical imaging software.

Every single data structure is essentially a tree

>He is not Google
Not making your point any stronger lad

Binary trees, not much. Other kinds of trees have their own applications.

Yes, by citing evidence, I made my point weaker. Somehow you are making your point stronger by saying mine is invalid because I'm not Google. You aren't Google either, so everything you're saying is wrong, right?

void invert(Node *head, nodecount) {
Node *temp;
for(int i = 0; i < nodecount; i++){
temp = head[i * 4];
head[i * 4] = head[i * 4+1];
head[i * 4 + 1] = temp;
}
}

The easy way, assuming your nodes are in a contiguous block of memory and contain three Node pointers, a value and some padding.

I'm not Google, but you are still making your point weaker since you also tried to dictate what is right, and then started providing really shitty and not really relevant "evidence". My lack of basis, on the other hand, is still coupled with true facts about recursion and iteration

invert_node(Node node)
{
if (node != null)
{
Node temp_node = node.get_right node();
node.set_right_node(node.get_left_node());
node.set_left_node(temp_node);

invert_node(node.get_left_node());
invert_node(node.get_right_node())
}
}

*two node pointers

non programmer here:

why don't they just let him google the answer? what difference does it make if you can do random things on the spot?

seems like at a place like google your people skills matter more than your ability to do some kind of esoteric coding exercise in an interview. i bet there's some autistic robot man who has mind melded with computers but is completely non-functional in the context of a project team. he could do this binary tree shit 24/7 but that doesn't mean shit

Because if the answer to every question google had could be found on google, they wouldn't need to hire anybody.

>why don't they just let him google the answer
they probably want qualified applicants

The answer to how to do algorithm shit that nobody more than a year out of their CS degree remembers does in the real world, is, however, on google.

They don't want people googling basic data structure theory while they're on the job, though. They want them to know it off the top of their head.

It's important to understand fundamentally and conceptually what you're doing. The question they're asking isn't that asinine either.

You can't just google up a piece of software. Developing requires actually using a bit of your brain and problem solving. Not all problems have already been solved. Inverting a binary tree, Fizzbuzz, and the like, are useful because, as simple as they are, they weed out so many people. You only need basic problem solving skills, you're right, so they should be able to invert a binary tree if asked with no issues

>I'm entitled to a job for life because I made some semi-useful thing 'for free like a retard instead of protecting it and getting paid' homebrew but can't into basic community college level undergrad pseudomath.
I'm surprised he even got an interview.
cool story bro

>assuming your nodes are in a contiguous block of memory

big assumption

pseudocode for this is really easy, how could you fuck this up?

for each node {
if it's not a leaf && has more than 1 branches {
swap the branches
}
}

of course you have to iterate from root -> tips, but that shouldn't be hard. hell, the default node ordering should be like that already. as long as you're doing it that way, you can parallelize too. replace that first for loop with an apply function and yer done.

This is autism

This is wrong

See

I hate to tell you this user but most advances and innovation in tech comes from massive autists.

>but that shouldn't be hard.
then do it

lmao you managed to fuck it up right there

You're right, I should allow for discontiguous blocks.
void invert(Node *head, nodecount) {
Node *temp;
for(int i = 0; i < nodecount; i++){
temp = head[i * 4];
head[i * 4] = head[i * 4+1];
head[i * 4 + 1] = temp;
if(head[i * 4 + 2] != NULL){
head = head[i * 4 + 2];
nodecount = nodecount - (i + 1);
i = -1;
}
}
}


Node is now three node pointers (left, right, next block head) and a value.

>"Really easy"
>Gets it wrong

ahahahahahhaahhah