Go Interview with a LinkedIn engineer

Watch someone solve the falling leaves of a tree problem in an interview with a LinkedIn engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Falling leaves of a tree

Interview question

1) Given a list of numbers and a target, find if there exists a difference of two numbers that makes the target. 2) Find how many ways there are to get from the top-left to the bottom-right of a grid only traversing down and right. 3) Return a list of list, where each list is a layer of leaves. After those leaves are accounted for, imagine that they fall off and the next level up is now a layer of leaves.

Interview Feedback

Feedback about Neuro Owl (the interviewee)

Advance this person to the next round?

Yes

How were their technical skills?

4/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

Amazing job. I should've given you more difficult problems!

Feedback about Existential Crumpet (the interviewer)

Would you want to work with this person?

Yes

How excited would you be to work with them?

4/4

How good were the questions?

4/4

How helpful was your interviewer in guiding you to the solution(s)?

4/4

Nice walk through, very helpful. Don't really have anything in mind to improve on.

Interview Transcript

Neuro Owl: Hello?

Existential Crumpet: Hey.

Neuro Owl: Hey, Sorry, I'm a little bit late.

Existential Crumpet: No worries.

Neuro Owl: How you doing?

Existential Crumpet: Good, how are you?

Neuro Owl: Good. Where are you calling from.

Existential Crumpet: Seattle. Where are you?

Neuro Owl: I'm from San Francisco, right now.

Existential Crumpet: Alright. So, do you have anything in particular you want to practice?

Neuro Owl: Well, I'm preparing for a Google and Facebook interviews, so if you know what kind of phone interviews they have, that would be great. Other than that, I didn't have anything in particular in mind.

Existential Crumpet: Okay. So I work at LinkedIn. I can give you questions of similar difficulty. I know that GeeksForGeeks has really good questions and then they list off questions by company. So I can do some Google or Facebook questions.

Neuro Owl: Okay, yeah, that sounds good.

Existential Crumpet: Cool. Alright. What would you the difficulty level you are going for here? I don't want to give you anything too easy, doesn't make very much sense.

Neuro Owl: Probably medium is good. Yeah, the medium is fine, probably. Yeah.

Existential Crumpet: Alright. Let's do this one. This one's hard. Alright, here's a medium. Alright. So. I don't know Go syntax, so I'm just gonna comment. So I'm gonna give you an array. It's gonna look like something like this. It looks kind of like that and then I'm also going to give you a number. I'd like for you to write a function that determines two numbers in the array that when the first number is subtracted by the second number equals to the number I provided.

Neuro Owl: So subtract the first one from the second one. And return what the index is or...?

Existential Crumpet: The numbers themselves are fine.

Neuro Owl: Okay, all right, cool. So. Um, well, I could just walk the array and then compare each number to... well not compare, but try to match the numbers one to another, and then if I find a pair, I just print them or return them. That would be a quadratic because I'll have to compare each number to the rest of the numbers, basically like a double for loop. To do the faster, I could... Just walk the array and then kind of keep track of what I've covered so far with a hashmap, of them consult a hashmap for each next number and and see if there is a match. So, I'll probably go with that so that, that's going to be a linear time. Is that okay? Alright. Yeah, go ahead?

Existential Crumpet: Yeah, so. Why don't you do that. I can ask a follow up question after it.

Neuro Owl: Okay, cool. So I know you said you don't know Go syntax, but it's somewhat C like, so should be pretty straightforward. Alright, so I'm gonna create a hashmap of an integer to an integer, what I'm gonna keep probably gonna in the map, the key is gonna be the value of the item in there and then the value is gonna be the index at which the number is at. So when we try this... Obviously the main function... we'll write an actual function. And it doesn't matter if we didn't find anything. Let me see how should I do this? Oh and the target number, that's right. And you said subtract first one from the second one, right?

Existential Crumpet: Yeah, I mean, the order that you return them should be such that A minus B equals the number provided.

