Python Interview with a Microsoft engineer

Watch someone solve the merge linked lists in order problem in an interview with a Microsoft engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Merge linked lists in order

Interview question

1) Given two linked lists, merge them into one such that their values are in sorted order. 2) Given a full binary tree, return an array containing the boundary elements from the left, then bottom, then right side, without duplicates.

Interview Feedback

Feedback about Efficacious Pirate (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

Really very good skills, extremely communicative . Room for optimization in timing - practice practice practice. Each question should not take your more than 20 mins.

Feedback about Astronomic Avenger (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

You were awesome! I really appreciate you taking a few minutes out at the start to talk to me generally before diving into the question, that helped me be less anxious than I'd typically be. You were also ready to jump in whenever I was struggling and gave me the space to think when I needed to. Great idea to put a "model" solution in for me to study from too. Audio issues aside this was the best experience I've had on this platform. Thank you very much and have a great weekend!

Interview Transcript

Efficacious Pirate: Hi.

Astronomic Avenger: Hi, Efficacious Pirate.

Efficacious Pirate: Yeah, that's me. Efficacious Pirate. And you're Astronomic Avenger. Nice to meet you.

Astronomic Avenger: I'm glad that you can hear me. Thank you for verifying. I've been having problems with the headset. So if you have any issues.

Efficacious Pirate: Oh, I didn't have any issues.

Astronomic Avenger: All right. So, how's your Saturday morning going?

Efficacious Pirate: Oh, well, I wish I could be doing anything else, but you know, we're here. It's not too bad.

Astronomic Avenger: So have you just... give me a one... Excuse me for the interruption. Have you been through one of these prep interviews with interviewing.io before?

Efficacious Pirate: Oh, yeah, this isn't my first one. Usually what happens is that I tell people a little bit about my background and language I'm comfortable with. So I'm still in University, but I'm looking for a new grad role, since I'm graduating this year. And that's my goal.

Astronomic Avenger: Great. So what kind of role are you looking for? Engineer?

Efficacious Pirate: Yeah, software engineer.

Astronomic Avenger: Software engineer. Okay. Any specific area?

Efficacious Pirate: Oh, right now just looking for a generalist stuff. I have an on site interview coming up with Microsoft. Right. That's all. Background is machine learning.

Astronomic Avenger: Machine learning and AI?

Efficacious Pirate: Yeah, I started a long time ago. Not too long ago, but I won a few international competitions, which put my name on this page, like $35,000 in one. And, you know, was impressive on paper at least. So that's how I got it.

Astronomic Avenger: That's awesome. And so this is probably going to be, I mean, given Coronavirus and everything, it's probably going to be...

Efficacious Pirate: The same format. Yeah. I'm sorry, I didn't say anything after it's probably gonna be.

Astronomic Avenger: Okay. All right. Let me quickly switch to... All right. I am connected back now.

Efficacious Pirate: Oh, good, I can hear you better. I'll let you know if I'm having issues.

Astronomic Avenger: Thank you. Okay. Perfect. All right. So, do you have any specific goals for this particular mock technical interview that you want to walk through or practice?

Efficacious Pirate: I did have a question in mind. Sometimes when I'm doing peer reviews with friends, I bring up a topic that I've been struggling with recently. But part of the reason I'm having this interview is because it's simulated, the fact that I want you to select the problem that we're working on. So if you have something from before, you can just paste it over here. And we can go through it.

Astronomic Avenger: Sounds good. All right, cool. Um, there's a couple of things. There's a couple of problems I'm going to share with you here. I'm going to start off slow, and then I'm going to get increasingly more and more difficult. So hopefully, that's okay. So the first question is going to be fairly simple. I'm just asking you to write a function. Here... Write a function that takes in two sorted lists and outputs a sorted list that is their union. The first solution that's going to come to your mind is to merge the two lists and sort them afterwards. So this is going to be part A of this question. I'll make it a little bit more complex right after, but I want to go through this and stuff. And one other thing. Just checking, since you have a machine learning background, do you want me to go into like, Python questions specific to machine learning?

Efficacious Pirate: I don't think that's necessary right now, because the interview that I'm expecting to have would just be a general coding algorithmic interview. And I haven't prepared for domain, you know, the sort of domain questions that asked about bias, variance, trade offs, and stuff for machine learning specific interview. Right now I'm targeting software engineering roles where knowledge in a specific domain is unexpected. But I appreciate you taking the time to ask. Since this is so simple, I think I'm going to coding right away.

Astronomic Avenger: Okay, sounds good.

Efficacious Pirate: And now I want to ask some clarifying... Before I dive into it, I want to ask a few questions about these two lists, right. So, by list, I'm assuming you mean arrays, right?

Astronomic Avenger: No, I mean, linked lists.

Efficacious Pirate: Okay. These are linked lists. Okay. And so, what comes to mind is that I have the node, and then I have a value. And you have the pointer to the next element. Is that what you have in mind?

Astronomic Avenger: That's right. Yes.

Efficacious Pirate: All right. So are elements repeated in these lists?

Astronomic Avenger: That's a good question. No, in this first iteration, I haven't put in any constraints. The second time, what I'm going to do is add in constraints of like, yes, you have to manage duplicates. And then also, after that, take away the sorting function. Like you can't use the sorting function. Right? You have to create your own sorting ability. So I was hoping to take this question, step by step even more complex, but if we want to make it like, difficult, and you're okay with that, then let's go with, yeah, you have to handle duplicates. You have to have your own sorting mechanism that you develop, as opposed to using the sorting function, or even order a function.

Efficacious Pirate: Yeah. So these lists can be assumed that they fit into memory? I'm sorry, I mean, to say that are they mutable or immutable list?

Astronomic Avenger: They can be changed. Yeah. You can change them.

Efficacious Pirate: Right. So class ListNode... Next is reserved keywords. I'm just trying to see... Okay. All right. So this is my definition of the ListNode. And so let's say that I'm going to write this and so... Get merged list. I'm going to take in two lists right? And I want to return the sorted list, right? So the union, what format are you expecting? Are you expecting a linked list, or are you expecting an array?

Astronomic Avenger: Linked list.

Efficacious Pirate: So this is going to be... Yeah, so linked list. Okay. So again, to walk through the algorithm that I'm going to use is I'm going to check the head of L1, I would have checked. So I'm going to say that... Is going to be the min of L1 and L2 and then I'm going to proceed, right? Then value is meant to be min val, right? So I have this temporary variable, which gets me the minimum of these two, which gives me a ListNode, which, so to draw it out, right... Can you see my drawing?

Astronomic Avenger: Yeah, I can.

Efficacious Pirate: Alright. Right. So let's say 1 3 5. And this is 2 6 8. Right? So my function is going to say, okay, fine, what's the minimum that I have right now? So I'm going to have a new list. Right? And I'm going to enter, what's the minimum? Okay. And so we'll have one start here. And two start here, right? So I want to determine which have a one. So I think that instead of using this compact min notation, it's going to be... a little simpler if I just handle it case by case, right?

Astronomic Avenger: So I think so.

Efficacious Pirate: And alright, so what I want to do is just going back to the drawing tab, I have this... Can you hear me?

Astronomic Avenger: Yeah, I'm here.

Efficacious Pirate: So I'll just keep going like this, like this, like this, you know, this is going to be my result. And once I reach the end, then I just reverse the list. Right? So that it's still sorted but in the opposite direction.

Astronomic Avenger: Okay, there might be a slight, essentially a delay on my screen, because I see you going up to your up to line 45. Your code is from line 34 to 45. Is that right?

Efficacious Pirate: Let's see. Okay, yeah, okay, fine. So let's say temp equals result. This way, I could just use a... right... And then in the end, I want to say result equals result dot next after the while loop is over. So yes.

Astronomic Avenger: That's right.

Efficacious Pirate: Alright. So now I just want to, you know, implement these two operations. But so this is going to fail, because there's no, you know, I haven't given it any value for val, right? So let me just give it, you know, so, minus int, or just zero, right? Just, this is a hack just to get around that. Notice, that isn't the best solution. Now, I just have to... And then outside of this, I can see that. All right. So after a lot more time than that should have taken, I can return result. So let's walk through this with an example and I will provide the example with say, the same example that I use here 1 3 5, that's L1. Yeah. And so we walk through it, then we see that we have our result is just zero, pointing to... I think pointing to None. And then once we get here, we just see that one is less than two. So then it becomes 0 pointing to 1, right? And again, I don't like the zero, but we get rid of it here anyway. So then L1 becomes three into five. Right? And so you've progressed like this throughout this until at the end, both L1 and L2 point to None. And so they just add this endpoint. And our result is going to be zero pointing to 1 2 3 5 6 12, right? So now I can see that there's an edge case here, which might, which you might run into right? Because you can't compare L1 does that and L2 does that if you reach the end of one of those lists.

Astronomic Avenger: Yeah.

Efficacious Pirate: Right. So that's going to be an issue that we need to close. So let's say that we reach the end of L1. Right? So we can, there's a quick hack on this. So you can see that if L2 is a one, but then this gets messy. Let me just write L1. So instead of just taking these, I can just do an empty check, right.

Astronomic Avenger: Yeah, absolutely, cool.

Efficacious Pirate: So wait. So after this while, I think I should change this to while to an or, but no, that's not going to change the result. So now you know, one of one of them is empty. Okay, so once you get out of this while loop, one of them is empty. I just check which one is empty and fill the rest.

Astronomic Avenger: So do you want me to give a hint?

Efficacious Pirate: Uh, no, not right now. I can figure that out. So I need to put this back up here. All right, this takes care of the reaching the end of one of the lists. Because otherwise, you know, you don't run into your five. Now, we should end up with this. And then what I'm saying is that since the zero is not really part of our solution, we can just say we move the pointer to go to one. And so by doing result equals result dot Next, we just have the answer. So walking through this again, this seems to be good.

Astronomic Avenger: How about, did we want to address the duplicates?

Efficacious Pirate: Right, so that's why I have this equal to, right.

Astronomic Avenger: So I think that it doesn't make it valid.

Efficacious Pirate: That's why this less than or equal to, right, I'm just picking picking one of them if both of these have the same value, right, then I pick the one from L1. It'll just take the one for the empty list at the end, right.

Astronomic Avenger: So let's see that L1 is here.

Efficacious Pirate: Yep.

Astronomic Avenger: And we have a L2 here, right? And let's say we have even more threes. Right? So this is saying that if we found that L1 and L2 are equal, then just pick the value from L1 and advance that forward. Now we see that L1 and L2 are the same. So we still advance L1 forward. Now we advance L2 forward. You take this to the end.

Efficacious Pirate: Alright, good.

Astronomic Avenger: It's possible to do this with immutable lists. It just takes a little extra memory.

Efficacious Pirate: That's okay. I mean, we're not trying to get to, you know, optimized code necessarily in the first go. I think this is good. I think we have time for one more question, unless we want to run through some random examples.

Astronomic Avenger: Yeah. Let's do one more since you mentioned it. How about one with like a binary tree?

Efficacious Pirate: All right. Sure.

Astronomic Avenger: Yeah. Okay. I'm gonna scroll down to 78. All right. So what we want, that's the binary tree that we have. You can pretend for a moment that it is pretty. Basically what we're doing is, what we want to do is ensure that we get an output array, that looks as follows. Line 85. So what you're seeing happen here is that we start at the root and go anti clockwise. What we're seeing happen is the root being a, we're going down the left flank. So a b d h, you see that? And then from there, we traverse the bottom flank. And that takes us to O, and then it will go up the right hand side flank. And it takes G and C does not bring back A.

Efficacious Pirate: So, what happens to E F, just forgotten?

Astronomic Avenger: Yeah, no, no, it's not forgotten. The question here is that you need to get this output at 85,right? In this array format. And the assumptions being made in this particular question, are that one, all nodes are letters. Two, you're only printing the boundaries, you are not printing, like inside the perimeter.

Efficacious Pirate: Printing a list?

Astronomic Avenger: Sorry, would you repeat that?

Efficacious Pirate: Adding them to the list?

Astronomic Avenger: Yes, adding them to the list. That's right. And the output is an array. And you can assume a standard tree data structure. You will have access to both children left and right. All of these are letters.

Efficacious Pirate: So all of the letters, we only added boundaries array, and is a standard tree data structure.

Astronomic Avenger: Right.

Efficacious Pirate: And so two children at the leaf nodes, so is it a complete binary tree? Or is going to be?

Astronomic Avenger: Yes.

Efficacious Pirate: So we can assume that this layer will always be full?

Astronomic Avenger: Correct.

Efficacious Pirate: All right. All right. P is complete. So we start at the root. And then we have to come up with this. Right? So for example, if our input was like this, right? And our output would be a b d e f d c.

Astronomic Avenger: Correct.

Efficacious Pirate: All right. So this isn't a simple pre order, in order, post order traversal. But let's see if there's any properties of this that make it easier to learn. This is a tree problem, we need to have some recursion. So let's try to do this by hand. Just to get a sense of how the algorithm is going to work. Right? So we start at a, then we went to the left child, right? And then at b, again, we're going left. So the pattern is go left until you reach the bottom layer, until we reach the base case. The base case is that material. And as and as long as you're going left... And so what I'm thinking is that we can go over the entire thing, but we'll have a check. And then what we can do is when, for adding these, there's no easy way once you're at edge to go to i unless you recurse, right? And then so, what I'm thinking about is traverse the entire tree in, let's say preorder, but only add to the list if, and then there are three cases. One, when you're doing the first side of the triangle, right? Now in the second stage, we just touched the leaves. Three, you're going back up the right. So I think that I can determine this. Now let's think about how we would go about doing this. So what properties can we observe here? Is this way, it goes this way. All right. So we're going to need... the approach that comes to my mind, and is to use a bunch of boolean flags. And then that meant that will, you know, determine our controls now. But for this last, but for the last one, so let's say that you do a b d edge, then you go i, then you go, e j, right? Then you go k. But you want c to be at the end of the array.

Astronomic Avenger: So, there is a definitive order. So you'll have to go left. Right, in your case number one, in line 101. The first side of the triangle is always going to be the left side, the second item this? Well, the second, you know, action item would be the bottom section, row 83. And the third will be, excuse me, the right hand side. Those are given, it's not going to shift.

Efficacious Pirate: So maybe three reversals of the tree, right?

Astronomic Avenger: Yeah, that's right.

Efficacious Pirate: First one is going to get all of the, you know, get the left side. The second one will get the middle place. So this is going to get a to h. This is going to get the i to n or i to o, all depends on the implementation. It will be easy to get the h to o and just remove the duplicates. And this just gets a c g o, and then reverses it.

Astronomic Avenger: Right. And remember that you won't have another a, right? You'll basically just have o g c. Yeah.

Efficacious Pirate: Reverses it to o g c a, then truncates the last thing, so yeah.

Astronomic Avenger: Yeah, the root element right.

Efficacious Pirate: So similarly over here. What you can do is a b d h. Trucnate the final element. And this one will just get h i j n o. And then at the end once you finish our tree traversals, you know, we'll have the three array, the left, the middle, the right. And we add and then this guy. And then we just, you know, concatenate them together.

Astronomic Avenger: Yeah, that's right.

Efficacious Pirate: All right. So let's start implementing this.

Astronomic Avenger: Let's do it.

Efficacious Pirate: I'm just writing out the pseudocode so that I can keep going forward. And this is going to be the bring it all together. Right. So let's say that left equals an empty array. And then we need a helper function. So the base case of this will be if not root. So I'm going to pass in an array. And then otherwise, I don't need an else here. Oh, but because we are assuming that this is a complete binary, you know, we don't we don't have to deal with validation, right?

Astronomic Avenger: We don't have? What's that? Sorry? Can you repeat that last statement?

Efficacious Pirate: Because we are assuming, I'm assuming over here that we are dealing with a complete binary tree.

Astronomic Avenger: Yeah.

Efficacious Pirate: And so once we reach the end here, okay. This will have none. So we'll have this, this, this, this. So root dot left and array plus root dot path, or better yet, array... Yeah. So, reason I put in here instead of array dot append is because I want to give, I want to pass this around in memory, but this becomes very memory inefficient, right? So I just changed the return and over this array dot append, root.val, right. So this way, I am what I am trying to modify the original... I'm passing by reference, right? Now I'm going to be modifying the original left, instead of passing left around, which you know, it's just gonna take too much memory, right? And then at the end over here, I want to say left equals left dot pop, is going to remove our last element. So we have to truncated the last element and we are left with a b d.

Astronomic Avenger: Okay.

Efficacious Pirate: Now we do our second traversal. Again, I have a tendency to talk when I'm writing everything, just because I feel like we're communicating better, you know?

Astronomic Avenger: Yeah, definitely helps.

Efficacious Pirate: And, of course, I don't want to forget to call the function. So this calls it, modifies it, and then returns it. Then I want to say leaves. Or I'm going to call it middle. And we'll call this leaf traversal... or middle traversal. What's a good name here?

Astronomic Avenger: Bottom is good. Yep.

Efficacious Pirate: I'm running in the middle, because when you think about it in terms of the array, this is going to be the middle of the array. But when you think of it in terms of the tree, this is going to reach the bottom of the tree. Right?

Astronomic Avenger: That is true. Yeah, absolutely. You're right, you are capturing all the leaves. But I know what you're saying here.

Efficacious Pirate: So the condition over here is going to be different. This is going to be just a standard binary tree traversal, right? And over here, I want to say that if the root exists, but the children don't exist. Now it's complete. So we only need to check one of the children. Because everything in this tree, except for the leaf nodes, are going to, you know, have it, so if you just check one side, you don't need to check the other side, you know. And this, I want to be clear, I'm just checking whether it's like, so then it goes through the entire, it goes here. So yeah, so it goes infinitely, because once we hit this, it returns and now we just want to say that. Okay. And for the middle, we don't need to do anything with it. And it's good, we have 10 minutes left, so I'm just going to write this out. So I can just erase that. Yeah. And then I call it on this and of course, over here, I have to reverse it and truncate the root element. So yeah, I'm going to reverse it, then truncate the root element. Alright, so let's walk through this, we're not done yet, we have to take an example and see if this implementation makes sense. In the interest of time, so that we have some time left for feedback at the end, I'm going to use the simpler case that you mentioned with a b c d e f g.

Astronomic Avenger: Okay.

Efficacious Pirate: And then I can have feedback at the end. So root is pointing to a. And left is empty. And, and this is just a definition. In Python, if you're not familiar, we just tend to define functions as functions. So this is just part of the core convention. Right. So we have left traversal, and then we pass in root, and we pass in this array. So we're here, we go... We go to our left value. So now we have a in our first iteration, you have a inside left. And next, we call it and then we are dealing with this b, right? And then we put b inside, and then we put d inside, right? Because we're not ever going to the right. And at the end we have a b d. However, since we like to have D inside, excuse me, when we use this bottom traversal, we remove d because we have it. And we want to have just a b, because we don't want to have duplicates. And the second traversal. We have the middle again, just kind of go to the question, we traverse the entire tree. And so if we want to discuss the asymptotic complexity, because we're traversing over the entire tree, it's O(n), where n is the number of elements in the tree. Or, it's O(2^L where L is the number of levels. Right? That's our time complexity. Our space complexity, well, you can't do any better than O(n), again, where n is the number of nodes because you need to, you know, in this case... And then again, you push this and d e f g in that order, you're going to push them in because of the traversal that I did with left then middle then right? If I did it in another order, then maybe it'll be messed up but definitely not when you're doing this preorder traversal. Alright, so then we have our third traversal with right traversal. And then it goes a c g. But we don't want a c g, we want g c and no a. So we will reverse it from a c g and it becomes g c a. Then we pop it to remove the a. And then we have a b d f g, and then oh... okay. So there's a problem here where this g is double counted. Right? So we want to do middle dot pop. Good that we walked through it. And now we just have d e f. Right? So a b d e f g c, then we concatenate them together, and we return it. And yeah, I think that concludes the time of the interview. I would appreciate any feedback. I think that I didn't start off too strong here. I struggled a bit, but for this problem I did better. That's my opinion.

Astronomic Avenger: I think, yeah, over time, you kind of started to see where this was a little bit more complex. Right. So I think it was good. You got the time complexity and space complexity absolutely right. And I think you essentially, did, you know, one of the things that you could always mention, right, you, you did it, but one thing I mentioned would have been like, okay, this is actually using the depth first. So, yeah, just, it'll help you put yourself in a better line if you say that. Okay, so then, in this case, you got, you know, the main. You showed a modular approach to problem solving. So that was really good. Because you broke it down into left, you know, the leaf nodes, and the bottom, and then the right section. So that was good. You used all the right, you used the pop function, for example. You used all of those right mechanisms to get there. And you entered it finally, in, you know, in the form that we needed, that was also good. You knew which one is the root, and then followed along the lines from the root. So all of these were good things that you were able to complete. You were able to check, you know, look at left and right and check if it's a leaf or not. So all of these were good. Yeah.

Efficacious Pirate: So room for improvement. What can I do better? And I think I can, you know, write a lot faster, I suppose.

Astronomic Avenger: Right. I'm just trying to paste my code for example, I actually did it in this form. And you can do this in many different forms, right? But in my case, yeah, this is a solid use. Yeah, I just did a deque and pop functions and I somehow a little bit more comfortable with append. That one, but same thing, right, broke it down into traversal of the bottom, left, right, all of these and, you know, checked what the expected output should be. So, yeah. I wanted to share that with you. Okay. So I think in the time that we had, the two questions that were provided Give me an idea, on what level of difficulty did you feel they were?

Efficacious Pirate: Easy to medium? Yeah. Definitely appropriate for the level of experience that I have.

Astronomic Avenger: Okay. Okay, so it's good. It's good. All right, sir. Well, um, do you have any questions for me before we put in feedback for each other in the form?

Efficacious Pirate: I'd love to, but my mind went blank now. I just want to enjoy.

Astronomic Avenger: I've been there, time for some coffee or tea or something, I get it. So it's been a pleasure to speak with you. And thank you for giving me the opportunity to be a part of your interview journey. I wish you all the best in your interviews and give it hell, right? Go rock this interview with Microsoft.