3 ms·

You're missing the point. There is a larger absolute number of people working on complex algorithms, but as a percentage it is much smaller. In the 60's deep al

by dtech 6y ago

You're missing the point. There is a larger absolute number of people working on complex algorithms, but as a percentage it is much smaller. In the 60's deep algorithmic knowledge was required for 90%+ of programming tasks, now it is probably closer to 1%. It is perfectly possible to make a living as a programmer nowadays without being able to inverse a binary tree

oriolid 6y ago
What's the obsession with inverting a binary tree? I have never found an use case that particular algorithm, but on the other hand I would be very happy if more programmers were aware that having a where clause in sql statement (and maybe and index) is more efficient than selecting entire database and looping over the results, even if the end result is the same. I understand that in order to come up with the inversion on the fly you need to know about trees and recursion, but is it really that scary?
- arethuza 6y ago
  Possibly due to the tweet by Max Howell: "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."
  - oriolid 6y ago
    Probably unrelated, but every time I update Homebrew, I get the feeling that there's something that should be O(log N) or O(n) but the implementation takes O(N), O(N^2) or worse. There's no way checking a small list of installed package versions against a large list of available versions should take that long.
    - OldOneEye 6y ago
      Oh, yes, this! I feel like I'm going crazy that my team members cannot see how incredibly slow Homebrew is. I don't know the reason for this, but updating the list of packages is excruciatingly slow and it does it every time I want to install anything. Every time I have to use it, I have time to ponder about my life choices (like why am I using a mac to do sysadmin/dev work?).
    - arethuza 6y ago
      I noted in an another discussion on HN that dependency checking is apparently NP-hard: https://stackoverflow.com/questions/28099683/algorithm-for-dependency-resolution https://stackoverflow.com/questions/28099683/algorithm-for-d...
      - oriolid 6y ago
        I doubt it's just this, since on my laptop just brew list from warm cache with 102 packages takes about a second, and twice as long if files must be read from SSD. That's a lot of reading and computation for list of 102 packages.
  - rodw 6y ago
    Apparently I've been living under a rock because despite 20+ years of professional software development (and a degree in discrete mathematics) I wasn't familiar or at least didn't recall this "invert a binary tree" problem. I had to look up what we mean by "invert" here. My first thought was "flatten the tree depth first and then reverse that linear list" which I knew to be inefficient, but I'm guessing I'd eventually stumble upon the recursive version of that when I got down to the nitty-gritty. But now that I think about it can't you solve this problem with a single boolean flag that says "read right to left" or "read left to right"? I.e,. if the children are labeled `A` and `B` and you interpret "normal" as A,B and "inverted" as "B,A", isn't that sufficient? That's basically what the recursive version of this algorithm is doing, but why bother to actually move data around? I get that this is an abstract problem, but I'm having trouble understanding any practical use case for this concept. If you've got a real, in-memory, linked-list-style binary tree my `is_inverted` flag seems like it would be sufficient. And if the real problem is moving blocks of data around on disk or in buffers, then isn't this all a question of the exact "flat" representation of this tree? If my whiteboard answer was "keep a flag that says whether or not the tree is inverted" would I be hired? Can someone reframe this question in a way that makes it clear that the trivial rtl-mode vs ltr-mode is insufficient? The only way this question makes sense to me is if you're really looking for someone to come up with the serialized representation of that data structure that makes this transform efficient, but none of the public answers to this question seem to cover that at all. I honestly don't understand how this problem is meaningful for the in-memory, linked-list case.
    - tlrobinson 6y ago
      Like many algorithm interview questions, I'm not sure it's meant to be a practical problem, but rather one that demonstrates your ability to think through problems. (Out of principle, I prefer to ask interview questions that are based on real problems I've had to solve in my job, but sometimes they're harder to ask coherently than well-defined/concise problems like "invert a binary tree" so I can see the appeal) > If my whiteboard answer was "keep a flag that says whether or not the tree is inverted" would I be hired? Personally I'd give you bonus points for recognizing that could be a solution, then clarify that I wanted a solution that actually moved the data around and give you the opportunity to answer it in light of that clarification.
