5 ms·

Max Howell's story really surprises me. You would figure that someone would've internally fast tracked a developer like him.

hinkley 8y ago
That one is famous. We had a quite lively discussion about it here shortly after the event. Edit: to this day I have no fucking idea what “inverting a binary tree” means, other than the interviewer was too proud to admit they made a mistake. Trees have two dimensions and “invert” is the one you can’t change.
- gnulinux 8y ago
  It just means making 1 - 2 -- 4 -- 5 - 3 --7 into 7 - 3 -- 1 [union] 5 - 2 -- 1 [union] 4 - 2 -- 1 as one graph. I must say I'm surprised someone can't write this given enough time and proudly claim "they didn't hire me because I couldn't do this". Seems like CS 101 hw.
  - ghaff 8y ago
    As he says, he wasn't a CS major. I can totally relate. I had a pretty popular DOS shareware back in the day (along with some other things). But I wasn't a CS major and would not have been able to answer most algorithmic CS questions unless I had specifically studied them for the purpose of an interview.
    - gnulinux 8y ago
      Fine, but don't you think companies should have some filter to choose candidates? In my company I interview often, and most candidates don't know how to code. Asking CS hw questions is a signal that predicts if they can code or not. If you're not a CS major it's ok but in general if you can't figure this question in 15 mins I don't want you to push code to my codebase. Some level of competence is ok. And I don't even work in a FAANG this is a random no name startup in Boston.
      - hinkley 8y ago
        There's one particular category of question that I've started building up a question set in, in part because the last few coworkers who weren't nearly as useful as you would hope all struggled with it: Data transformation. Most of us are at least partly in the business of data transformation. Few of us should be implementing trees (you want coworkers who are informed consumers of data structures, not people who think reimplementing solved problems at work is a reasonable or even sane thing to do). The simplest one I have is this: Hand them a data structure containing a list of lists, have them generate a list of the grandchildren ordered by some property of the grandchild. Like take a list of cars or computers grouped by make and model and give me all of the models sorted by price, or by popularity. If that's too simple, filter by another criteria and do a little data cleanup. I've seen people drop elements, get the order wrong, scope variables too broadly and confuse themselves into grabbing data from a previous iteration, or forget to grab it entirely. And this is exactly the sort of thing that puts your team on the spot for having dumb bugs in production. Not inverting binary trees, or fizzbuzz.
  - hinkley 8y ago
    Reversing a tree (max element on the left) is absolutely CS homework (though probably 201). I'm sure I had to do that at least once or twice. But you can also avoid that most of the time by writing a second in-order traversal algorithm that runs from right to left. But why would I need a data structure where I have the elements by the leaves instead of the roots? Make the nodes doubly linked (parent element) and you get the same effect without all the grandstanding.
- deleted 8y ago
  [deleted]
- gaius 8y ago
  It means to reverse it left-to-right, like a mirror. You will never have to implement this yourself for real.
  - monocasa 8y ago
    You won't because it's a toy problem, not because it something only greybeards did in libraries written decades ago. Asking someone to describe the simplest possible transformations on one of the simplest data structures isn't a stretch, and this is coming from someone without a CS degree. EDIT: And that's not to say Google doesn't have a screwed up hiring system. I know someone who implemented a dynamic programming problem correctly, with the appropriate big O complexity, but was rejected because the constant time factor was slightly higher than what the interviewer was looking for. That's a BS decision; Max Howell's was not.
  - hinkley 8y ago
    There's another term for reversing a tree: reversing a tree. 'Reverse' is switching the orientation left to right or front to back. Top to bottom is 'inverting' (except in graph theory where inverting means something entirely... weird). > other than the interviewer was too proud to admit they made a mistake.
daveFNbuck 8y ago
He wrote a bit more about it on Quora [1]. He still feels he should have been hired, but I think the Quora answer makes it pretty clear that he's not what Google is looking for in software engineers. [1] https://www.quora.com/Whats-the-logic-behind-Google-rejecting-Max-Howell-the-author-of-Homebrew-for-not-being-able-to-invert-a-binary-tree/answer/Max-Howell https://www.quora.com/Whats-the-logic-behind-Google-rejectin...

hinkley 8y ago

That one is famous. We had a quite lively discussion about it here shortly after the event. Edit: to this day I have no fucking idea what “inverting a binary tree” means, other than the interviewer was too proud to admit they made a mistake. Trees have two dimensions and “invert” is the one you can’t change.

gnulinux 8y ago
It just means making 1 - 2 -- 4 -- 5 - 3 --7 into 7 - 3 -- 1 [union] 5 - 2 -- 1 [union] 4 - 2 -- 1 as one graph. I must say I'm surprised someone can't write this given enough time and proudly claim "they didn't hire me because I couldn't do this". Seems like CS 101 hw.
- ghaff 8y ago
  As he says, he wasn't a CS major. I can totally relate. I had a pretty popular DOS shareware back in the day (along with some other things). But I wasn't a CS major and would not have been able to answer most algorithmic CS questions unless I had specifically studied them for the purpose of an interview.
  - gnulinux 8y ago
    Fine, but don't you think companies should have some filter to choose candidates? In my company I interview often, and most candidates don't know how to code. Asking CS hw questions is a signal that predicts if they can code or not. If you're not a CS major it's ok but in general if you can't figure this question in 15 mins I don't want you to push code to my codebase. Some level of competence is ok. And I don't even work in a FAANG this is a random no name startup in Boston.
    - hinkley 8y ago
      There's one particular category of question that I've started building up a question set in, in part because the last few coworkers who weren't nearly as useful as you would hope all struggled with it: Data transformation. Most of us are at least partly in the business of data transformation. Few of us should be implementing trees (you want coworkers who are informed consumers of data structures, not people who think reimplementing solved problems at work is a reasonable or even sane thing to do). The simplest one I have is this: Hand them a data structure containing a list of lists, have them generate a list of the grandchildren ordered by some property of the grandchild. Like take a list of cars or computers grouped by make and model and give me all of the models sorted by price, or by popularity. If that's too simple, filter by another criteria and do a little data cleanup. I've seen people drop elements, get the order wrong, scope variables too broadly and confuse themselves into grabbing data from a previous iteration, or forget to grab it entirely. And this is exactly the sort of thing that puts your team on the spot for having dumb bugs in production. Not inverting binary trees, or fizzbuzz.
- hinkley 8y ago
  Reversing a tree (max element on the left) is absolutely CS homework (though probably 201). I'm sure I had to do that at least once or twice. But you can also avoid that most of the time by writing a second in-order traversal algorithm that runs from right to left. But why would I need a data structure where I have the elements by the leaves instead of the roots? Make the nodes doubly linked (parent element) and you get the same effect without all the grandstanding.
deleted 8y ago
[deleted]
gaius 8y ago
It means to reverse it left-to-right, like a mirror. You will never have to implement this yourself for real.
- monocasa 8y ago
  You won't because it's a toy problem, not because it something only greybeards did in libraries written decades ago. Asking someone to describe the simplest possible transformations on one of the simplest data structures isn't a stretch, and this is coming from someone without a CS degree. EDIT: And that's not to say Google doesn't have a screwed up hiring system. I know someone who implemented a dynamic programming problem correctly, with the appropriate big O complexity, but was rejected because the constant time factor was slightly higher than what the interviewer was looking for. That's a BS decision; Max Howell's was not.
- hinkley 8y ago
  There's another term for reversing a tree: reversing a tree. 'Reverse' is switching the orientation left to right or front to back. Top to bottom is 'inverting' (except in graph theory where inverting means something entirely... weird). > other than the interviewer was too proud to admit they made a mistake.

daveFNbuck 8y ago

He wrote a bit more about it on Quora [1]. He still feels he should have been hired, but I think the Quora answer makes it pretty clear that he's not what Google is looking for in software engineers. [1] https://www.quora.com/Whats-the-logic-behind-Google-rejecting-Max-Howell-the-author-of-Homebrew-for-not-being-able-to-invert-a-binary-tree/answer/Max-Howell https://www.quora.com/Whats-the-logic-behind-Google-rejectin...