Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Inverting Binary Trees Considered Harmful

jasq.org

Post reply on HN
Print view View original

61–70 of 225 posts

Re: Inverting Binary Trees Considered Harmful

#61

Post by rtpg »

orangecat wrote: post #43

I'll be the contrarian and claim that inverting a binary tree is a perfectly reasonable interview question. (Although not anymore now that it's famous). It combines basic background knowledge (what is a binary tree and how is it structured?), ability to reason logically (binary tree algorithms are often recursive, "inverting" a tree with no children is a no-op, otherwise you want to swap the children, and the childre…

I also think it's an extremely simple question, but only if you've ever taken a data structures class.

Turns out a lot of people in our industry don't! I have a Computer Engineering degree, and know this stuff mainly due to this being my hobby (and having tried out for the IOI in high school). But there are former classmates who are only vaguely aware of these data structures, because they never got any exposure to them despite writing real programs.

I don't think there's a super strong argument that most computer engineers need to know much of anything about base data structures. There are so many other concepts that are more important to writing and deploying useful software (especially in the enterprise world) that at no point involve writing complex data structures. Data structures (or rather, knowledge of the internals) are much more domain specific than some of us would like to admit, especially in the age of RoR and Unity. There are many more design patters more important to know about than being able to implement quicksort (it took 6 years for researchers to write the first bug-free implementation!)

Google does it because they can. They're probably filtering out a lot of people who treat code as prose rather than a technical manual though. Which is probably why Google libraries look the way they look.

The biggest surprise for me is how many game programmers don't know about this stuff. It seems like the sort of stuff you'd run into pretty quickly

Re: Inverting Binary Trees Considered Harmful

#62

Post by IgorPartola »

I love interviewing and being interviewed. Don't know why but I do. However, I hate these types of interviews. I mean, sure if I am a new grad or you suspect I might not know my shit, ask me some probing questions. However, almost nobody these days needs to invert a binary tree or compute the hash of a string by hand.

Here is my secret go to question when interviewing someone: "can you describe how an AJAX request works, from start to finish?". The answer involves knowing that AJAX works over HTTP, same as regular page requests, knowing what IP, TCP, and HTTP are, and how client and server interact using them. It is a question most competent people can answer, yet it has lots of room for depth of detail. By discussing technical subjects, challenges and solutions I think you get a much better idea of how good someone is vs some predefined set of puzzles.

Re: Inverting Binary Trees Considered Harmful

#63

Post by gnuvince »

rayiner wrote: post #42

I don't think inverting binary trees is the problem per se. I mean, algorithms are the bread and butter of programming. You should be able to implement simple ones like that even if you'd never actually do that in practice. The real problem in my opinion is the whiteboard and time pressure.

I gave this example on Reddit this morning, but I'll repeat it. If a programmer was given an array of elements [a1, a2, a3, a4, ..., an-1, an] and asked to produce the array [a2, a1, a4, a3, ..., an, an-1] and couldn't do it, he'd be the laughing stock of /r/programming for a couple of days and we'd hear about this problem for years to come, the same way we hear about FizzBuzz. Certainly a programmer should know how to traverse an array and manipulate its elements!

For the case of inverting a binary tree, we haven't gotten a clear answer to what it means, but the concensus seems to be to swap every left and right nodes in the tree. Well, that's exactly like the array problem above: traverse the structure and manipulate its elements! The traversal is not a simple loop, you use recursion (or if you're fancier, use an explicit stack to avoid causing an overflow of the call stack), but I'd argue that recursion is a fundamental notion for a programmer to know.

A commenter on Reddit mentioned that there's a difference between programmers and computer scientists and that the programmer is responsible for writing software and the computer scientists are responsible for coming up with algorithms and data structures. But then, what do the programmers use? If we cannot expect them to know about trees, what about linked lists? Resizable arrays? Hash tables? Graphs? These data structures are extremely important tools for creating solutions, shouldn't programmers be aware of them and how to use them?

Re: Inverting Binary Trees Considered Harmful

#64

Post by sriram_sun »

The rules are pretty clear on what the interview will cover. The recruiter tells you months before the interview and they (Google) even send you a list of what books and papers to read before you consider yourself ready. That is more than fair. I just joined a start up. It consists of 3 non-minorities and 3 minorities. All three non-minorities were recruited early on because they all knew someone within the company (and they all were competent). All three minorities came in through a recruiter - expensive and the bar definitely was a little higher than the internal referral-hire process.

So In summary, I like Google's process for its fairness. They also seem to hire quite a few good engineers and a few great ones too.

Re: Inverting Binary Trees Considered Harmful

#65

Post by mianos »

wyldfire wrote: post #17

I enjoy the challenge of programming interviews. When I interviewed in Mountain View, I thought it was just super cool to have been invited. It was like the mother ship had summoned me home! I was mega-underwhelmed when I botched the last session, though. And after doing so poorly, no one escorted me out or summed things up. Efficient, I suppose -- I'd met with the recruiter at the beginning of the day and there was…

Identical experience. They had me design and implement a practical thing. It was an interesting problem, not something I would normally be able to do in 30 minutes. They wanted it in 30 minutes. After about 20 I stopped coding on the whiteboard and started explaining where I was going with it. It was not complicated, just using a hash to store things, but the removal involved moving used blocks a free list of pre-used slots so the overhead of adding a new costly element was way cheaper. This would beat a binary tree for the scale of elements they where talking about but still easily kept in ram. I am sure they didn't have a clue what I was talking about. I think they wanted an RB tree based algorithm and a more primitive solution. Right after the interview I implemented it and sent it to them. I didn't even get a reply. About two months later I got a survey. This was after three interviews. The happy ending is I have used that bit of code several times since and it rocks. :)

Re: Inverting Binary Trees Considered Harmful

#66

Post by BinaryIdiot »

Osiris wrote: post #48

The last interview I did was for a node.js position. I was told to bring my laptop. When I got there, the put me in an office and handed me a packet with instructions on checking out a nearly empty git repo. Then they said "Write an API that meets as many of the following requirements as possible and push the code. We'll be back in 3 hours." After 3 hours, I was taken to a conference room where I demonstrated the API…

That actually sounds like a decent way to do things. The only thing I'd change is making it shorter and trying to incorporate some pair programming at least to some minor degree to see how well they communicate along with developing.

Re: Inverting Binary Trees Considered Harmful

#67

Post by gnuvince »

matchu wrote: post #55
gnuvince wrote: post #44

Earlier quoted context omitted.

So instead of giving them an algorithm problem that they might have seen in the past (or seen something similar) you give them a random open source project -- along with all the idiosycracies it certainly contains -- that they are 100% unfamiliar with and ask them within a few minutes to make sense of the entire codebase and produce a meaningful contribution? Sorry, but that sounds even more cruel and unusual than as…

This might be viable if you do it remotely: let them take their time to understand the project, understand the task, find the relevant section of the project, find the relevant section of code, understand the change they need to make, set up the development environment, and make the change. That's at minimum a day's work for most tasks, and sometimes two if setup or debugging turns out to be more difficult than expec…

I personally wouldn't be willing to spend 8 or even 16 hours working on an interview question for the chance to receive an offer. I'd take the one hour whiteboard dance.

Re: Inverting Binary Trees Considered Harmful

#68

Post by Xorlev »

BinaryIdiot wrote: post #59
swang wrote: post #2

Not sure what OP is being proud of exactly. I was subjected to this style when I interviewed at Twitter. Sorry my op sounded like I was accusing the author of something but this whiteboard approach is what I did at Twitter.

Yeah I don't think OP was defending Twitter I think it was just more of a story about how crappy the interview process is at most tech companies. My experience with Twitter was really odd. I knew someone internal and had them directly submit my resume with a recommendation. The resume was tailored for exactly the position they wanted showing me besting all of their requirements. I got an email 4 months later telling…

It's possible the position was filled, so some hiring manager just cleared the queue.
Post reply on HN