virgilp 6y ago
They're not missing it, that is their point exactly: that relative numbers don't matter, absolute numbers do. Of course you no longer need 90% of programmers to write hardcore algorithms - we've evolved beyond that (and yes it's evolution, not involution).

by dtech 6y ago

oriolid 6y ago

What's the obsession with inverting a binary tree? I have never found an use case that particular algorithm, but on the other hand I would be very happy if more programmers were aware that having a where clause in sql statement (and maybe and index) is more efficient than selecting entire database and looping over the results, even if the end result is the same. I understand that in order to come up with the inversion on the fly you need to know about trees and recursion, but is it really that scary?

arethuza 6y ago
Possibly due to the tweet by Max Howell: "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."
- oriolid 6y ago
  Probably unrelated, but every time I update Homebrew, I get the feeling that there's something that should be O(log N) or O(n) but the implementation takes O(N), O(N^2) or worse. There's no way checking a small list of installed package versions against a large list of available versions should take that long.
  - OldOneEye 6y ago
    Oh, yes, this! I feel like I'm going crazy that my team members cannot see how incredibly slow Homebrew is. I don't know the reason for this, but updating the list of packages is excruciatingly slow and it does it every time I want to install anything. Every time I have to use it, I have time to ponder about my life choices (like why am I using a mac to do sysadmin/dev work?).
  - arethuza 6y ago
    I noted in an another discussion on HN that dependency checking is apparently NP-hard: https://stackoverflow.com/questions/28099683/algorithm-for-dependency-resolution https://stackoverflow.com/questions/28099683/algorithm-for-d...
    - oriolid 6y ago
      I doubt it's just this, since on my laptop just brew list from warm cache with 102 packages takes about a second, and twice as long if files must be read from SSD. That's a lot of reading and computation for list of 102 packages.
- rodw 6y ago
  Apparently I've been living under a rock because despite 20+ years of professional software development (and a degree in discrete mathematics) I wasn't familiar or at least didn't recall this "invert a binary tree" problem. I had to look up what we mean by "invert" here. My first thought was "flatten the tree depth first and then reverse that linear list" which I knew to be inefficient, but I'm guessing I'd eventually stumble upon the recursive version of that when I got down to the nitty-gritty. But now that I think about it can't you solve this problem with a single boolean flag that says "read right to left" or "read left to right"? I.e,. if the children are labeled `A` and `B` and you interpret "normal" as A,B and "inverted" as "B,A", isn't that sufficient? That's basically what the recursive version of this algorithm is doing, but why bother to actually move data around? I get that this is an abstract problem, but I'm having trouble understanding any practical use case for this concept. If you've got a real, in-memory, linked-list-style binary tree my `is_inverted` flag seems like it would be sufficient. And if the real problem is moving blocks of data around on disk or in buffers, then isn't this all a question of the exact "flat" representation of this tree? If my whiteboard answer was "keep a flag that says whether or not the tree is inverted" would I be hired? Can someone reframe this question in a way that makes it clear that the trivial rtl-mode vs ltr-mode is insufficient? The only way this question makes sense to me is if you're really looking for someone to come up with the serialized representation of that data structure that makes this transform efficient, but none of the public answers to this question seem to cover that at all. I honestly don't understand how this problem is meaningful for the in-memory, linked-list case.
  - tlrobinson 6y ago
    Like many algorithm interview questions, I'm not sure it's meant to be a practical problem, but rather one that demonstrates your ability to think through problems. (Out of principle, I prefer to ask interview questions that are based on real problems I've had to solve in my job, but sometimes they're harder to ask coherently than well-defined/concise problems like "invert a binary tree" so I can see the appeal) > If my whiteboard answer was "keep a flag that says whether or not the tree is inverted" would I be hired? Personally I'd give you bonus points for recognizing that could be a solution, then clarify that I wanted a solution that actually moved the data around and give you the opportunity to answer it in light of that clarification.

virgilp 6y ago

They're not missing it, that is their point exactly: that relative numbers don't matter, absolute numbers do. Of course you no longer need 90% of programmers to write hardcore algorithms - we've evolved beyond that (and yes it's evolution, not involution).