Neuro Owl: A minus B, okay got it. Alright, say difference is going to be... I think the number itself should be inserted there. Yeah, well index would be... So that should work. Let me test that. I'm just gonna copy where you have here. Just print the function. Number. And let's run it. Alright, so that seems to work.

Existential Crumpet: Yeah. Okay. So... this is probably too easy for you.

Neuro Owl: Yeah, it wasn't too hard. It wasn't too hard. We can do another one if you want to.

Existential Crumpet: Yeah. Let's do another one. That's a that's a confidence booster, that's a warm up question right there. Alright. This one's a medium. So this one's called a count all possible paths. The idea is... This will be really math orientated, but there's a formula for it. But most people are not, so, they will basically run the simulation to figure out the answer here. So the idea is provided a grid.

Neuro Owl: Oh yeah, I love grids. For some reason the those things just click with me but yeah, let's continue.

Existential Crumpet: Alright, well maybe this will be easy too. So provided a grid where the substance of the grid is really the the edges, right? So you can think of it as a bunch of equidistant points and then edges between those points. It's an MxN grid, in terms of number of edges on each side. So it's a rectangular grid and the idea is that you start on the top and you want to finish at the bottom right. The idea is to count the number of ways that you can define a path from the top left to the bottom, right? Given the rule that you can only go right and down.

Neuro Owl: Okay, and then you mentioned that there is something in the cells themselves. Are they numbers, do they matter? Or it doesn't really matter, it's just a grid?

Existential Crumpet: They don't matter. You just return the number of different ways.

Neuro Owl: Okay, cool. So, I'm gonna... Usually what I do with the grids, I start at the left top, and then I recursively call the directions that I'm allowed to go to, for example, right and down and then I calculate the number... Oh, I need to calculate the number of ways I can get to the final point, right? Let me think about this. If I start here and then I have a little notebook here. I'm trying to visualize the grid, so if we go, right? It's one path from there. Oh I see so... okay. So I'm gonna go to each neighbor, well write them down, and then recursively go everywhere else from there and then what I'm gonna return is... What am I gonna return? I'm gonna return the number of ways I can get there. And so, how would I do that? Okay, so let me try that. So I'll just recursively call it and return a boolean, let's say true for if it actually reached the destination through recursion down down the path or false if it didn't. And then... I have to accumulate the numbers somewhere. Maybe it's not a boolean, maybe it's an integer that I need to... Yeah, it will have to be an integer. Alright, so let me try to code it up and then I'll see how it goes. So we'll have... you mind if I just delete the the other function or... does it matter if it stays there? Well, I'll let it stay there, okay. So, I'll have function walkCell that'll have a grid. Well, I guess if only are allowed to go right and down, we cannot intersect with... We cannot intersect our own path, I guess while we're trying to reach there, so that should be fine. Okay, go right and figure out the number of ways to get there. And yeah and then the same for the left. Oh down, not left. I guess that should work. So come here we get our one, come back as one, two, okay and here same grid and it's gonna be... So one. And two.

Existential Crumpet: Yeah, that definitely is not correct. So four by four grid, there will be exactly two paths that we can reach the top left to the top to the to the bottom right, so let me see where I got it wrong.

Neuro Owl: Just two?

Existential Crumpet: What's that?

Neuro Owl: Just just two paths?

Existential Crumpet: Oh I'm sorry, this is two by two, yes. I just drew two by two. Four by four would be a bigger matrix, yeah that's right, let me try that. Well actually since they did two by two, let me try. So it actually does give us two. What about a 2x3? Three.

Neuro Owl: Yeah, it seems to be working. It did give me the right answer for two small things there.

Existential Crumpet: Let's try running it with three rows and four columns.

Neuro Owl: So, it says ten is the answer for three rows and four columns.

Existential Crumpet: I think that's correct?

Neuro Owl: Alright. Yeah, like I said, I for some reason I can visualize the grid in my head very easy now. Trees are a little harder to to visualize.

Existential Crumpet: Do you want to try another problem?

