> If you can't do it, you probably don't understand recursion

No, I can't do it (don't even understand the question) but I certainly understand what recursion is, and can solve problems and make things work far more reliably than many of the more academic programmers I have worked with.

Well one of the points of an interview is to see how (or if) the person goes about understanding problems the context of a given problem. So presumably it's unclear to inverse a binary tree to you - that's why you ask clarifying questions. Perhaps you draw what you think it means and ask if that's correct. What will be considered the root if it's just a matter of reversing the direction of the pointers? Stuff like that. Google isn't dumb, and I'd be willing to bet that it's questions like those that are just as important than coding the solution (since it won't be that hard once you clarify the problem).

Here's an example to think about: You're asked to write a method that, given a word and a book, will return the number of times that word appears in the book. A logical way to continue would be to (after clarifying what a book is represented as and things like that) write a simple method that iterates over the book and counts how many occurrences of the words there are, and returns that. Is that a good answer? No, because you failed to ask questions like whether the method might be called many times for the same book (in which case it'd be better to build a map of words to occurrences). Or maybe the interviewer would say that it'd only be called once per book, in which your solution is perfect. The bottom line is that coding isn't as important as the way you approach the problem to the interviewer.

The best analogy I've heard for this: If you wanted to judge whether a person was a good chess or card player by seeing just a couple moves or hands - you wouldn't just look at the couple moves/hands played - it'd give you very little information. But if you asked the player to explain their whole thought process for the moves/hands, you'd get a much better indication of how good or mediocre that player was.

I believe "invert" here means to flip the left-right direction. A better word for it would be "mirror."

I'm a CS major, and I'm not even sure exactly what they're expecting. I mean a binary tree is just nodes with no more than 2 children. A linked list is a binary tree. Do they want a search tree? Do they want a self balancing tree?

Can you confirm that actually inverting a BT or solving other similarly probs would have been part of his future job at Google?

If so, they were consistent in disqualifying him in spite of his awesome track record, fame or "street cred" but if not, I can't really justify or defend this type of ceremonial or bureaucratic gotcha interview questions as they are just useless and can be abused by the interviewer to reject applicants they dislike for any reason or whim they might have at that moment.

I have no idea what the job was.

But my point is this is not a bureaucratic gotcha question. If you can't do this task, you don't really know how to program well. Sorry but that's just how it is. It's like failing FizzBuzz.

There is this culture of crappy software that has happened lately, especially in the Web world, and it is really quite lamentable. I believe that a very large positive impact would be made on the world -- due to the extreme prevalence of software these days -- if more people would take seriously the idea of software creation as a craft with a very high skill ceiling, and work diligently to improve their understanding and their skills.

Note that "invert" in this context is fairly ambiguous. I suspect the interviewer meant reverse, which is, I agree, utterly trivial.

I, and apparently many others in this thread, spent some time trying to ferret out an answer to what it would mean to invert a binary tree: at first thought it would imply a collection of nodes all pointing at their parents, which seems not very useful (and would require more than 10 lines of code to whiteboard reasonably).

Much of the discussion is about whether or not the problem was described in sufficient detail or not.

The question is definitely not described in sufficient detail. That's usually on purpose. The interviewer WANTS the candidate to realize that too and ask the questions necessary to actually understand what they are trying to solve. It's very analogous to nailing down specifications on a new feature or something like that.

I've never inverted a binary tree (I'm not familiar with the concept). You claim that makes me a bad programmer. Be careful there: just because somebody hasn't been exposed to something doesn't mean they aren't smart enough to figure it out. Fizz buzz is also flawed in this way: it doesn't test if you know how to program, it merely tests "have you been exposed to the modulo operator yet".

FizzBuzz is not about the modulo operator. You can write it pretty easily without it, in several different ways. If you can't figure out how pretty quickly, you're not a good programmer. Sorry.

It is even kind of reasonable to just substitute a call to some black-box is_divisible_by() if you can't figure out how to do that test ...

No one is claiming that makes you a bad programmer. However, if you got this as a problem to solve and your response is "I don't know" and you stop there, then you are a bad programmer. As I've commented elsewhere, the interviewers want you to ask clarifying questions. Those are often just as important as the code itself. Once you've nailed down the definition of inverting a binary tree (maybe it's just switching left and right node pointers), coding will be trivial. It's much like getting sufficient detail on a feature request before starting to work on the feature.