Hacker News Reader

Comment by enriquto | Hacker News Reader

> I date the age of the Algorithm from roughly the 1960s to the late 1980s. During the age of the Algorithms, developers spent a lot of time figuring out the best algorithm to use and writing code to implement algorithms.

Today there's orders of magnitude more developers spending time figuring out algorithms and writing core to implement them than in the 80s. The difference, maybe, is that even more developers today do not write any algorithm at all. But if there's an age of the algorithm, it is today. At no point in human history have as many algorithms been written as today. And next week, many more will be written!

View on HN

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

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?

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

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.

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?).

I noted in an another discussion on HN that dependency checking is apparently NP-hard:

https://stackoverflow.com/questions/28099683/algorithm-for-d...

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.

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.

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.

Most people interpreted it as a horizontal flip like you did, though some cursed souls leapt to doing a vertical flip and converting it into a DAG. A horizontal flip is actually extremely simple, just check the base case, swap the pointers and recurse. Arguably easier than fizzbuzz, and imo a pretty solid interview question. A good argument for physically flipping it instead of tagging it as flipped is that localizes the operation instead of leaking a (potentially recursively) tagged tree into the rest of the application. Of course all the ink spilled about binary tree 'inversion' doesn't have much to do with the actual interview, which apparently was actually about converting from a min-heap to max-heap. Max also self-described as 'rude' w/r/t the interview, so hard to know if the heap incident was even why he wasn't selected.

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

Reply on news.ycombinator.com