What does it mean to invert a binary tree?
I've seen it mean two things. One is to swap right and left. Another is to take the deepest leaf and make it the root.
Inverting Binary Trees Considered Harmful
31–40 of 225 posts
Re: Inverting Binary Trees Considered Harmful
#32Earlier quoted context omitted.
To change the nodes to point the other way around. So if the left edge of N1 points to N2 and the right edge points to N3 you make it so that N1's left edge points to N3 and the right edge points to N2. It's a trivial problem of changing pointers around. It's like 4 or 5 lines of code if you write a recursive function.
def invert(node): if node is None: return invert(node.left) invert(node.right) node.left, node.right = node.right, node.left Yep, pretty much. But, to be honest, if you hadn't described it I wouldn't have had a clue what was meant by inverting a tree. Zippering it or something? I wouldn't know.
You can ask the interviewer to clarify what the question is or what the result should look like. You should always ask for more details ask if you don't understand the question, and sometimes people ask in a vague way to see if the candidate will ask for clarification for better or for worse. It will not make you look stupid.
The simple action of saying "I don't know what you mean by X" or "I don't understand what X is" builds up your credibility, not reduce it. People who aren't afraid to ask questions demonstrate credibility because when they do say they know something you know they probably actually do.
I have learned so much from not being afraid to say "What is X" when someone starts talking to me about something and assume I know what it is already.
Nobody has ever laughed at me for this. Even if they did, it wouldn't bother me, because I'd rather I look silly and then learn what it is than to pretend I know and then actually end up not learning what it was someone was talking to me about.
Finally if they did think you should have known what the topic was you'd rather they know that about you while they're evaluating you not after you're hired and end up in over your head. This is a really unlikely scenario. These interviews are not so much about what you know, but how you solve problems.
Re: Inverting Binary Trees Considered Harmful
#33What does it mean to invert a binary tree?
exactly :)
Re: Inverting Binary Trees Considered Harmful
#34I 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…
I don't mean to personalize this to you, but your story kinda illustrates one of the problems. There's so much ego and self-worth tied up in both sides of this style of "interview". Both sides have this overwhelming need to show how smart they are.
It's understandable in some ways. It's part of what attracts people to the field, showing off intelligence. I'm guilty of it myself.
But it makes the "interview" process have an adversarial nature most of the time. That's not helpful to the actual goal of hiring people who will make your team successful.
One thing that might work along these lines- Bring in a hard problem that the interviewer doesn't know how to solve and spend some time trying to solve it with the candidate. As a team, discussing different options and problems with those options. You know, like people do in actual work situations...
Re: Inverting Binary Trees Considered Harmful
#35>You are then ushered into a room with the programmer's worst nightmare - a blank whiteboard. Am I the only one who enjoys programming interviews? Even if you screw it up, it's still fun to try your hand at whatever problem they give you. They also don't expect you to do it perfectly; you're allowed to have sub-superhuman performance.
I think the idea of solving a whiteboard problem can be fun, providing it's unique. Quite a few times while looking for an internship I was asked mostly standard problems out of "Cracking the Coding Interview" or similar. Under pressure, even problems I've practiced or just understood from a contextual standpoint can be tough. Personally I have issues with the usual situation of it - interviewer staring, which is intimidating, and/or not even trying to have a mutual conversation and bounce ideas around to ease some of the pressure.
Re: Inverting Binary Trees Considered Harmful
#36I 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…
Nice attitude! The fact that your curiousity drove you to figure out the problem long after its solution had immediate utility...that's always a good feature for a programmer.
Re: Inverting Binary Trees Considered Harmful
#37Fact is, it just isn't true. As a Googler, I am surrounded by enormously talented engineers, the likes of which I rarely encountered on the outside. They love what they do, and it shows.
I have no doubt that there are false negatives/positives, but I am convinced that Google is doing something right.
Re: Inverting Binary Trees Considered Harmful
#38I faced similar experience but here in India , since good interview questions are rare , most of the times questions are repeated from forums such as Career cup , I was asked questions irrespective of my role . I do take interviews at my current organization and ask simple practical problems with very simple solutions but most of the times candidates think in terms of complex data structures instead of simply trying to solve a problem, they do premature optimization and what not .
Re: Inverting Binary Trees Considered Harmful
#39Fact is, it just isn't true. As a Googler, I am surrounded by enormously talented engineers, the likes of which I rarely encountered on the outside. They love what they do, and it shows. I have no doubt that there are false negatives/positives, but I am convinced that Google is doing something right.
A slightly...biased perspective?
Re: Inverting Binary Trees Considered Harmful
#40While I'm completely, 100%, against these kinds of questions, how else can a company that receives thousands of resumes a day filter out the good from bad?
How about sitting the candidate down in front of an actual computer, or ask the candidate to bring in their own laptop? Then if you want to see how they do, pick out some open source projects that need a feature or two added, or a bug fixed, and have the candidate walk through some solution? This way, you are getting to see what their style is, and the random open source projects gets a potential improvement. And you…
I like this idea for small firms, but how does this scale to the level that the parent comment is asking about? If we want to interview a few hundred candidates this month, who finds the few hundred open-source project tasks and audits them for appropriateness?
And, for what it's worth, the peg game problem sounds to me like standard interview fare: an interesting puzzle that bears little resemblance to real-world software challenges. Why is it a better alternative?