Comment by fishnchips
11 years ago
[Ex-Googler here] Truth be told this is a trivial question to be asked during an algo interview and as an interviewer I'd consider this a warm-up. Otherwise it's a rather poor question since either you know how to do it (ie, you have an idea about recursion) or you don't - there aren't too many shades of grey or possible follow-up questions that I can ask to probe the depth of your knowledge.
That being said if I asked this as a warm-up and we'd spend the whole interview trying to get that done then of course my verdict would be No Hire. As an interviewer it is not my job to look at your GitHub profile - instead I am assigned an area to check and I try to come up with the best understanding of the candidate in that area. While failing to reverse a binary tree is a total failure in algo/ds you can still be hired since there are several interviewers (if you make it to onsites, that is), each probing a different area.
My biggest problem with Google style interview process is that it's easily passed by folks who already passed it in a different company. After having interviewed hundreds of Google's candidates I moved to another big company with the same interview type and the experience was really surreal. On my algo/ds interview I got asked slight variations of the same questions I was asking myself - and over time I've seen some totally brilliant, unexpected solutions. Must have been a strange experience for the interviewer who got his questions each answered in 3 minutes tops. I also made it a sport to solve each one in a different language because why not. Not sure though about validity of the signal the company got from this interview.
> [Ex-Googler here] Truth be told this is a trivial question to be asked during an algo interview and as an interviewer I'd consider this a warm-up. Otherwise it's a rather poor question since either you know how to do it (ie, you have an idea about recursion) or you don't - there aren't too many shades of grey or possible follow-up questions that I can ask to probe the depth of your knowledge.
It is a terrible question.
First, you can't invert a binary tree (as in flip upside down). If you did, you'd end up with multiple roots and since all binary trees are rooted, you'd no longer have a binary tree. It'd be a tree, just not a binary tree.
If the questioner meant mirror a binary tree (swap left & right at each node), then it is a no-op. You do not need to modify memory to do it. Left & right are just labels for two pointers. You can just swap the order your variables in whatever struct defines your node and cast it against your existing memory (or change what your accessors return in a derived class or create a reverse iterator or however you want to implement it) and there you go, a "reversed" tree with zero overhead.
Either way, it is a terrible question unless you wanted to see if someone understood the difference between how a data structure is drawn on a whiteboard for humans vs. how it actually works. Maybe they were actually asking that question, but that seems highly unlikely.
And if they actually meant for you to recurse down and swap left and right on everything, it would dramatically lower my opinion of them because it would make me wonder if they knew the difference between how a binary tree is drawn on a whiteboard vs. how it is laid out in memory.
> First, you can't invert a binary tree (as in flip upside down). If you did, you'd end up with multiple roots and since all binary trees are rooted, you'd no longer have a binary tree. It'd be a tree, just not a binary tree.
Inversion is a transformation that maps directed graphs to directed graphs. Binary trees are a subset of directed graphs, so applying inversion to them is not unreasonable. That subset is not closed under inversion, so you can get results that are not binary trees, but I see nothing in the question that implies that the interviewer was asking for the output to be a binary tree.
That may even be one of the points the interviewer wants to see the candidate address. Since the output no longer has a single node from which all other nodes can be reached, in addition to just inverting it they may want the candidate to mention the need to have some new auxiliary data structure to keep track of the multiple root nodes (and perhaps note that in the inverted tree each node only has one outgoing link, so if we are inverting in place each has room for two, so we can use that now available second link space to make a linked list of the roots, so we don't need any extra storage for the new root list data structure).
> if they actually meant for you to recurse down and swap
While only the person asking this question knows for sure I'd assume that was the intention.
It's not a _terrible_ question - it's just a recursive equivalent of FizzBuzz. You would treat this as a way of making a (good) candidate gain some confidence. And that alone is extremely important since the more at ease the candidate is the better the signal that you're getting. What I was trying to say there was that if I asked that as a warm-up and didn't get a satisfactory response very very soon I'd realise that your man has no clue about recursion and would move to the main question, choosing one that does not involve it. It would be something easier than I'd ask otherwise and would be closer to real-life scenarios - like first solving a simple problem, then parallelising the solution and correctly managing concurrent access.
> First, you can't invert a binary tree (as in flip upside down). If you did, you'd end up with multiple roots and since all binary trees are rooted, you'd no longer have a binary tree. It'd be a tree, just not a binary tree
Just because someone wrote on Twitter with limited number of characters that the problem was to "invert a binary tree", does not mean there were no clarification from the recruiter.
> And if they actually meant for you to recurse down and swap left and right on everything, it would dramatically lower my opinion of them because it would make me wonder if they knew the difference between how a binary tree is drawn on a whiteboard vs. how it is laid out in memory.
If you're thinking about making a real structure, I believe you should recurse down and swap. If you don't do this, rotating, joining etc, could be a real pain.
If they said "swap left & right at each node" it would have been easy. But they used a term that doesn't even yield an example in google searches - what kind of "inversion" do they have in mind? It's as if everyone is on the same page but me.
You're allowed to ask your interviewer for clarification. You'll even get brownie points for asking smart questions.
"Invert a binary tree" and "inverting a binary tree" both give me as the first result in Google this Quora question where someone gives an example and asks how to do it: http://qr.ae/7NDCg4
Would a multiply-rooted tree still be a tree? I thought a single root was part of the definition of a tree. Would it instead be a graph?
Sorry for the elementary questions. I'm bad at algorithms and just trying to get a grasp here.
At my university it's common to call acyclic, connected graph a tree. We distinguish between rooted and unrooted trees. For example, minimal spanning tree doesn't really have to be rooted, it just has no cycles.
1 reply →
Tree is a graph without any cycles, hence the definition still holds. And yes, you can have multiple roots in a tree, ex:
a --> c <---b ^ d-----|
Yes, it's not a tree any more. Which is why I believe this was not the question.
Exactly. This style interview doesn't find the people I think are valuable - people who ship code. Instead, it validates people who spend time thinking about interview questions.
A lot of people require a github to get an interview. But nobody wants to look at what's on the github.
I've interviewed hires before, and if I ask for a github, I'm going to take the time to review some of the code, otherwise why would I ask?
The link between the content of your GitHub and your ability to ship code is unclear at best. I knew a guy who had a really awesome GitHub profile but turned out to be a mediocre contributor to the codebase. He claimed that coding style guides we used were hurting his creativity to the point that he did not enjoy coding and would avoid it if possible. He'd fix bugs and make small-ish contributions but would never ship major features or libraries "because of the style guide". While I understand the sentiment I always found his attitude juvenile.
Seems like that's something you could easily suss out in an interview if you asked him questions about his code on github.
This is about Google, which does not require a github.
The thread is about the industry in general, which has adopted Google's algorithm heavy interview process, but also adopted github and open source as a resume.