5 ms·

The test isn't so much about the ability to invert a binary tree (for example), but the ability to problem solve complicated problems where the obvious solution

The test isn't so much about the ability to invert a binary tree (for example), but the ability to problem solve complicated problems where the obvious solution is probably not the best one. In interviewing, it is hard to produce real world problems that don't require a huge amount of context and details of some obscure software stack, so we go with abstract problems which are kind of irrelevant to real work, but the problem solving approaches you need to take are very relevant. Thinking about the requirements, thinking at the right level of abstraction, defensive coding, to name just a few. Communication and whatnot are all on top of that, and yes, absolutely do need to be evaluated. I'll also note that MAANG companies have extremely sophisticated software stacks (and multiple ones for each company!) that were built by people who were hired using that method. If it is wrong, it's working pretty darn well. There are many things I would change if I could, but we do have an existence proof that, in the aggregate at least, the people this interviewing method selects for can build amazing software stacks.

disgruntledphd2 5y ago
If we're going to use Meta for the acronym, then for God's sake can we call them MANGA? More generally, the absurd success of most of Big Tech has not come from better technology but extremely high margins facilitated by software. Apart from the core ranking/ads problem that M and G solve, most of it doesn't need to be that complicated. I would venture that lots of the cool technology stuff is designed to keep engineers happy so that the money train continues. Certainly the one I was at built a lot of cool stuff, but there was so much reinventing of the wheel that I suspect that the core business and products could have been served by a much much smaller engineering org.
- osigurdson 5y ago
  According to Jim Cramer (who came up with the FAANG acronym), we should now be using MAMAA (Meta, Apple, Microsoft, Amazon and Alphabet). https://finance.yahoo.com/news/not-faang-mamaa-jim-cramer-163000145.html https://finance.yahoo.com/news/not-faang-mamaa-jim-cramer-16...
  - disgruntledphd2 5y ago
    I kinda agree with that, but MANGA is such a great acronym that I'd like to keep it.
jcrites 5y ago
This actually seems like a pretty simple problem, to be honest, where the obvious solution is the best one. Inverting a binary tree means reversing the order of the sequence of elements that it represents. Thus inverting a binary tree is simply swapping the left and right edge of every node recursively down the tree. You could do this with a recursive algorithm by modifying the tree in-place or by constructing a new tree. I don’t see any obvious candidate optimizations other than the fact that it’s straightforward to do in place (e.g. using std::swap in C++, or mem::swap in Rust). However I don’t think this is as good of an interviewing question as other potential questions. See my other comment in the thread for one that I think is better. The reason is that programming tasks like this are pretty uncommon to encounter as a professional software engineer. Better questions (IMO) are tasks that professional software engineers are likely to encounter while doing their job at the company — or representations of them, while testing knowledge of A&DS as necessary. Even if a company does particularly a lot of work with binary trees, then that company would be likely to have number of such A&DS already implemented. If you’re working at Google then I can’t imagine that you would need to build a binary tree data structure or an algorithm for inverting them; undoubtedly these implementations already exist within their standard libraries. Personally, I can’t immediately ever recall encountering a binary tree in business logic while working as a professional engineer. I wouldn’t expect to unless I was building some thing like a collections library or a specialized solution to a large scale problem like implementing a novel data store of some kind. And if I was doing that kind of work I’d break out references (e.g. Knuth as a starting point, and any relevant recent research), and review open source software for comparison or as a candidate for directly solving the problem (SQLite, MySQL/InnoDB, LevelDB & BDB, Apache Commons libraries, etc.)
- WalterBright 5y ago
  > The reason is that programming tasks like this are pretty uncommon to encounter as a professional software engineer. I'm not so sure. One aspect is even recognizing that the task can be done by a known algorithm. Not knowing the algorithms may make one mistakenly believe that the opportunity to apply algorithms never came up. > I can’t imagine that you would need to build a binary tree data structure or an algorithm for inverting them I'm sorry, they are so trivial it takes more work to understand the documentation on the library one than it takes to just do it. Though personally, if a candidate flunked the binary tree question, but had a very successful project, I'd take a closer look before rejecting him. For one thing, I'd want to have a look at the project's source code. I'd also want to verify he'd actually written the code for that project.
908B64B197 5y ago
> which are kind of irrelevant to real work, but the problem solving approaches you need to take are very relevant It's also a common vocabulary shared across engineers, no matter their seniority or where they graduated from. And knowledge of algo and data structures demonstrate someone could learn it in the first place. Especially for junior hires, it's an excellent predictor of success.
vanusa 5y ago
But the ability to problem solve complicated problems where the obvious solution is probably not the best one. Problems like designing "the most popular package manager on macOS", for example? I think what the author finds strange is that not only do many people still believe that LC (or whiteboarding) are effective proxies for general problem solving ability -- they seem to tacitly believe they are better measures than demonstrated, real-world problem solving achievements. Even problems that are significantly more multifaceted and nuanced. If it is wrong, it's working pretty darn well [for MANGA]. The problem is, these tests (and extensive rounds of them, with onerous time limits) are used by companies that (inasmuch as they would like to believe otherwise) definitely are not MANGA and certainly are not offering MANGA levels of compensation.
- TulliusCicero 5y ago
  > Problems like designing "the most popular package manager on macOS", for example? Yes, those fall through the gaps, but people with that kind of extremely strong, publicly viewable history are much more the exception than the norm.
  - vanusa 5y ago
    Does have to be not just "strong" -- but "extremely strong" evidence? Not to split hairs - but it does seem to be a peculiar choice of words, there. I just don't see why the DSA filter has come to be considered so golden that one's ability to not just demonstrate some baseline capacity for this skillset, but to positively master a sequence of concocted performative rituals around it (specifically: reciting these algorithms in front of groups of strangers at a whiteboard; "talking" large blocks of code to someone over a phone; or doing online tests under completely unrealistic time pressure) -- that, in some corners at least, has come to categorically dominate all other selection criteria in the hiring process. (Actually I do see why -- but it all comes down to factors not related to the intrinsic importance of these skills, or to whether the candidate can effectively do the job).
    - TulliusCicero 5y ago

disgruntledphd2 5y ago

If we're going to use Meta for the acronym, then for God's sake can we call them MANGA? More generally, the absurd success of most of Big Tech has not come from better technology but extremely high margins facilitated by software. Apart from the core ranking/ads problem that M and G solve, most of it doesn't need to be that complicated. I would venture that lots of the cool technology stuff is designed to keep engineers happy so that the money train continues. Certainly the one I was at built a lot of cool stuff, but there was so much reinventing of the wheel that I suspect that the core business and products could have been served by a much much smaller engineering org.

osigurdson 5y ago
According to Jim Cramer (who came up with the FAANG acronym), we should now be using MAMAA (Meta, Apple, Microsoft, Amazon and Alphabet). https://finance.yahoo.com/news/not-faang-mamaa-jim-cramer-163000145.html https://finance.yahoo.com/news/not-faang-mamaa-jim-cramer-16...
- disgruntledphd2 5y ago
  I kinda agree with that, but MANGA is such a great acronym that I'd like to keep it.

jcrites 5y ago

This actually seems like a pretty simple problem, to be honest, where the obvious solution is the best one. Inverting a binary tree means reversing the order of the sequence of elements that it represents. Thus inverting a binary tree is simply swapping the left and right edge of every node recursively down the tree. You could do this with a recursive algorithm by modifying the tree in-place or by constructing a new tree. I don’t see any obvious candidate optimizations other than the fact that it’s straightforward to do in place (e.g. using std::swap in C++, or mem::swap in Rust). However I don’t think this is as good of an interviewing question as other potential questions. See my other comment in the thread for one that I think is better. The reason is that programming tasks like this are pretty uncommon to encounter as a professional software engineer. Better questions (IMO) are tasks that professional software engineers are likely to encounter while doing their job at the company — or representations of them, while testing knowledge of A&DS as necessary. Even if a company does particularly a lot of work with binary trees, then that company would be likely to have number of such A&DS already implemented. If you’re working at Google then I can’t imagine that you would need to build a binary tree data structure or an algorithm for inverting them; undoubtedly these implementations already exist within their standard libraries. Personally, I can’t immediately ever recall encountering a binary tree in business logic while working as a professional engineer. I wouldn’t expect to unless I was building some thing like a collections library or a specialized solution to a large scale problem like implementing a novel data store of some kind. And if I was doing that kind of work I’d break out references (e.g. Knuth as a starting point, and any relevant recent research), and review open source software for comparison or as a candidate for directly solving the problem (SQLite, MySQL/InnoDB, LevelDB & BDB, Apache Commons libraries, etc.)

WalterBright 5y ago
> The reason is that programming tasks like this are pretty uncommon to encounter as a professional software engineer. I'm not so sure. One aspect is even recognizing that the task can be done by a known algorithm. Not knowing the algorithms may make one mistakenly believe that the opportunity to apply algorithms never came up. > I can’t imagine that you would need to build a binary tree data structure or an algorithm for inverting them I'm sorry, they are so trivial it takes more work to understand the documentation on the library one than it takes to just do it. Though personally, if a candidate flunked the binary tree question, but had a very successful project, I'd take a closer look before rejecting him. For one thing, I'd want to have a look at the project's source code. I'd also want to verify he'd actually written the code for that project.

908B64B197 5y ago

> which are kind of irrelevant to real work, but the problem solving approaches you need to take are very relevant It's also a common vocabulary shared across engineers, no matter their seniority or where they graduated from. And knowledge of algo and data structures demonstrate someone could learn it in the first place. Especially for junior hires, it's an excellent predictor of success.

vanusa 5y ago

But the ability to problem solve complicated problems where the obvious solution is probably not the best one. Problems like designing "the most popular package manager on macOS", for example? I think what the author finds strange is that not only do many people still believe that LC (or whiteboarding) are effective proxies for general problem solving ability -- they seem to tacitly believe they are better measures than demonstrated, real-world problem solving achievements. Even problems that are significantly more multifaceted and nuanced. If it is wrong, it's working pretty darn well [for MANGA]. The problem is, these tests (and extensive rounds of them, with onerous time limits) are used by companies that (inasmuch as they would like to believe otherwise) definitely are not MANGA and certainly are not offering MANGA levels of compensation.

TulliusCicero 5y ago
> Problems like designing "the most popular package manager on macOS", for example? Yes, those fall through the gaps, but people with that kind of extremely strong, publicly viewable history are much more the exception than the norm.
- vanusa 5y ago
  Does have to be not just "strong" -- but "extremely strong" evidence? Not to split hairs - but it does seem to be a peculiar choice of words, there. I just don't see why the DSA filter has come to be considered so golden that one's ability to not just demonstrate some baseline capacity for this skillset, but to positively master a sequence of concocted performative rituals around it (specifically: reciting these algorithms in front of groups of strangers at a whiteboard; "talking" large blocks of code to someone over a phone; or doing online tests under completely unrealistic time pressure) -- that, in some corners at least, has come to categorically dominate all other selection criteria in the hiring process. (Actually I do see why -- but it all comes down to factors not related to the intrinsic importance of these skills, or to whether the candidate can effectively do the job).
  - TulliusCicero 5y ago