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?
>>54398740
>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
>>54398752
A data structure where each node has up to 2 children.
>>54398676
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
>>54398676
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.
>>54399478
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?
>>54398676
>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.
>>54399654
moot knows how to suck better.
>>54399356
Is this really all that it is? How could he not do this?
>>54398676
Real spit, I'm not a programmer, how hard is it to invert a binary tree?
>>54398676invert 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.
>>54402034
Easier than fizzbuzz
>>54402069
All you have to do is die your hair blue and have a vagina.
They will hire you for HR if nothing else.
>>54402065
>it doesn't even invert the tree
LOL
No job for you, bud!
>>54402069
Really? I just drew the tree with the bird nests and all upside down. They didn't like it.
>>54402069
Where you asked about your views on feminism?
>>54402128
Nice meme.
>>54398794
>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
>>54402142
It doesn't do anything to the tree though, idiot. Good job.
>>54399356
>>54402019
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
>>54402164
That's why I said "nice meme" instead of calling you a retard, pajeet.
>>54402188
But it's no meme that >>54402065 is retarded
Try doing this in C++, I bet none of you can
>>54402239
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.
>>54402128
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.
>>54402302
"Inverted" is misleading. This >>54399356 is what it actually means.
>>54402314
If I was in charge of naming things I would call that flipping
>>54399356
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.
>>54402314
"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?
>>54402370
pleb!
>>54402295
>want to work at google
>>54402372
>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.
>>54402372
Yeahdefine 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
>>54402372
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.
>>54402382
Interesting, I should get a fallback unicode font.
>>54402407
What would be the better way?
>>54402407
One of the worst posts I've ever read
>>54402261
More than 10 lines of code, I bet you're some shitty java dev
>>54402431
Starting a huge company, getting a ton of job applicants, and forcing the interviewees to do it on a whiteboard.
>>54402407
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?
>>54402443
You can't use tail call optimization when inverting a binary tree, so recursion depth will still be a thing here
>>54402469
That's not going to lose you a job
>community college
>>54402468
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
>>54402495
I don't see what that has to do with anything
>>54402407
what
a common interview question is "implement factorial with recursion and then iteration"
>>54402407
looping is technically an abstracted type of recursion
>>54398676
doesn't inverting a binary tree do nothing? all the nodes are still connected to the same nodes. they are exactly the same tree
>>54398802
Don't talk to me or my leafs ever again
>>54402517
>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.
>>54402536
No it's not
>>54402541
>looping is technically an abstracted type of recursion
dear god
>>54402541
>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
>>54402552
>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'
>>54402576
>>54402517
For all the hate about recursion you sure don't seem to understand the concept of a logarithmic depth
>>54402576
Additionally, using iteration does not imply optimization, it's another approach, and the right approach to inverting a binary tree
>>54399377
>tripfag can't read
What a surprise
>>54402239if(!root)
return;
invert(root->left);
invert(root->right);
std::swap(root->left, root->right);
>>54402598
Oh we understand, and there is no hate, but shallower depth does not imply complete protection from stack overflow
>>54402600
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.
>>54402647
Yes I'm sure you're Google lmao
can someone tell me what trees are used for other than job interviews?
>>54402669
Great source of oxygen imo
>>54402669
They're used in Java and Python when you call functions to sort sometimes
Not even Google engineers write them
>>54402656
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.
>>54402669
Every single data structure is essentially a tree
>>54402692
>He is not Google
Not making your point any stronger lad
>>54402669
Binary trees, not much. Other kinds of trees have their own applications.
>>54402701
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?
>>54402239void 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.
>>54402723
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
>>54399356
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())
}
}
>>54402742
*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
>>54402791
Because if the answer to every question google had could be found on google, they wouldn't need to hire anybody.
>>54402791
>why don't they just let him google the answer
they probably want qualified applicants
>>54402804
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.
>>54402816
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.
>>54402791
It's important to understand fundamentally and conceptually what you're doing. The question they're asking isn't that asinine either.
>>54402816
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
>>54398676
>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
>>54402742
>assuming your nodes are in a contiguous block of memory
big assumption
>>54398676
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.
>>54402943
This is autism
>>54402971
This is wrong
See >>54399356
>>54402979
I hate to tell you this anon but most advances and innovation in tech comes from massive autists.
>>54402971
>but that shouldn't be hard.
then do it
>>54402971
lmao you managed to fuck it up right there
>>54402943
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.
>>54402971
>"Really easy"
>Gets it wrong
ahahahahahhaahhah
def ohai *args
puts "#{Tty.blue}==>#{Tty.white} #{args.shell_s}#{Tty.reset}"
endohai "Installation successful!"
ohai "Next steps"
wouldn't have hired that btard either.
(Source: https://raw.githubusercontent.com/Homebrew/install/master/install)
>>54403063
God youre retarded
>Using homebrew
>Not pkgsrc with signed builds
Homebrew is basically the AUR but worse
No good packages, mostly skid/ricer shit like "zomg newer vim", relies on other more mature and reliable systems for its major patches, zero security, and the "port files" are written in ruby (almost as bad as bash, almost)
Respect for google engineers: Going into the negative
Why do the node use pointers?
>>54403141
How the fuck are you going to point to data?
>>54403155
Left and right.
>>54403134
Does it worry you that I write core software for a multi-million dollar company?
That said, I'm too tired to do it right, so feel free to put forward your own solution or to point out where I fucked up.
>>54403190
Thats not really an achievement. Im in the same position. Your code is still retarded
>>54403190
>I'm too tired
Lol
>>54402742
>>54403063
Now do it for a binary tree stored as an array. (No pointers involved)
>>54403135
I doubt that 90% of Google engineers use homebrew or OS X to begin with.
the guy is just bitter
>>54403167
Full retard. Nodes can point to nodes. Your tree generally isnt decided before running
>>54403307
Google, facebook and other big companies, like the one I work in, do use OS X primarily for obvious reasons. Mine doesnt use homebrew though, it is lacking
>>54403287
isn't that trivial?
>>54403287
>array binary trees
Nice meme
>>54402364
you sound enlightened
How is it possible to find right from left/vice versa in C++?
pic related, using structs. Classes give the same result.
>>54402669
Searching for any elements in O( log n ) time
>>54403599
nvm found it
this tree stuff is trivial
>>54403409
>>54403465
I think it's much harder than doing it the recursive/swap way that everybody here is posting.
But feel free to disprove me.
>>54404110
Still a meme
>>54402469
>recursion depth
>No no really, I'm telling you it's a real problem what if your tree has 2^20000 elements and you run out of stack? What then? HUH?!?
>studying comp sci
>tfw too retarded for it
jdimsa
>>54398794
Did you get the job?
>>54402503
>i went into more debt than you did for my babysitters
>>54402019
> palms are sweaty
> moms spaghetti
it's all ogre at interviews m8.
I could not implement fucking String class in Java because I was so tired and stressed out, lol.
But I did not really want the job, so it was ok.
>>54399356
pls rate my pseudo codeinvertNode(node) {
if(node == null)
return;
tmp = node.left;
node.left = node.right;
node.right = tmp;
invertNode(node.left);
invertNode(node.right);
}
>>54404904
bravo anon, you can work for google, but you can't make software that 90% of their engineers use.
>>54402536
If your candidate is twelve, maybe
>Or something else?
It's HR shit, it's not about your skills.
> invert a binary tree on a whiteboard
>> draw a binary tree
>> turn the whiteboard upside down
>> here, I inverted it.
>>54402791
CS student here. Inverting a binary tree is babby's first tree algorithm. Any second semester could do it. And trees, together with arrays, are the mother of all data structures.
The interviewer didn't want to know if the guy can invert a binary tree. Like you said, it's such a basic algo, you could simply google it on the job. But if you can't even invert a binary tree on the fly, you're obviously not comfortable with trees in general. So in your actual job, when you have to invent algorithms that suit Google's needs and that you can't find on the internet, you're dead weight. Not really the person you want to give a job to.
>>54403063
>magic numbers in your code
>not sizeof
Have fun refactoring
>>54402669
Programming AI in videogames.
>>54405032
>It's HR shit, it's not about your skills.
All HR does is look for a reason to decline your application. They are not competent to judge you and are paralysed by the fear of making a bad choice.
If you can be the guy who excels you'll probably be successful.
>import invertbinarytree
>>54402364
>can't do a VERY BASIC engineering principle
>"It's just wankery glad I didn't get a job at Google"
/g/ can't even average 2 ints in C
>>54398676
>calling Codemonkeys Engineers
>>54402295
>4chan emojis
I love the future
>>54402617
>but shallower depth does not imply complete protection from stack overflow
Are you worried that Pajeets are going to copy and paste code to pass your interview question?
>>54398676
Fuck this guy. Homebrew is a piece of shit. Pkgsrc ftw.
>>54402065
shouldn't it be:
invert (Node v l r) = Node v (invert r) (invert l)
?
>>54408158
yes
see >>54402287
>>54408284
whoops yeah hadn't read the whole thread when I saw this
>>54402364
Except they test your ability to think through a process and come up with a solution, IE: exactly what a programmer does, and allows the interviewer to see your thought process as you do it. For some reason the guy seems to think that having written a package manager that some people use should just get him a job without being able to demonstrate ability to even come up with a really simple algorithm.
>>54408293
when I wrote that*
>>54402541
The edges are named ("left" and "right")
>>54402692
Kofax?
>>54399578
>package manger for Macs 6 years ago
lol
>>54399578
If he doesn't know how to invert a tree, homebrew can't possibly be doing dependency resolution, can it?