Neuro Owl: Sure if you have time yeah, of course, we can do a couple of increasing, why not?

Existential Crumpet: Take a three like this and we'd like you to output a list of lists where the first index is a list of leaves that would fall off if it was a normal tree. And the next list is the second set of leaves that would fall off the tree hypothetically.

Neuro Owl: Okay, so basically, we need to get to the leaves and then kind of remove them. Well, add them to to the list, and then do the rest the rest of the tree as if we were say to remove those leaves, right?

Existential Crumpet: That's right. That's it. You don't actually have to remove the leaves.

Neuro Owl: Right. Okay. So we need to do the leaves first. Alright, well. So we can easily get to the leaves recursively and just collect them all once we get to a node that doesn't have any left or right children. We added to some list. But... But at that point we'll traverse the whole tree already. And then after that we need to get to the rest. So you said that we cannot kind of modify the input tree whatsoever? Because if we could just kind of cut off the leaves that fell, that would be easy.

Existential Crumpet: We could pretend that we're cutting them off because really there's nothing...

Neuro Owl: Alright yeah, that's right, so it's pretty much gonna be a... Well no, that's that's not gonna be like an inorder traversal because I have to get D and E, so that's easy. Next line I have to get the C, so I can't go back to B and say, oh now... oh well... Let me see if I can do it. So I'll return from D and E, we'll know. What do we know? Well okay, so if I were to say okay, so this is gonna be a linear time no matter, what I mean, it must be linear because we have to visit all the mode at least once, and let's say I'm gonna, you know, traverse the tree more than once. So say I first traverse the whole tree and find the the first set of leave and I just stick the values into hash maps, then I traverse it again and then at this point what I do is I traverse it and see if the children of a given mode are in that hashmap that we just populated and then I create another hashmap and then insert that node in. Yeah, it's just gonna be two hash maps and then that will give me the second level, that is B. So D and E are over there, so I'm gonna get B and then I go back to A and C's in there already. And then after that, I add this to the list and get the other half now. Alright that will work. I can I don't like the the additional solutions to use two hash maps for this and then I'll have to traverse the tree multiple times. Actually, how many times will I have to traverse it? Well, it depends on how many leave we have, so I mean, it's still gonna be linear, but it's definitely not a single traversal. So what do you think about this? I mean, this is not probably the optimal way to do this...

Existential Crumpet: Yeah, so I think. Your approach is definitely not optimal from a space perspective.

Neuro Owl: Okay, so you're saying we could probably do it in a single traversal?

Existential Crumpet: Yeah.

Neuro Owl: Okay.

Existential Crumpet: You can do it in a single traversal with only your result list.You have a mutating result list and then...

Neuro Owl: Right right, yeah. Alright, let me think. So okay, well I do have the level but the level doesn't really give us much. Okay, so I could get to the to the lead, to the first one, say you always go to the left node first, all the time. So I would get start from the root and which is a and then go to b and then go to d, ok d is the leaf, so I return back and I could return like an integer, so say every leaf is gonna be zero, level zero, so I will add because it's a list of lists, so all the leaves, if I consider them level zero, then I will populate the first list and the list of lists, and then I return back to B. I'll say well that was leaf and I will return one and so I populate the second thing there. And then from B I could return two, so the A will know to be added to two. Yeah, that could work, so if I kind of work bottom up fashion where I get to the leaves first and then start populating the list of lists from there and then I just indicate how many levels the previous call is away from the leaf, so that is when I return back from E to B, I will say, oh, you know your a level one, which means that you're just above a leaf node. So that could probably work, you want me to try and code that?

Existential Crumpet: Yeah one question, what happens when you get back to A.

Neuro Owl: So when I get back to A, b will return two, oh I see and C will return one. How should I handle that? I should probably take the larger number because like if for example D wasn't... Well yeah we should probably look at what the left recursion would return and the right would return and just pick the maximum number out of those two and kind of stick it in there. So that way A is going to be a level two, B will return two, and then C will return one, so it will say well B has a higher depth, so we'll take that.

