Hacker News new | past | comments | ask | show | jobs | submit login

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."


Something similarly hilarious happened to me. I sold an app I built to a company in the 6 figures. I was the sole developer on the app. The sale had already gone through and they (obviously) needed someone to help maintain the app. Rather than just offer me a job, they insisted I go in for a technical interview with their engineering manager -- after buying the app I had built 100% myself. That and a few other clues scared me away and I ended up working for a competitor which went on to become much much more successful.

It was clear from the very beginning that the decision was more on the "culture fit" side than the knowledge. His attitude shows this and then is confirmed after he quit Apple (who hired him no long after Google's rejection) and he — himself — stated in a message via Twitter that Apple's work environment was not for him.

Reversing a binary tree is not that difficult, and a good interviewer (specially the ones at Google) already know this, but if the interviewee shows an angry face out of frustration and doesn't ask for help or doesn't communicates his inability to proceed with such task, then what does the interviewer says? Rejection!

Interviewers also evaluate your communication skills.

It's horse shit questions like that in tech interviews that caused me to start my own company and leave corporate America. A whiteboard is just a glorified chalkboard, and I got sick of being asked to prove I understood how to use and manipulate one of the most complex systems ever invented by man by basically rubbing a soft rock against a hard rock. I figured if a company couldn't do a better job of interviewing me than to ask ridiculous puzzle/whiteboard questions that have nothing to do with their business, then I probably didn't want to work there anyway.

Throughout my career, I have valued companies who can ascertain my skills by looking at where I've worked, code I've worked on, and the conversation we've had. Those companies seem equally adroit at determining the market and making good business decisions. Nearly every place I've worked who employs puzzle questions has either failed to maintain their market position or gone out of business. Sure, there are exceptions, but not many.

In my opinion, puzzle questions show a lack of knowledge and insight, and before starting my own company, I made it a habit to walk out of any interview that employed them.

Ah yes, people do bring this case up. However, they don't usually remember that Homebrew at that point was a poor and incomplete reimplementation of other package managers, used to break installed software on updates, and the fact that the very team that was maintaining Homebrew was not competent enough to either manage SSL certificate for their website properly or at least admit that it was a bug.

The sole fact that people use your software doesn't mean that you're competent, similarly to your inability to work with data structures on a whiteboard not meaning that you're incompetent. Somehow people only remember about the latter part for Homebrew.

"The sole fact that people use your software doesn't mean that you're competent"

It means something else, which may actually be more valuable than being a "competent software engineer" in the eyes of a specific company.

Millions of people have used bad or buggy products for decades, but that doesn't mean that you want to hire the engineers who built them, no more then you want to hire lottery winners (For being lucky!).

Authors of widely successful but "buggy" software are now lottery winners? My point was that these "unqualified" engineers clearly have something that separates themselves from even "genius" engineers. Hustle (to name one trait) matters, sometimes more than qualification and academic credentials.

No, but if being an author of successful software makes you a good employee (Because surely, that success is wholly transitive), then being a lottery winner would too. (After all, you were lucky - and it's good to hire lucky people.)

Put another way - does being a security engineer for Equifax make you an obvious hire at Google? I mean, every American Google employee has used Equifax's credit report systems, or used a bank that uses Equifax's credit report systems - clearly, said security engineer knows what he's doing.

Equifax's ubiquitousness is not a direct result or byproduct of the engineer's work.

And neither is the ubiquity of any one particular software product. There are always factors beyond 'Was Bob a good engineer.' 95% of businesses exclusively used Windows in the early 2000s, but that doesn't mean that you should blindly hire anyone who worked on it.

The author of that blog post wrote Homebrew. Thousands of engineers use it on a daily basis. That's great. I use thousands of pieces of software, worked on by hundreds of thousands of people, on a daily basis. That doesn't mean I should skip the interview process, and hire all of them. Some of those people are rock stars. Some... Are awful developers.

Was it ever figured out what "invert a binary tree" means? At least I had never heard this term used prior to this incident. This has me slightly worried about this particular example somehow, and I'm not quite sure what to make of it...

            2                             2        
           / \                           / \       
          /   \                         /   \      
         /     \                       /     \     
        1       3                     3       1    
       / \     / \                   / \     / \   
      0   7   9   1    reverse >>>  1   9   7   0  
     /   / \     / \               / \     / \   \ 
    2   1   0   8   8             8   8   0   1   2
           /                               \       
          7                                 7

So several people replied with this same thing, which I have heard before being suggested. However, as I recall it at the time, if you tried to search for "invert binary tree" this term basically did not exist on the internet. I just tried searching on google with time set between 2000 and end of 2014 which seems to give similar results.

I guess I did not spell it out in my original post, but I always felt it might have been an intentional nonsense question intended to gauge how he would react to someone talking nonsense, or something like that, and not necessarily related to technical things. A sibling post of my original to suggest this was the case, without the weird detour through the term "invert binary tree".

Edit: Of course an alternative explanation is that the interview used another term and he then used the term "invert" on twitter.

Idk, this example at least has to me always felt like people who complain about not passing the driver's test coz they did some minor error and then forgetting to mention that they drove past a stop sign.

I'm not 100% sure about the inverting part, but at Google nobody ever told me to ,,fuck off'' and nobody would tolerate that language, and that person would get a serious talk from his/her manager, maybe even laid off instantly, especially if it's written.

I assumed it as taking a binary tree (L|R) and reproducing a tree that's (R|L). And if it is that, then writing out the algorithm on a back of a napkin just now was a pretty thought provoking exercise :)

It means to swap the left and right arm of each node. So you effectively "mirror" the tree.

Yeah, it's relatively simple once you come to that realization:

    TreeNode* invertTree(TreeNode* root) {
      if (root == NULL) {
        return NULL;
      TreeNode* tmp = invertTree(root->left);
      root->left = invertTree(root->right);
      root->right = tmp;
      return root;
It sounds a lot more complicated than it is.

Until I throw this test case at you:

    TreeNode testRoot = new TreeNode();
    testRoot.left = testRoot;

    invertTree(root); // Stack overflow.
But that's not a tree, that's a cyclic graph, you may shout. That's true, but you still need to sanity-check your inputs.

That ought to be done in a separate validation step, and/or the tree object should enforce its invariants.

(I shouldn’t be arguing interview problems on HN, but I’ve had a few beers.)

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 properly formatted integer gracefully.

Or at least to point out to the interviewer that your solution fails to handle unexpected input, and ask if they want you to add input validation logic, or if they are satisfied with the answer.

Sure, but this assumes that foo is a valid String — just formatted incorrectly for use with an int. If we can't assume that TreeNode constitutes a valid (cycle-free) tree, we essentially have to embed a full cycle-checker in our otherwise simple inversion function. I would argue that goes against the intent of the question.

Invert a binary tree as in heapify it maybe because inserting occurs at the leaf not root? Is that what it means? Does it simply mean changing the insert criteria so that a<b is now b<a?

It's not about knowing how to do it, it's about watching the thought process of how you go about getting to the solution and how you communicate ideas and problems.

It's really great that he made a widely used piece of software, and he's a prolific developer for it. But if he can't explain the process to how he gets to an answer, it's hard to know how he'll work with other developers on problems.

That sucks.

Also, I didn't realize Jonathan Blow was such an ass.

I can agree with Jonathan Blow's responses in so far that you should be able to invert a binary tree in an interview if that's the sort of knowledge you need on-call on the job and there's somehow no room for rustiness because it's some sort of high stress environment that needs immediate results (btw that doesn't describe jobs at Google).

But then he reveals that he's completely full of himself when he suggests that "sorry, you're not a good programmer then."

For writing non-trivial software basic knowledge of data structures is needed. Especially with performance requirements like Google has. In some areas you get away without such knowledge but if you bild a dependency management tool like brew and don't know what a tree is, this is suspicious.

In the interviews I did with Google, Facebook and others (mostly for fun, not profit) if I didn't know an algoithm from top of my head I typically could talk to the interview and discuss th problem and they'd point me in the direction. Sometimes those interviews are less about being able to remember the thing, but the thought process to get there.

Aside from that: Google clearly optimizes on not hiring too many bad people, but rather leave a few good candidates behind.

    > if you build a dependency management tool like brew
    > and don't know what a tree is, this is suspicious
They didn't say that they didn't know what a tree is. They said they couldn't invert a binary tree in the interview.

It's a stretch to start suggesting that someone doesn't know their basic data structures because they failed some riddleware on the spot.

You can say that they aren't what google was looking for, but my problem comes when someone tries to dismiss another as a bad developer because of that.

Well, inverting is a trivial operation, pseudo-implementation: swap(left, right); recurse(left); recurse(right);

If one doesn't know what is meant one can talk to the interviewer and get a hint about what is meant. It can be that the interviewer is bad and misleading, but usually they have some specific training, this seems unlikely as the candidate didn't complain about the interviewer but admitted he had no clue.

The follow-up question would probably be the question about the complexity, that is also trivial f you know fundamentals of big O notation, as one has to walk over each node.

It's hard to find a more trivial algorithms question. Algorithms are fundamental knowledge for programmers (other than script kiddies)

Isn't the typical practice amongst software engineers, when you don't know something off the top of your head, to cut and paste from StackOverflow? Why do we need day-long job interviews and whiteboards to ascertain that?

The name "Jonathan Blow" and the words "full of himself" pretty much go hand-in-hand.

Haha, I've been a programmer for most of my life and I don't know what "inverting" a binary tree even means!

            2                             2        
           / \                           / \       
          /   \                         /   \      
         /     \                       /     \     
        1       3                     3       1    
       / \     / \                   / \     / \   
      0   7   9   1    reverse >>>  1   9   7   0  
     /   / \     / \               / \     / \   \ 
    2   1   0   8   8             8   8   0   1   2
           /                               \       
          7                                 7

Ah, I would personally call that "flipping", I kind-of imagined that "inverting" would mean maybe taking a node and putting in the root of the tree or something similar...

Why would you want to reverse/inverse a binary tree?

It's an easy way to check if you can think recursively/are familiar with a btree.

That’s reversing a binary tree.

    This problem was inspired by this original tweet by Max Howell
There are many definitions of invert. This is relying on one definition that is jargon, and not widely agreed upon jargon at that.

For a two or more dimensional “object”. Invert means to reorient the top and the bottom, while reverse swaps the left and the right.

The two only might mean the same thing with one dimensional data structures. For instance inverting a line of text might (ambiguously) mean reversing it. Or drawing it upside down. Or upside down and backward. But at least you would expect a clarification.

That was fun, thanks! I remember reading that tweet a while ago, and "inverting a binary tree" sounded very complicated, but it's really just one line of code.

I'd be very careful now, you might not be a REAL programmer.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact