Interview Transcript
Factual Hedgehog: Hello? Hello, can you hear me?
Astronomic Avenger: Hey, can you hear me?
Factual Hedgehog: Yeah, I can hear you now.
Astronomic Avenger: Hey how's it going?
Factual Hedgehog: Good, how are you?
Astronomic Avenger: I'm pretty good, thank you. So yeah by way of introduction, I'm a software engineer at Microsoft. The team I'm on, what we're doing is that we're building a container to run SQL Server inside of. The idea being that SQL Server will run as a Windows process, inside the container, and the container will handle the system call translation. So yeah, that's a little bit about myself, what's your background?
Factual Hedgehog: Okay, I am also software developer at Microsoft and I am as your tools team right now, and the tool which I am working with, it helps deploy the user services on cube entities in Azure. And we provide a developer environment and that gives a creative remote debugging feature. So yeah, that's pretty much about it.
Astronomic Avenger: If I may, which building are you in?
Factual Hedgehog: 18
Astronomic Avenger: Oh you're in 18, I see. I'm in 43.
Factual Hedgehog: Yeah actually, um yeah lot of our folks were importing as well, plus 43, like earlier. I think it...
Astronomic Avenger: Right, right. We recently moved there.
Factual Hedgehog: Okay, okay. Cool.
Astronomic Avenger: Yeah um, I guess like what I have in the agenda is to basically treat those like a mock phone screen for Microsoft.
Factual Hedgehog: Okay.
Astronomic Avenger: Having said that though because you're an experienced engineer, but the disclosure would be that the phone screen for experienced engineers is slightly different, so the thing is for new grads what they look for is basically, you know, how quickly you can solve problems and things like that.
Factual Hedgehog: Okay.
Astronomic Avenger: So you're... they're judged on three criteria essentially: there is problem solving skills, coding skills, basically can they express themselves in code, so they say an idea in words and then can they sort of express the same idea in code, that sort of thing, and then communication right? So these three metrics are used to judge new grads, right? So the way it works is that each interviewer gets assigned a pool of candidates, so say ten or fifteen candidates during the peak season, like right now. What will happen is that each interviewer world basically get 15 candidates, and they can only recommend that two or three candidates be flown out for the on sites. Right, so it's a ranking based system.
Factual Hedgehog: Yeah.
Astronomic Avenger: So just by... so regardless of whether the questions are easy or hard, what will happen is that a candidate in just based on how their peers do. For experienced candidates however, the technique method is slightly different. The pool is smaller because you apply for specific roles, right?
Factual Hedgehog: Yeah.
Astronomic Avenger: So only say four or five people will apply for a particular team. So the pool is smaller and the metrics, and they have additional metrics that they use to judge experienced candidates. And that is basically, you know, are they good fit for the team, like what value can they add to the team. So the emphasis is less on your algorithmic prowess, if you will, and the emphasis is more on what value do you bring to the team?
Factual Hedgehog: Got it, yeah.
Astronomic Avenger: So because they don't... depending on what level, say for example if somebody's hired at like a senior engineer level, they expect the engineer to start contributing from day one, right? So there's no ramp up period. I guess, the metric that they'll judge you most critically on is basically, how much of a quick learner are you? For experienced candidates. But if you're interviewing for say a software engineer 2 or software engineer 1, then the process would be slightly different. There would be, they would expect there to be a ramp up period. So they wouldn't expect you to sort of, you know, be able to think on your feet and things like that.
Factual Hedgehog: Yeah.
Astronomic Avenger: But yeah, that's a slight difference, but I just wanted to sort of make sure that we're both on the same page. I won't be able to replicate that here, because you, know we don't have any of that, but we'll get a bunch of other problems.
Factual Hedgehog: Okay, that sounds good.
Astronomic Avenger: All right, so if you could... if you have any questions, please feel free to ask at any point, but if you don't have any questions at this point, then let's get started.
Factual Hedgehog: Yeah, I think questions which I usually are mostly about the position of the company and how does the process go, but that doesn't hold here.
Astronomic Avenger: I mean, I can make something up, but yeah that's a good thing to ask.
Factual Hedgehog: Yeah.
Astronomic Avenger: All right, so if you could go ahead and pick your language, let's get started.
Factual Hedgehog: Yeah, I would go with C #. I'm comfortable with that right now, yeah.
Astronomic Avenger: Sure, so I guess the first question we'll be looking at, it's a list manipulation problem. So you're given a list of integers.
Factual Hedgehog: Okay.
Astronomic Avenger: L and a number K. I'm going to ask you to write the function to partition L into elements that are strictly less than K, equal to K, and strictly greater than K.
Factual Hedgehog: Okay, so when do you say elements, what do you mean by that. Like into smaller sub lists?
Astronomic Avenger: Um, I mean, so the thing is that you're given a list, right? So the idea is to create segments inside your list, so when you say sub list, I guess like I don't mean... you cannot create new lists. If you could create a new lists, this problem would be trivial.
Factual Hedgehog: Okay, you're saying just like swap the values within the same list?
Astronomic Avenger: Yeah, and make sure that you have like three segments, right? Each segment does not need to be sorted, but overall like there has to be a segment which is full of elements that are strictly less than K, followed by a segment of elements that are equal to K, followed by a segment of elements that are strictly greater than K. Now within each segment, the elements don't need to be sorted. Sorry go ahead?
Factual Hedgehog: Got it. Yeah, I was trying to give an example here to see if I have got that correctly. So if I say 4 5 7 3 2 1 0 and if the element is K. Oh sorry, the element is 3, the K is 3, what I mean. But then, you're saying I should have it like 2 1 0 3 4 5 7, is that correct?
Astronomic Avenger: Correct.
Factual Hedgehog: Okay, okay, got it. So I don't have to partition it with something else as well right, like a space or something, like an empty...
Astronomic Avenger: No, no.
Factual Hedgehog: Just logical partition. Okay got it, so taking the same example, for now. Okay, so what I think.
Astronomic Avenger: So I just want to suggest an approach, so you could always sort the array, right? And it would automatically be partitioned, and the best sorting algorithm that you can use is probably mergesort. That will give you O(n log n) right?
Factual Hedgehog: Yeah, that would be one solution definitely.
Astronomic Avenger: But I guess we're looking for something better, right? So sorting gives us... That's also trivial, if you think about it, right? Are we doing extra work. Each segment, each partition does not need to be sorted within the partition, right?
Factual Hedgehog: That's what I was going to use, because you said it does not need to be partitioned, so yeah, it does not need to be sorted, like this does not need to be 0 1 2, it can be 2 1 0 as well.
Astronomic Avenger: mergesort would be wasteful in that sense, right? So, to create these partitions, I guess the runtime that we're looking for would have to be better than O(n log n), because...
Factual Hedgehog: That would have to be O(n) I believe?
Astronomic Avenger: Right.
Factual Hedgehog: Yeah, that would end up as O(n) I guess, so yeah.
Astronomic Avenger: Yeah, so we're looking for an O(n), like a single pass solution.
Factual Hedgehog: Mm-hm, so what I will do here is, I will try to traverse this particular array, like the first one, and I'll try to... if I am going for O(n), then I will just traverse it, and try to swap the values according to K.
Astronomic Avenger: Okay.
Factual Hedgehog: So let me get that. So...
Astronomic Avenger: That would work, but I would encourage you to think about it in terms of an invariant, right? In your array, from the very beginning. So you have an array of elements right? What I would recommend that you do is think about it in terms of having these logical separators, where basically the first separator will tell you where the partition of smaller elements ends. The second separator will tell you where the partition of equal elements ends, and the third separator will tell you where the partition of larger elements begins.
Factual Hedgehog: Yes.
Astronomic Avenger: So something like this. If you have an array, to create like these logical partitions right? To do that, basically the idea is to... the trick here is that you have a region of unsorted or unseen elements, like this region here, is full of elements that you haven't discovered yet, right? So I guess what I'm suggesting is a way to sort of keep track of these three partitions using pointers in your array.
Factual Hedgehog: Yep.
Astronomic Avenger: These are indices at the end of the day, right?
Factual Hedgehog: Mm-hmm.
Astronomic Avenger: You can keep track of where the index for each partition begins and basically perform the swap accordingly as you're moving through the array.
Factual Hedgehog: Okay, so if we do that... let's see... So far for example, if the smaller... let's keep every pointer pointing to the first element. So...
Astronomic Avenger: Not every pointer thought. The larger will have to begin at the end.
Factual Hedgehog: Um, so it's like 4 5 3 2 1 0, yeah. So the smaller, I will have it as at the space zero. And then I can have the larger one at the last 0 1 2 3 4 5. Yeah. Let's assume the mid will be 3 for now.
Astronomic Avenger: How will you know that though?
Factual Hedgehog: I'm just taking the half of that, right now. Half of the length of the array.
Astronomic Avenger: No but then in your array the mid tracks the end of the section partition where the elements are equal equal. Okay or stored, right?
Factual Hedgehog: Yes.
Astronomic Avenger: In your array, you don't know how many elements that is.
Factual Hedgehog: Yeah, that I agree. But I'm just trying to go with this initial values now and then calculate it over when I will traverse it through.
Astronomic Avenger: Sure, sure. I don't see how that will work, but sure. I mean, yeah.
Factual Hedgehog: I'm just giving a try, maybe I'll change my approach a little. So yeah, that's what I have as an initial thought in my mind, so I will prefer, you know, updating that when I go forward. So okay, so these three things, I'm just going with right now. So I will check. Yeah. So let's see... I will see the first values is 4, like when I'm traversing through the array, the first value is 4, so I will see that is greater than the value 3, so our K is 3. So that is greater than the value 3, and so I will move this, swap it, with our larger value.
Astronomic Avenger: Hey, so where are we at?
Factual Hedgehog: Okay, um, so I'm time to go through. I'm doing a dry run of the algorithm I have in mind. So I can just take you through that. So let's see. So in the starting, the case 3 assume s = 0, the largest one is equal to 5, the end of the array. I'm taking middle is equal to -1 right now, I'm still trying to figure out the middle one. Ok. So let's see. When I come here, s = 0, that was 4. So when I come here, my S is equal to 0, that is 4, I check the value is greater than K. Then I will go do a swap of 0 and I will move it to the L value, so I get 0 5 3 2 1 4. So now I will do L-- because the swap has been done, and there is a larger value at the L position, so I will do L--, so L is equal to 4 right now.
Astronomic Avenger: Okay.
Factual Hedgehog: Okay, so again my s is still 0, I will still check the same condition again if it is less than k, then I will do a ++, otherwise again the same thing to swap, which we did earlier. So right now here, the S is equal to 0, so it is less than K, so we will do S++, our S will be 1, so now I will do the same algorithm. I will check S is... if the value at S is greater than or less than 0. It is less than 0, leave it there. If it is greater than 0, I will do the swap again. So that will be 0... With L, so L value is 4 right now. 0 1 3 2 5 4. That is what I will get right now. After the swap. So here my S is equal to 2. So I checked it, it is less than our 3, our K. And then I will do S++, so my S was 1, now my S become S = 2. So in this situation, I will check. So on the S = 2, the value is greater than, is equal to K. And then if my mid is equal to -1, I will assign mid to this value. So I'll have my mid over here.
Astronomic Avenger: So I would say like the mid that you have, right, you can use that to iterate through the array. Use that as the current index if you will. You do that, it then becomes much more straightforward. Same idea that you have, but using mid as your current index.
Factual Hedgehog: I was using S as the current index, so...
Astronomic Avenger: You're using S, that's fine, but what I'm saying is, yeah you can use S, but I'm saying is you're going to have to adjust your mid accordingly. So the idea is that... Okay so this is... there are three cases right? The current element is less than your K, right?
Factual Hedgehog: Uh-huh.
Astronomic Avenger: This case, it should be swapped with the smaller, right?
Factual Hedgehog: Yes.
Astronomic Avenger: And your current pointer should be incremented and your small pointer should be incremented as well.
Factual Hedgehog: Okay got it. Yeah, so yeah... I think... And I can leave mid down there itself and not swap it with anything, and just move to the next element.
Astronomic Avenger: Yeah, yeah. So there are three cases essentially. So the one case is that the current is smaller than K right? The other case, so when current is smaller than K, you swap it smaller and you increment both current and smaller right? You move your walls up.
Factual Hedgehog: Yeah.
Astronomic Avenger: Now the other case is where current is strictly greater than K right? If current is strictly greater than K, all you do is you swap with the larger, you decrement your larger, but keep your current the same. That's the trick, right?
Factual Hedgehog: Okay, so I think I have kind of... yeah, that in mind now. I got that of how to handle the mid thing.
Astronomic Avenger: Let's write some code, I think it would become clearer as we write the code.
Factual Hedgehog: We can start with the code. So I will declare three elements, mid is equal to zero, start is equal to 0, and and is equal to array.length. So actually I will just go through the loop, I'll set that condition later on, what I feel the condition would be if mid has hit larger, that's what I feel. So till that time, you will still go. If mid is equal to larger, then I think we have achieved, so that's one. So what I will do is, I will go through mid. Okay. So if any of middle less than K, then i'll... So i will write another function of swap, I'm just assuming it exists. So I will swap array of S and array of min. So 4 5 3 2 1 0. Okay, let's see if that works. Okay so, if... I just want to go to through the algorithm once and see if it works. Okay so, I have four... so I guess going... so the mid is zero, the S is zero, and L is five. So then the mid is less than larger. I'll go inside and say if array of 0, that is 4, is less than K, it is not. It is greater than K, then I'll swap it with L. And so the L is 5, so I will swap it with...
Astronomic Avenger: I think you're missing two things, um. Looking at your function, you're missing a few key things. One is that... what you have to realize is that you are starting with your mid at 0, right?
Factual Hedgehog: Uh-huh.
Astronomic Avenger: The thing is, when you encounter an element that is strictly less than K, the idea that you have to increment your mid well, you're not incrementing your mid...
Factual Hedgehog: Yeah, that I will do at the end, like I was thinking of doing it here.
Astronomic Avenger: No that... you cannot do that there because you're not supposed to increment the mid, like for this case.
Factual Hedgehog: Yes yes yes yes okay.
Astronomic Avenger: Because then you might run into an example or a case where say for example you have five here, and then some elements, and your larger is seven. L is equal to seven and mid is equal to five, okay? Now your K might be six. Actually K might be four. Let's say K is equal to six right? Or four. If K is equal to 4, then you're mid, arrays mid is strictly greater than K right? And you swap the two, right. So you take this and you swap. Now your mid is seven, okay, and your larger is five. But then you decrement your larger, so your larger become something else. But your mid should still be the same, because you might have to swap it again.
Factual Hedgehog: Yes.
Astronomic Avenger: So in this case you increment the mid and the other case you don't, and the other case that you're missing is that if..
Factual Hedgehog: If it is equal, then I have to decrement my mid.
Astronomic Avenger: Exactly exactly.
Factual Hedgehog: Yes, I was about to come to that because I was... the other way I had in mind, it was the use of S, so I had this one stuck in my mind.
Astronomic Avenger: Oh, I see. Okay.
Factual Hedgehog: Yeah so because if you see in the lower of like an example I have taken, the same thing I'm doing if it is S, then I am incrementing S, but in case of L, I am just decrementing L and not incrementing S, so that's why like if we just switch that with mid, so the same thing holds here. So in this case of greater than, we don't increment mid.
Astronomic Avenger: Your L has to be -1.
Factual Hedgehog: Yes.
Astronomic Avenger: And this will work now.
Factual Hedgehog: Yeah I also like, while I would do the dry run, I would have liked fix some things.
Astronomic Avenger: Of course. Yeah. We're almost out of time. Before we move into the feedback portion, I guess, you know let's quickly go over the runtime and the space.
Factual Hedgehog: Sure. Ah the space will be constant because we are just using space for swapping, nothing else. I believe, yeah. And the time would be... I'm traveling like sequentially, so I think it's O(n) only, it's yep.
Astronomic Avenger: Yeah, it will be O(n). Okay yeah, so that's good work. Now in terms of feedback right, so I think the biggest issue I see is that, and you know I'm completely convinced that you know you can solve this problem in all paths, right? But the biggest issue I see is with the time management.
Factual Hedgehog: Okay.
Astronomic Avenger: This question is definitely an easy question. Easy question in the sense of you know like a LeetCode easy question. Why, because this is like the partition phase of quicksort.
Factual Hedgehog: Mm-hm.
Astronomic Avenger: So the K that you're giving here is really the quicksort pivot right?
Factual Hedgehog: Yeah, yes.
Astronomic Avenger: So this, this is something that should take you at most say five to ten minutes, something like that.
Factual Hedgehog: Okay.
Astronomic Avenger: So if you take like 20, 25 minutes solve this problem, what will happen is that you will severely restrict yourself or hamper yourself from demonstrating your skills in some other areas. I like the way you solve the problem, go in for dry run and then sort of coming up with the code, but that is a very time-consuming process. If you can do that faster that's good. But if you can't, then I would recommend that you actually go straight into the code. I don't mean like your algorithm has to be perfect from the very beginning. I mean that you'll have a version one, right? And then maybe you'll do a dry run and change some things. What I'm going to say is that I think you started coding really, really late.
Factual Hedgehog: Okay, got it. So like I gave you the example in the starting, so you are like suggesting me to directly jump in the code, and then talk through that right?
Astronomic Avenger: Either that or if you're going to go for an example, do it much, much more quickly. I think you took like 10 minutes on that example, but yeah, we didn't get any information out of that example.
Factual Hedgehog: Yeah I agree. Okay got it.
Astronomic Avenger: What I would say is that I think you have to be more economical with your time and you know, really analyze, you know, only spend time in areas that will help you move forward in terms of solving the problem.
Factual Hedgehog: Got it.
Astronomic Avenger: But problem solving wise, I think you're in good shape. C# like being able to express yourself in code, I think you're in good shape. You know, you're using some fancy C# stuff with references and things like that, so I know for a fact that you know, you're comfortable expressing your ideas in code in your language of choice, so that is great. Problem-solving wise, like the basically I knew from the very beginning that you were on the right track, that you know by running through a few examples you would be able to sort of come up with the solution, I could get that right? But I also got the feeling that you are a bit rusty, right? But you hadn't done these things in quite some time. And that shows. So being able to come up with the algorithm is one thing. Being able to do it really quickly in a time efficient manner with somebody, you know, looking over your shoulder, that's another right? So it seems to me that you're a little bit rusty, which is good. It's good in the sense that it can be fixed easily, you know just by practicing more. But I definitely do think that you know you need a little bit of practice when it comes to the interviews. The speed is a bit of an issue.
Factual Hedgehog: Okay got it, I'm sure I'll try to take care of that, thank you.
Astronomic Avenger: Yeah, so I know that's a little bit harsh, and you know we've all been there right? But there's no consequences here, that's great. So, you know, if you have some time, if you spend like an hour every day solving these problems, right for four weeks, then if you come back and do this again, or if you sort of just you know... you'll start thinking more efficiently, and that will show. I mean that's the feedback I have. Do you have you have any questions?
Factual Hedgehog: Yeah that's really good, and thank you for that. That was, yeah, that was a good feedback.
Astronomic Avenger: Yeah, you're welcome, anytime. Do you have any questions?
Factual Hedgehog: So yeah, for the like interview point of view, so if I... so I always had this question like if I'm going through the... so do you guys suggests, you know, writing the like compiled code in the first run and then going for like, or like if I write some code and now I see, oh there's an issue, like while I'm doing the dry run and I found some bugs and I fixed it, so does that count as a negative thing? Like should I have not have those in the first run?
Astronomic Avenger: In general no, but like your code would have compiled from the very beginning. I think your syntax was great, your syntax you know would have worked. I think you were missing a couple of cases so your algorithm wouldn't have worked, right? So they're not expecting that you know that from the first line of code to the very last line of code that you code should be perfect, that's something that's not expected. What's expected is to basically break the problem down into small pieces and solve each piece in turn. If you miss a piece, that's fine come back to it and solve it right? But I think the approach you took was to basically look the whole problem and tackle the whole problem at once right? But if you broke it down into smaller pieces once you had the three pointer approach, you're set. You had a three pointer approach. How do you move the pointers, that's a different question. What is the approach? The approach must agree you have to use three pointers. The other was how do you manipulate the three pointers? That's a different question. Now for, how to manipulate the pointers, there are three cases right? Within the integer, there are always three cases, less than, equal to, greater than right? How do you handle each case? So what I would ideally have liked to seen is to basically... is for you to break down the problem into these two questions and answer each question in turn. Does that sort of make sense, like how the problem can be broken down into smaller pieces?
Factual Hedgehog: Yeah yeah, I agree with that, yeah. I could have like started that way as well. Like the starting when I while I was giving you the example like what my approach was like while I was explaining to you the example down there. I was kind of getting my algorithm like you know, I was trying to build my idea. Of course I could have jumped in the code, but it wouldn't have given me anything because I didn't have anything in the mind. So I was not going to build an algorithm which I can't right?
Astronomic Avenger: Right right, of course. And that makes sense. If you have to do that, definitely do it. But you might want to be sort of... be a little bit more efficient when doing it with time.
Factual Hedgehog: Got it.
Astronomic Avenger: But also when you're thinking about the algorithm, like just take a simple example. I think the example you took was too complicated. See, you could easily have come up with the algorithm using a list that had just like three or four elements right? That would have Illustrated the main point.
Factual Hedgehog: Okay.
Astronomic Avenger: So what I'm suggesting here is that not to sort of come up with the algorithm using a specific example, think of a general example right? Think of an arbitrary example but that illustrates the main point. So you see how on line 41 or 40. How we did that, so you'll see that we only use two elements right? But we came up with a very important idea here. Because what I often see is that people sort of start with an example and then they write an algorithm for that example, but then when they try to sort of use a different example it doesn't work because the algorithm is tied to that one example.
Factual Hedgehog: Yeah even like, yeah I have had that issue sometimes. So you want a general approach, not a specific example.
Astronomic Avenger: Yeah, so go with the general approach. Take a step back, look at the bigger problem you're trying to solve. Identify the main points of that problem. That is what I would recommend.
Factual Hedgehog: Sure yes, that makes sense, and I'll keep that in mind, and you know try to do that most of the time.
Astronomic Avenger: So any other questions?
Factual Hedgehog: No that would be all for now I think, yeah I've got most of my questions answered already, so yeah thank you for this.
Astronomic Avenger: Yeah no problem, and I had a... it was great talking to you. Thank you for doing this and hopefully we can keep in touch, and if you're still practicing, I'm also... I'm not sure, are you actually interviewing like internally or externally?
Factual Hedgehog: I'm actually looking for internally first and then if I'm looking for a team change right now, not like yeah I'm just exploring right now, in any case. So I just started practicing and everything, so in case there is a internal switch I do or... an external switch. So I'm not like, I haven't... there's nothing like finalized or decided yet.
Astronomic Avenger: Okay, well I kind of like to... the thing is I'm also looking externally, so if you would like to sort of get together sometime and solve problems, I'm open to that as well.
Factual Hedgehog: Okay yeah, then that sounds good, yeah. So you, which position are you at right now? Like which level?
Astronomic Avenger: I'm at level 61.
Factual Hedgehog: Okay, I am at level 61 right now, so yeah same.
Astronomic Avenger: I see, I see okay okay. Um you said tools right? Azure tools?
Factual Hedgehog: Yes Azure tools.
Astronomic Avenger: Right, cool cool. Well hopefully we can keep in touch. And I wish you all the best. And you know, if you want to solve problems together, let me know.
Factual Hedgehog: Yeah, we can do that, thanks.
Astronomic Avenger: Cool, sounds great. Well, nice talking to you, and all the best.
Factual Hedgehog: Same man, thank you, you too.
Astronomic Avenger: Thanks, take care. Bye.