What does it mean to invert a binary tree? I'm not familiar with this operation on binary trees. Does it mean to swap parents with child nodes? Or to swap siblings?
I have a feeling that the question is not really about whiteboard coding or solving graph problems. This is a blatantly ambiguous task. Maybe it was meant to force the interviewee to demonstrate how they communicate to the interviewer that they needed more information about the problem before starting.
Pretending you understand or blindly assuming what the interviewer meant is more of a red flag to me than requiring a few rounds of clarification.
In my opinion, an ideal interviewee would communicate that they don't fully understand the requirements and possibly offer a brief set of possible interpretations. Once the interviewer has clarified, my ideal interviewee would restate the clarification to demonstrate competence and verify their new interpretation of the requirements before proceeding.
In this case, it means to reverse the binary tree, so that you get the largest item by iterating down the left branch to the bottom of the tree. You would do this by breadth-first scanning the tree, swapping the left and right pointers as you go.
Oddly enough, Google shows me interview questions where "inverting a binary tree" means something quite different — for example, flipping it upside down, and making the left leaf the root, the right leaf the left leaf and the root the right leaf.
If this was really about "reversing" the tree, as you mention, the question seems more likely to address how the candidate approaches the situation. Like, he should start by making sure they both agree on what the question actually means.
Once that's out of the way, it seems relatively easy to come up with a naive solution, without having memorised any algorithms. It seems more like a case of brainfreeze to me, which can be sort-of fixed with practice (which in turn many candidates refuse to do: the dreaded "If I have to cram for the interview, I don't want the job" statement.)
So maybe he really wasn't a good fit for Google, despite apparently being a rockstar developer. Hey, startups need rockstar devs too.
I was gonna say, who calls reversing a tree's ordering inverting?
> Oddly enough, Google shows me interview questions where "inverting a binary tree" means something quite different — for example, flipping it upside down, and making the left leaf the root, the right leaf the left leaf and the root the right leaf.
Whaaaaa? I can't find this, but it seems like such a weird operation. Got a link?
I don't even understand why you would ever want to do this. You could just invert the input or output at the beginning or end (depending on what the binary tree is used for) for super cheap. It's not uprising that no one has done this in practice, though it also seems trivial (visit each node once).
It's an interview programming question, so what matters is that it's a good interview programming question, not that it's something you would ever want to do. It's an important distinction. Generally you're looking to test candidates' abilities to come up with efficient algorithms to solve problems, which you're not going to get if you ask them to, say, tweak the order that fields are displayed on a web app form (even though that's a "real programming task").
Although I do see this as something you could possibly do "for real". Sometimes you'd rather change your existing data once than continue carrying forward what amounts to hacks, which is what inverting the output would amount to. Reversing a binary tree would be what you'd run in a tool to migrate all of your data over from the old format to the new format.
Yeah I checked Google as well, but swapping children seemed too easy for an interview question. I'm wondering if it means restructuring the tree so a different node is the root. Trees have the property that any node can be the root and it is still a tree. Not sure just wondering if anyone had more info.
It does seem way too easy. Maybe it was the first part in an increasingly difficult several part question, each part building off of the previous part, and the interviewee never made it past the first part in the time allotted?
