edit: really good english skills
edit: really good english skills
Inverting a binary tree is pretty easy. It is not quite as trivial as FizzBuzz, but it is something any programmer should be able to do. If you can't do it, you probably don't understand recursion, which is a very basic programming concept.
This isn't one of those much-maligned trick interview questions. This is exactly the kind of problem one may have to solve when writing real software, and though you may never have to do this specific thing, it is very related to a lot of other things you might do.
I run a small software company and I very likely would not hire a programmer who was not able to step through this problem and express a pseudocode solution on a whiteboard.
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.
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.
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 ...
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.
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.
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.