The practice of asking brainteasers in interviews is a common punching bagfor pundits. Last summer, Hacker News blew up over the following exceptionallyinsightful tweet on the topic.

• Homebrew Google Interview Answers
• Homebrew Google Interview

This literally happened to Max Howell, the guy behind homebrew. 'Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.' I argue that if an interview question asks you to implement parseInt(String foo), it's your responsibility to handle inputs that aren't a. Hi, I’m Max Howell, so maybe I shouldn’t answer this. Hi, I’m Max Howell, I’ve spent the last two years not answering this, and many questions like it. Maybe I shouldn’t answer this. So, what's the logic? Clearly I wrote something worthy of Google.

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

First of all, don't get me wrong,I think homebrew is an awful piece of software that should never be used by anyone.Homebrew is like herpes: you pay for your moment of instantgratification with a lifetime of burning pain.

That being said, this tweet struck close to home for me because inverting abinary tree is a small part of an interview question that I've asked hundredsof interns, junior engineers, and even a former Goldman Sachs VP over the lastseveral years. I'm retiring this question from my pool of brainteasers, becauseI've asked it far too many times already. However, I think it's a good exampleof how asking a neat algorithms question can tell you a lot about what kind ofwork somebody will produce.

Intuitively, it's easy to tell whether a binary tree is symmetric. Here'sa few small trees courtesy of the fine people atWolfram MathWorld. The trees at row 1 column 1,row 2 column 3, row 4 column 5, row 5 column 1, and row 5 column 7 aresymmetric, the rest aren't.

The task is to write a function, that, given a binary tree, returns trueif it is symmetric. I always leave the choice of language up to the interviewee,because a good solution should be easy to understand in most languages.

Here's the first reason why this question is so good: a skilledprogrammer can map their intuition to code. You can tellat a glance whether a binary tree is symmetric, but beginners will oftenstruggle with a question like this because they approach thisproblem from a visual/intuitive angle rather than the logical angle.

The logical angle is 'what does it mean for a tree to be symmetric?' Inother words, a novice programmer may attempt to map their visual process fordetermining symmetry. The end result is a tangled mess of code. Most goodprogrammers will instead think about how to define symmetry using a simplerecurrence relationship. In other words, as Linus Torvalds once said:

'Bad programmers worry about the code. Good programmers worry about data structures and their relationships.'

The definition typically involves two steps. The first step is to realizethat a tree is symmetric if its left and right subtrees are symmetric.There's two definitions that most successful solutions end up with for whatit means for two trees to be symmetric:

• The purely recursive definition: two binary trees t1 and t2 are symmetric if and only if t1.left and t2.rightare symmetric, and t1.right and t2.left are symmetric.
• The two-step definition: two binary trees t1 and t2 are symmetric ifthe reverse of t2 is equal to t1.

Homebrew Google Interview Answers

The first definition leads to the most concise solution:

The second definition requires reversing a binary tree and then comparingif two binary trees are equal. This is the solution that requires reversinga binary tree on the whiteboard, and the one that most intern candidates endup using to solve the problem in 20 minutes.

Trees are the single most important data structure in computer science.Just about everything you do in your programming career will be relatedto trees. For example, let's take a look at your average full stackweb developer. They store their data in a database,which is just a collection of B-trees. They typically think of the data they work with as JSON objects,Python dicts, or Ruby hashes, which are all trees. On the frontend, theytake their JSON objects and render them to the DOM, which is also a tree.Maybe they even use React components, which are organized in a tree.

Can you be a good engineer without knowing anything about trees? Anappropriate analogy would be, can you be a good doctor without knowinganything about what a heart is? Despite that the heart ispivotal to how the human body works, in theory you could become aleading knee surgeon without knowing anything about it.In practice, I'm sure the Dr. Peter Wehlings of the world have forgotten more about the heart than I will ever learnin my lifetime. After all, how do you come up with a medical procedure basedon transfusing an extract of the patient's blood into their knee to reducearthritis without knowing anything about the circulatory system?

Homebrew Google Interview

Skill in software engineering, like skill in any subject, is not cultivatedby limiting yourself to a narrow set of knowledge and challenges. The kindof engineer that I want to work with is someone who takes the initiative totry out the unknown and take on new challenges, not someone who sits aroundwhining 'nobody told me to!'And just like odds are you aren't a leading knee surgeon if you don't knowwhat a heart is, you're probably not the kind of engineer I'd like on my team.