Existential Crumpet: Cool. That makes sense.

Neuro Owl: Alright, so I'll do... And then oh, I need the array that's right. So, I should pass it. Well, is it okay if I make the list of lists a global variable kind of?

Existential Crumpet: Yeah, I guess so.

Neuro Owl: Well problem with Golang is it doesn't have arrayLists. So I'll have to like re add them all the time, that's... Well, I guess that's fine. Yeah. So I can just like array push or something. I guess I could create a structure to do that, but I'll just go with this. So I'll I constantly like redefine it and have to return a new pointer, that's the pain. Yeah, that's the list of lists and then... I will say results because this is where I'll keep the lists.Then what do I want to do? Oh, I want to find the max. And this is what I'm talking about. you have to constantly resize the arrays. So, well, yeah. And then. Grow it if we don't have the level yet, we add the level and then we grow that. You'll have to go somehow, but let me see. So, how do we get to the lead node? So let's start with the root and go and go and go. And I will find the leaf node, how to find it? So once we get to the leaf, we just simply insert to level zero. Oh, we need to turn two, so we will return one. If not, we go and traverse the left of the right if we can. And what do we do? Alright, so let me try, wheres's D? D will get inserted first and we return 1, so we come back for B, we'll go to E, E get's inserted. Then here we'll receive both of our depth ones, so it's gonna be one, it's smaller than one. Oh, so less than or equal, let's say a res of one. Yes, this will work and here we'll return res and also the max steps plus one. So that will make it such that A will receive two. Alright, so this this should work. This is our base case for the recursion to terminate at the leaf nodes and we're basically just keep populating the first list of the lists.

Existential Crumpet: What are you returning as the result?

Neuro Owl: So what happens in Golang, so you see how like the array? Well so array type is a pointer and you can you can modify the array elements, but once you call this, append, which is like growing it, so like say have three elements and you're adding the fourth and what that does it basically allocates new memory, copies the whole thing over and then, you've got a new pointer. So that's what I was mentioning, saying that it's a pain. I mean you wouldn't do that for you know, for normal code, like passing arrays around and kind of, you know, appending, recreating old ones. I would usually use a like an arraylist, where you can just like create one pointer and then just like push into it, and then you just have to pass it around, you don't have to return it. That's why I suggest well, you know, if I made a global variable, then I wouldn't have to return it, but yeah it kind of cumbersome.

Existential Crumpet: So on line 51 and line 55, looks like you're finding the result twice. Is it because of scope?

Neuro Owl: Wait, uh say that again, so what happened twice?

Existential Crumpet: So on 51, you're finding the second result of walking. And on line 55, you are also finding the result?

Neuro Owl: Right, yeah that's the same thing. So both of the recursive calls might have changed the refs, right? Because you recursed down the some node and it will change, you have to get back the new pointer so you can pass it up. That's why you have to like pass it around because like once you call append, it will basically take this res that exists and create a new pointer, copy the existing values, add new empty array or whatever else you do, and then return the new pointer so you've got to save it and kind of pass it up.

Existential Crumpet: So it sounds looks like you're calling walking, you're passing res down to it, and then it returns a res pointer that may be the same pointer but it might be a different pointer right?

Neuro Owl: That is correct, yeah?

Existential Crumpet: Right and then on line 55, you... Oh actually yeah.

Neuro Owl: Yeah, so it's like I'm just passing a point around but it's like a variable that I have to keep track of and return everywhere. It's yeah, it's a pain. But yeah.That makes sense. I'm thinking of this as unusual.

Existential Crumpet: Okay, cool, yeah.

Neuro Owl: Alright cool yeah, that was helpful.

Existential Crumpet: Alright, next time you should ask for hard questions.

Neuro Owl: Yeah yeah, maybe you're right, I'll try to do that next time.

Existential Crumpet: Alright, well, best of luck in your job search. I think you did really well.