I was interviewing with Uber recently for a staff engineer role. It was a coding round. An Uber staff engineer was interviewing me. Problem: Given an N-ary tree, print the boundary nodes, anti-clockwise. I took up an example to see if I understood the problem correctly. So for the below example (see image) I asked if the correct answer was 1-2-4-5-6-4-3 He argued since 4 is already visited, I shouldn't visit it again. His take was that it should be considered as part of the left view, (so, 1-2-4-5-6-3). He further stressed that if 4 were a child of 3, then it should be visited on the right side, in which case it would be 1-2-5-6-4-3. I was confused. Many such examples later, it was clear to me that the interviewer wasn't presenting a well-defined problem statement, or didn't understand the problem hinself. He was half assing a problem he read somewhere without actually thinking through it. Eventually I confronted him on this. He kept defending his views. He kept using the terms right child, left child and such. I figured out that he was thinking of this as a binary tree. Then with another example (fig B), I showed him the error of his thinking, when he said this should be 1-2-4-5-3, as 3 was the right child of 2 so should be in the right side scan. I told him N-ary trees don't have left and right children. They just have children. Just because I have drawn it slightly to the right doesn't make it the right child. Eventually he gave some excuses, and modified the problem statement to something simpler. I solved that and the interview finished. The idiot gave me a border-line rating. So much for being a staff engineer at Uber. What do you think of this incident? -------------- EDIT Many of you seem to think that in an N-ary sequence of children, the first one can be treated as the left child and the last one can be treated as the right child. What you are missing is that that is a trivial case, and not the source of the contention here. The source of contention is how to treat node 4 in the fig a (unlabelled image below) and the node 2 and 3 in fig b (the attached image labelled as b). The interviewer wasn't offering a consistent approach to it. He was calling the fig a, element 4 as left, and fig.b element 2 and 3 as right. Also I probed with many other examples to try to understand if I was indeed missing something. No, I wasn't. The interviewer was indeed in the wrong here, which is why once I politely confronted him with some concrete counterexamples with the only child of a node drawn directly below the parent, he went into a brain freeze, made up some excuses, immediately became defensive, went on the backfoot, and swapped the problem statement, while making some excuses. It was clear to him that he had f'd up, but didn't have the integrity to acknowythe same. By then we had lost a major part of the interview time by then, so he just gave me a borderline rating. I did end up getting an offer, but got down-leveled (which I politely declined) due to system design and behavioral interview performance, but that's completely on me!
Draw a circle around it, trace it counterclockwise, see which nodes you encounter close to the circle.
You are making the same mistake as the interviewer. Where it is drawn doesn't mean where its logical position is.
Tesci, have you considered that a binary tree has no left or right either. Just two leaf nodes. However, we ascribe the positional attributes just based on convenience to solve a problem. You could have done the same and made a positional arrangement for an n-ary tree too, such that you would get a left-most child and right-most child. Now, I agree that there could be boundary condition issues such as a node with a single child being able to potentially call that child both the left most and right most child for example. But those are just conventions/definitions that you can just define on the fly, right?
Man this is stupid sorry you were stuck with a moron. I experienced it before. You can request another round if you get a level below. Or stick to your level and refuse an offer except for staff
That's exactly what I did. They made an offer but down-leveled me. I refused the offer. Will keep looking.
Here is my solution to the original problem. I will keep two variables - level and place. Level tells me the depth of the node from root. Place tells me the position of a node among its siblings. For example, node 1 has three children - x,y,z. Then place of x is 1, y is 2 and z is 3. Now, for printing the boundary nodes, only include those nodes whose level is minimum possible or maximum possible(leaves). Also, include those nodes which are present at minimum place and maximum place at each level. Handle the duplicates.
You are assuming the number of nodes has predefined placeholders for children nodes identified by position. In the actual problem statement we had a sequence of children without any null placeholders representing any absent children of a given node. Had the case been otherwise, perhaps the interviewer should have framed the problem accordingly. That's why I am speculating that he didn't really have a grasp on the specifics of the problem; probably just looked up the problem statement superficially and threw it at me.
I get really confused by what you mean by “predefined placeholders”? So a tree node has a children array, and the array can be of any length. The first element is automatically the left node, the last element is automatically the right node, and they can be the same node, in which case don’t output that node twice in the result. Agree that all the children arrays wouldn’t have exactly the same length realized through “placeholders”. But that doesn’t prevent you from knowing which is the left child and right child. What’s the problem?
what if the n-ary tree has an index for each of its children? couldn't you assume that and then solve it after getting on the same page.
Yeah, with a list of children nodes, the 0th node is the left node, the length-1th node is the right node, and if left and right node are the same, use it as appropriate if it becomes part of the circle. Now if it becomes both the left and right side of the circle, define it such that it only counts for the left side and leave it out for the right side. Seems to be a well defined problem. What’s your build in Elden ring? Mine’s good ol quality
In the problem statement, there were no placeholders for missing nodes. It was a sequence of non-null children nodes.
Honestly, if he was being pushy you could've just solved it the way he thinks. Then as a follow-up talk on your optimizations. Feel you both failed the interview given that. Would've won the battle and the war in that case, now you only won the war. I feel foe you though OP, some interviewers shouldn't be interviewing lol
I would have, and I tried, but his 'approach' wasn't consistent (because he didn't understand his own problem statement) There was no way to tell if the node visible from both the left and the right side of the tree should be considered in the left side scan or the right side scan. I proposed if we could consider them all as left (because we would encounter them first there in an anticlockwise scan). He kept on moving, (which I later realised was based on if I had drawn it to the left or right of the parent node)
When you get a hint that interviewer is sticking to a solution he has in mind, you could have just played along the solution what he is looking for. Sometimes interviews aren't a place for finding who is right or wrong, remember the goal is to get a "HIre" . if that requires you to play dumb for 45 mins, what is there to lose... play the game.
I would have, but he didn't have a consistent pattern. Kept calling nodes left or right on the figure I drew based on how I had drawn them, instead of any inherent property, direct or derived, of the nodes themselves.
node.children[0] is left node, node.children[node.children.length-1] is right node.
you were unable to work through a problem without being combative. pretty sure thats a fail even if the interviewer made a mistake. if he doesn’t want duplicate nodes then dont give duplicate nodes, who cares, just go along with it
I’m not reading all of that. I will say that I’ve been there, interviewing for senior positions with a mid level interviewer, and they stick to their script so hard that it screws everyone over. And they’re likely congratulated for having “such a high bar”. It sucks, move on.
Interviews are already frustrating. These kinds of incidents make them demotivating.
Interviewer passed stupidity bar, why ask questions one has no clear understanding of