Hacker News Reader

Comment by arethuza | Hacker News Reader

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

View on HN

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.

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.

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.

Reply on news.ycombinator.com