Why does Google care so much whether you can invert a binary tree or not?
Because they don't want worthless codemonkeys who can't program without stackoverflow open.
>>54365300
You don't need academical data structures to program faggot
>>54365318
Of course, a CRUD computer janitor like you doesn't need to implement data structures, so of course you don't need "academical" data structures ever.
because graph theory is so fucking important you shouldn't call yourself a programmer unless you can at the very least manipulate trees in your sleep
>>54365248
soooo, how do you invert a binary tree. isnt that pretty ambiguous, what leaf node should be the root?
>>54365248
Because their entire structure is based around binary trees, they have:
binary trees based rooms
binary trees cafeteria which serve many many flavors of binary tree based foods
binary tree toilets
Hell even their building layout is binary tree based, you NEED to know how to invert one if you want to have any hope of finding the front door at 5pm.
Ask binary moot if you dont believe me.
>>54365248
Because it shows you can take a problem and come up with a solution. I've never had to invert a binary tree before, but it wouldn't be that hard to come up with an algorithm. I've interviewed with Google before. It's all just them giving you problems and you coming up with algorithms and then implementing it.
Programming involves problem solving. They want to make sure you can actually use your brain and solve a problem, and not just copy and paste from stack overflow.
>>54365318
Binary trees and their variants are highly useful in software development. Sure, you could argue that most of that is done inside of libraries (ie std::map, TreeMap, etc using AVL/Red-black trees internally) but it is a good idea to know what they are and what their performance characteristics are. Plus sometimes you need an augmented data structure since you need more than just pure lookup/insertion, like for augmenting a tree so that nodes store how many items are less than it can be pretty useful.
>>54365984
You're probably given a rooted, oriented binary tree, judging by the picture. Since it's a directed tree you can assume that 8 is the root since it's the only one with 0 in-degree, and the rest can be inferred by its embedding within the picture. Your datastructure you're storing the tree in would obviously reflect this too with an ordering of siblings for each tree and by giving an explicit root.
>>54366136
I don't understand the question. Does it mean switch left and right leave nodes with each other?
So in OP's pic it'd be swapping (4,7) to be (7,4)
or does it mean switch every left/right nodes on each branch?
E.g.
(1,6) becomes (6,1)
(4,7) becomes (7,4)
>>54366374
I think it means to pick an arbitrary leaf node, make it the root node, and restructure the tree around that.
>>54366499
My arbitrary lead node is 6
So now (4,7) becomes (7,4)
Is that what is meant by the question?
>>54366538
a "leaf node" is a node with no children, so 4 or 7 or 13.
You pick one of those, make it the root, and then its child becomes 6, whose child becomes 3, whose child becomes 8.
I'm pretty sure you aren't supposed to swap around left and right children.
If my interpretation is right, then this problem is trivial with recursion, you don't even need any extra data structures.
>>54366374
I interpreted it as mirror. https://leetcode.com/problems/invert-binary-tree/ does as well.
However properly invert like reversing the directions would not result in a tree that could have a root as every leaf becomes a root.
>>54366374
>https://leetcode.com/articles/invert-binary-tree/#approach-1-recursive-accepted
They ask you ambiguous questions to see how work under pressure. That tells them more about YOU than asking some simple textbook question. Many HR people are also psycho/sociopaths and enjoy trolling applicants.
>>54365300
datastructures like trees are code monkey's job, nobody whos anybody deals with low level shit like that
They want to know that you got an education that exhaustively covered all the shit a CS graduate should know, and checking to see if you know this is a good way to do it.
You don't need to have graduated from university, but you need to have done all the contingent work.
This is like when a step-mother checks above the doorsill for dust. It's not that you need that clean; it's just to see if you're the sort of person to cut corners when you're doing something.
>>54365318
>binary trees
>"academical"
No. These are not brodal queues or fibonacci heaps. There is no excuse for not understanding basic trivial data structures like trees. You literally cannot be a decent programmer without it.
Why would you want to work for the machine?
It's an easy way to filter out idiots that can only glue together other people's libraries. Anyone with an elementary knowledge of computer science should know what a binary tree is, and given a reasonable description of what they mean by "invert" (I'd presume making a mirror image), should be able to come up with a solution. The test isn't "can you do the project you'll working on when we hire you?" It's "can you do basic problem solving, and possibly tackle a more difficult problem we might have 5 years sheen the road?"
>>54368902
5 years down the road*. Google, your autocorrect needs work. You need to have more difficult hitting criteria.
>>54368933
Hiring criteria. Fucking hell.
>>54367942
trees are the sort of thing that a self-taught programmer might never encounter/deeply understand (especially if he works with a high level language like Java, Python, etc... (I'm not super interested in arguing with someone about whether Java is high level), so this becomes one of the ways that companies can test to see if you've done all the work - even the annoying, tedious, not-immediately-apparent-why-it's-useful work.
Another perspective, which I don't necessarily subscribe to but in which I can see the merit, is that the question about inverting a binary tree is parallel to the interview process at universities as they emerged.
The consensus among historians is that universities (especially Ivy Leagues) adopted interview processes as minorities became competitive with whites in order to use fuzzy criteria that would emerge in an interview to justify admitting whites. Was the candidate well-dressed, articulate in his speech, etc... and of course it afforded interviewers the opportunity to say something vague like "not a good fit for the university" instead of "he's Asian (or Black or whatever)".
This became a sort of thin veil that allowed the university to say that they were utterly meritocratic, while still giving themselves the wiggle room to reject people that were different enough to make old white dudes uncomfortable.
The parallel I'm saying may reasonably exist is that Google et al. claim you can get into Google without a degree in CS, ostensibly holding up the mantle of meritocracy and equality of access and whatnot, but in truth you still need to know how to invert a binary tree. Is it necessarily useful to know that? No, not really. It's not even especially certain that you'll need to make use of binary trees in your code (or, for that matter, that you need to know it *going in* (i.e. can you not learn this later?)), but it's a great way to say you're meritocratic while still filtering out people that didn't graduate from universities.
>>54366593
Your explanation doesn't clear it up for me. Can you use notion like I did here: >>54366374
This makes more sense:
>>54366634
>>54366629
The question sounds ambiguous and not well-defined. Each person has their own "opinion" of what the question is asking, thus different "solutions".
If we can't agree upon what the question is asking then we can't agree to a proper solution.
>>54369248
>The question sounds ambiguous and not well-defined
Just like the vast majority of software design specifications. It's there to see if you'll clarify it instead of making assumptions. Good software engineers need to disambiguate shitty software specifications instead of just taking one (possibly not what the client wanted!) interpretation blindly.
>>54369329
True. Good point on pointing this out.
>>54365248
would going from the leaf nodes up and pushing the values onto the stack and then reversing the comparison conditions work out?
in terms of space complexity it's shit with the extra space on the stack. In terms of time it'd be O(n^2) as you have to push all the shit on the stack and then pop it all off for the new BST.
I assume recursion is better in terms of time complexity and probably space complexity.
>>54369500
>mfw I thought of the shittiest solution possible
may as well kill myself now
Does anyone know exactly how the original went down?
Was he given a picture of a binary tree and just asked how to explain how to invert it? Or did they show him code that makes a tree?
>>54369109
You don't need to "deeply understand" trees to answer this question. You honestly don't even need prior knowledge of what a binary tree is to answer a question like this.
It's a simple problem about a very simple, fundamental way to represent data. No matter what your background is, if you can't answer a question like this you absolutely will run into difficulty eventually solving real problems.
If a formal education in the field of abstract problem solving happens to give you a leg up on this sort of thing, so be it.
>>54369682
I agree with this absolutely. You don't need to know any complicated properties of trees or graph theory to answer the question. It's not like you're asked to know something specific of trees like that you can find the longest path in a tree in polynomial time where in graphs it's NP-hard, for example. You're not even required to know about basic shit you learn in the first day of class like the handshaking lemma.
>>54365248
probably because binary trees are babby shit and if you work at Google doing shit like that means you're not a dumbass
plus anyone who interviews at Google who has heard about homebrew will probably look it over anyway after hearing the story
>>54369682
whats the solution to this?
>>54369682
Having familiarity with binary trees is pretty much a requirement for this question given the situation.
You're right that someone could work through the concept of b-trees, and maybe they could do it under the pressure of an interview, but not under the time constraints of an interview.
The interviewer isn't going to sit there and watch you converge upon the intuition of b-trees if you've never learned about them before. If you don't know that topic area, you're simply not going to do well enough on this question (or not do well quickly enough) to convince them to move forward with you.
The best analogy I can come up with is a book report. Fundamentally there's nothing especially complex in a book you're reporting on. It's simply a matter of showing up prepared by having read the book. Even skimming the book in advance would be sufficient (for most people), but you need to do it before you walk through the doors.
>>54369109
If you don't know binary trees, you don't know CS
>>54365248
same people people used to ask you to solve fizzbuzz
>>54365318
exactly
>>54370824
FizzBuzz rekts me every time xD
>>54371152
hehe me too xD
who said grils can't kode ;)
>>54366634TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return NULL;
TreeNode* temp = root->left;
root->left = invertTree(root->right);
root->right = invertTree(temp);
return root;
}
Thoughts? Can I make it suck less?
>>54368902
Hi there!
You seem to have made a bit of a mistake in your post. Luckily, the users of 4chan are always willing to help you clear this problem right up! You appear to have used a tripcode when posting, but your identity has nothing at all to do with the conversation! Whoops! You should always remember to stop using your tripcode when the thread it was used for is gone, unless another one is started! Posting with a tripcode when it isn't necessary is poor form. You should always try to post anonymously, unless your identity is absolutely vital to the post that you're making!
Now, there's no need to thank me - I'm just doing my bit to help you get used to the anonymous image-board culture!
>>54369907
Pathetic analogy.
Assuming "invert" was well defined it is a trivial problem. Its designed to filter out mouth breathers who can only copy solutions.
>>54371630
Acting like a condescending faggot doesn't endow you with credibility or authority on anything. Chill with the dick-eater routine.
>>54365248
Because if you can't do that, you will fuck up the minute you face a remotely hard problem.
People complain about Google's hiring, but it works. Google is probably the most competent large corporation today.
>>54367840
when is programming not code monkeying?
>>54366634
how is this still a binary tree if the values to the left are larger? I thought binary trees forced you to keep values in order? Sorry If I sound stupid, I really dont know
>>54367878
WHY WOULD YOU WANT A STEP-MOTHER LIKE THAT
WHY WOULD YOU WORK FOR A COMPANY THAT MAKES YOU JUMP THROUGH HOOPS LIKE A TRAINED POODLE
HUXLEY WAS RIGHT
>mfw I have to relearn recursion every time since I never use it in the real world
>>54372595
For one, you're thinking of binary search trees, and two, it's still a binary search tree. Reversing it simply turns your <(=) operator into a >(=) operator, which still has the necessary properties to have a binary search tree work, you just change the ordering function.
A binary tree simply has the requirement that deg+(v) <= 2 for all v in V(T) and the existance of a unique root r such that deg-(r) = 0. Beyond that all it needs is for the graph to be a tree and for edges to be directed. There's no requirement on the value (or even existence) of labels (keys) on the vertices, or even any kind of orientation of the tree (since if you don't care about the embedding/rotation system of the tree, the algorithm in the OP's problem doesn't change the tree, it simply changes the embedding of it in the plane.)
>>54372817
I really, really hope this is bait.
>>54372851
you never use recursion since it always performs worse
>>54372896
Depending on how your recursion is written, the compiler can optimize it out into an iterative processing, and secondly, recursive code can often be much more readable than iterative code, which is going to matter more for 99% of applications as the penalty for recursion is likely going to be negligible assuming you're using recursion for something that it makes sense for (ie recursively subdividing something, so it's getting called an O(logn) amount of depth, rather than doing something silly and doing it O(nl) times).
And either way, if you're writing it iteratively using a stack you should *definitely* know hot to write it recursively too.
