JavaScript Interview with a Microsoft engineer

Watch someone solve the k closest points 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

K closest points

Interview question

1) Find the K closest points to a vertex. 2) How would you modify the solution if the input was an infinite streak of points?

Interview Feedback

Feedback about Nimble Pumpkin (the interviewee)

Advance this person to the next round?

How were their technical skills?

4/4

How was their problem solving ability?

3/4

What about their communication ability?

4/4

You did really well. If you perform like this on your future interviews I have no doubt that you'll get hired at any of the jobs you're interviewing for. You have solid communication skills, you walked through the problem to make sure you understood what I was asking, went through most of the edge cases and made sure you tested it. The only thing I wish I saw (during part two where you kept track of only k elements) was to use a priority queue / max heap to keep track of just the k closest points in O(NlogK) time. Overall, awesome job. I wish you the best of luck in your future interviews.

Feedback about Indelible Raven (the interviewer)

Would you want to work with this person?

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

I liked the question, I thought it was a good way to quickly assess someones thought process and see their coding abilities. Overall, you did a good job giving direction when necessary. I was a bit confused by the extension you asked to the question at the end. I was trying to ask some clarifying questions but overall it just wasn't super clear.

Interview Transcript

Nimble Pumpkin: Hello.

Indelible Raven: Hey, how's it going?

Nimble Pumpkin: It's going pretty good, how are you?

Indelible Raven: I'm doing all right. Been a bit sick, so I'm just getting over it. Hey, have you used this platform before?

Nimble Pumpkin: I have not, this is my first time, how about you?

Indelible Raven: I've used it quite a bit. So, let's see. I want to basically go over how it works quickly. You already set it to JavaScript, so good. So for me it's the typical like 45-minute tech interview, but since intro is five minutes and Q&A at the end is five minutes, it's really 35 minutes of tech. So we'll get started with that, I see you're an experienced engineer, and then at the end I could give you your feedback and then you get the chance to ask me any questions on it or we could discuss it. Sound good?

Nimble Pumpkin: Cool, yeah sounds great.

Indelible Raven: So I'm gonna start you out with... well I don't know JavaScript so it's just kind of a guess. So I'm going to give you a point class, or you can write it as a 2D array or 1D array or whatever, so this would just be like an X and Y right. And then knowing that, I'm going to give you a list of points. So that will be something like (0,1) (1,-3) (2,4) (1,1) (13, 2). And I'm going to give you the point organ which will be let's say (1,1) and then K let's say for example 2. What I want you to do is find the K closest points around the origin based on distance and just return those points. So in this case it would be like (0, 1) and (1, 1).

Nimble Pumpkin: Okay. So find the... you give me K, and so I want to find the K closest points, got it. Okay cool, so I will just probably comment all of that out because that's not JavaScript.

Indelible Raven: I don't know JavaScript, so you have to translate that yourself to whatever JavaScript does.

Nimble Pumpkin: Yep, got it, no worries. Cool, so I think it seems pretty straightforward to me. So I think the first thing is figuring out the distance formula, which the distance between two points I believe is (b2 - b1)^2 + (a2 - a1)^2 and then square root that term. I believe that's the formula for distance between two points, so we'll start with that, I think that's very important. So the first thing I... so I'll think about what the algorithm looks like, so I've got a list of points and you're giving me an origin point. So I think I'm just going to start by translating what you've written into something that's a bit more JavaScript-y. So the function first of all is find K closest points and you're going to give me a points array and you're going to give me K and you're giving me an origin, presumably as a point inside of the points guy.

Indelible Raven: It doesn't have to be. It could or could not bet.

Nimble Pumpkin: Okay got it, it does not have to be. So the point, the origin isn't necessarily inside. So one of the points could be the same as the origin, the distance would be zero, and that would be one of the closest ones presumably.

Indelible Raven: And there can be duplicates as well.

Nimble Pumpkin: And in the case where there's duplicate distances as well, say K is one and there's two that are the same, which do you want me to return? Or do you want me to return both?

Indelible Raven: Um, it doesn't matter just return up to K. So if you have duplicates, then you can just return partials. If you have three but you have two left, just return any of the two.

Nimble Pumpkin: Got it, cool. And so I thinking off the bat that my formula is basically go through the array of points and to iterate over the array of points, calculate the distance from the origin for each of them, and I guess I can... I need to map the distances to the points that they originated from and then I can sort the array based on the distance. So basically that looks like... I mean that's one way to do it. And the time complexity of that would be O(n log n) because sorting is `O(n log n) and iterating once is O(n) and O(n log n) is more, so it's just O(n log n). So that method would yield O(n log n) with probably O(n) space complexity as well, that's... does that make sense to start with?

Indelible Raven: Yeah, that makes sense.

Nimble Pumpkin: Okay, so I guess there's edge cases as well which I can handle which are like there are no points, if no points array, I probably throw an error. So there's that. If there are less points than K, less than or equal to K, then I can just return points. That's kind of a quick exit early strategy. And I guess you want me to throw an error if points are less than K, because you want K. I could handle that different ways depending on what this is being used for. So potentially if it was less, I might want to throw an error and say not enough points. If it's equal, I might want to return points. So I don't know how do you want me to deal with that?

Indelible Raven: Let's leave it at that.

Nimble Pumpkin: Cool okay. So there's that. So I'm going to represent a point as kind of like you had it, a point is XY as an array, and the points is essentially an array of these, like what you had below. And origin is going to be one of those points as well. So I will first start I think at this point... actually I'll just do the iteration. So I'm going to have like a stub for a function here that's calculate distance from origin to points and I will implemented later using this formula here. Alright. Okay so I'm now going to, as I said, iterate over this array points array and get the distances added into points distances like this. I guess actually there's another possibility for an error, which is that there's no origin, so I'll just throw an error for that as well. Can you see my cursor by the way or you see what I'm typing?

Indelible Raven: Oh no, I see the cursor and everything you have.

Nimble Pumpkin: So if there's no origin we throw an error. I like this practice, this is nice. Therefore it matters. So here's a point, I'm going to map over this and distance to origin is going to be this guy. Origin point and now I'm going to return the points and the distance will be... Cool, so that'll just like... Okay, cool so now I've got my points with distance and so at this point it's an array of guys that look like this. Now I can sort this. Okay so we want the smaller distance to be sorted earlier, so that would be one a negative. So if I do A minus B, so B is five and A is 3, I want a to come out in front, so I want it to be negative. So that's corrects, A minus B, 5-3, that would give me negative two which would put it in front. Yeah, that's correct. Cool, so now I've got my sorted points and I can just basically slice off the start of this array from 0 to K. Okay, so do you want me to implement this?

Indelible Raven: Yes please.

Nimble Pumpkin: Okay, cool. So this will be.

Indelible Raven: So I have a quick question on line thirty. Would it be A-B or would it be something else, because you're doing a point and distance.

Nimble Pumpkin: Oh yep yep yes yeah. So this would be this, so it would be the output of this and I guess also then I need to modify this guy as well to handle that, so this is actually point in points. So once I slice off the first K elements, I mean I'm not over the array that I created and just pull the point out which is what you said. Cool. Alright, now this guy is... So it's going to be now B is the point, we'll go with this for now. Yeah I'm pretty sure it's point minus origin, I can double-check that after. Okay. So I wanted to do this, this is square rooting that plus... So doing b2 minus b1, or this I guess is a a2 minus a1 squared and b2 minus b1 squared and adding them together and square rooting that, so that's the distance. Okay, alright. So I guess I'm pretty sure that this is the right order for these, I could double check that. I can come back to that at the end. I'm just going to kind of walk through a... I guess your example that you had down here, and see what this looks like. I might... cool.

Indelible Raven: And you're able to run here as well, so you can give it a shot.

Nimble Pumpkin: Oh, okay cool. Okay I guess I got to run this then. Okay, so let me just translate your points then into JavaScript. I'm just going to put this into a code editor so I can replace all that curly braces with square braces.

Indelible Raven: If you know vim, you can do it here as well.

Nimble Pumpkin: You can do that here? I'm not super good with vim, I know all my hotkeys in vscode, I'm not... I'm like, I can use vim but I'm not an expert. I can walk around the code and move some stuff but I don't know advanced parts. So I mean in the real world I would be writing test cases for this stuff.

Indelible Raven: I think you can do that here as well. There's Mocha.

Nimble Pumpkin: There's Mocha, sorry?

Indelible Raven: Where the JavaScript is, there's an info button. It runs the built in unit test library, if you want to use it.

Nimble Pumpkin: That's cool, neat. Well I made use out of the fact, I'm just going to run this, just see what it does. But I generally do write test cases. Okay, it didn't work. Okay, so um I would have started...

Indelible Raven: Did you say worked it worked or didn't work?

Nimble Pumpkin: Oh sorry, am I reading this wrong? It outputted. I'm not seeing the whole thing. Am I missing something? Oh okay, a line was getting cut off, sorry I didn't see it. Okay, it looks like it did work based on the answer you gave me, which was what we're seeing there, so it looks like it did work. Now that's like a great thing to see that it worked, but generally I would write test cases which I can do, I would have started by testing this function on its own. Let's see how the mocha test work. Okay so I can just fit it back. So before I do continue, I mean this does work, it looks like for this use case at least. I can write tests for it, I can try to potentially optimize the solution more, what would you like to see me do?

Indelible Raven: I would like to see it optimized.

Nimble Pumpkin: Okay cool, so alright. So what we have here as I mentioned basically at the start is that we have an O(n) right here in terms of time complexity and we also have space O(n) as well. Okay there's that. We've got an O(n log n) here, O(n log n) there. Another O(n) space. Technically actually this does do an in-place sort but anyways still O(n). Another O(n) and then, yeah we slice a map again, another O(n), so like I said, coming out to O(n) space complexity and O(n log n) time, so can I improve on this. So I think that the answer is yes, so I do need to iterate over every point at least once I believe because otherwise I don't know if it's the closest or not and I believe I need to calculate the distance for each of them. What I can do though is actually track the K closest points as I iterate over it, so I don't actually need to do this sort. I think the code is a bit cleaner this way but I can optimize the time complexity down to just O(n) by basically doing like greedily storing the top points along the way. So if I go with this idea, actually let me just copy this before I start destroying it. I'm just going to go down to the bottom.

Indelible Raven: I'm kind of curious, where are you at in your interviewing phase.

Nimble Pumpkin: So I haven't done any phone screens yet, I basically done a bunch of preliminary calls. I have several phone screen setup, as well as a couple on sites starting like next week I have several phone screens, and then I'm targeting some on sites in middle of November.

Indelible Raven: Nice.

Nimble Pumpkin: Okay, so here we're going to have K closest points, that's right. And I can use a for-loop, I think they're really ugly, but it does let me end earlier if we want to like really optimize it. I did actually just have a thought if I pause here because I think I could actually take a... oh no, no never mind, I have to go through all of them. Okay so do that, now we got the point is that is at i, calculate the distance. We've got the distance, now... okay so I've got the distance, like I said I can just kind of push these into the array, but that means every time I want to... every loop through every point that I track, I need to essentially look at all of the points inside of K closest points to see if this one is less. So I can also actually store... how can I do this? I can store the current max that's within the min, within the closest points essentially, which lets me know immediately if the current point is going to be less than or equal to that value and so it would be... Yeah this is essentially the max distance that's the closest because what we're looking for is K closest, so if the closest were like three four and five, the max would be five, so that if I found one that was, you know anything less than five essentially, I would replace five then with like two and then I would update the max distance to four at that point. So that does allow me to not have to look through this every time, it does just mean that when I want to move something that I've got to find it and remove, it which is like up to K but it should be faster still. Okay, so now if cur max distance, there's some funny JavaScript for you. So I have to check if max distance is null or it's just origin is less than or equal to cur max distance, then I will have to add this point and potentially evict another point. Okay hold on, so yeah there's a couple of things here. So yeah so inside of here if the max distance is null or this one is less then we want to add the point. Now we want to check if there's room to just add the points or if we need to evict one, that was already in there. Push in same thing that I did before, I'm gonna have to add the distance and once I've done this I should basically be able to get rid of this guy. Okay, so if the distance is null because this is much less. Okay, cool. So basically here we're saying if there are less than K points in there we can just push it in otherwise we need to first evict a point so I'm actually going to just change this ellipse to make it a bit clearer. I'm going to change this to if it's greater than or equal to, I guess just equal, but can't hurt to be safe. If the points are greater than or equal to K then we need to remove the max point, so here we'll index of max points is equal to this guy. And now I have a shadowing variable here. I would also probably split some stuff out into functions, I can do that after, but this is getting pretty ugly. Okay so if the distance to the origin is equal to the max connect systems, we can return this. Now it is possible that there are duplicates as well here, I'm just going to note that down: possible duplicates. That will find me a point, not necessarily all the points that are at that max and I can now essentially slice it out. I think it's probably easier to just let me reassign this array equal to... can't remember splice mutates or not. So I actually don't need to do this, splice mutates the array. So that will remove that element essentially from the array and now I can push this guy into that array. Now because there are duplicates, I don't... Not even because there are duplicates, I essentially now need to find the new max distance to origin, so that I will do here.

Indelible Raven: Let's stop with this question, I kind of want to go push it a little bit further. For the next part, it isn't really about code, but more about your problem solving, an idea that you can come up with. I want to change the inputs of the list of points to a stream of points where the input is infinite. So there's an infinite number of points coming in. So I don't know if you know how a stream works but it basically it'll start over and then you have the points coming in. What are some thoughts on that of how you attack of that? How do you return the K nearest neighbors when it's happening?

Nimble Pumpkin: Yeah so like can I use like an observable for this?

Indelible Raven: What do you mean by that?

Nimble Pumpkin: Like as the data... I mean so I'm pretty familiar with like Javascript so when you say you know a stream, you know I would model it probably as an observable. Essentially allows me to operate on a stream of data using you know things like map and reduce buffer etc. So anyways, that's just I'm going to think a bit more about how this will work though. So we've got a stream points coming in and we want to find K, so K is fixed but the points are just coming in over time and eventually will potentially complete, I mean I assume it has to complete at some point if we want a result to this. Otherwise I could probably just return the top, I mean I can return the top K to date if you want me to do that, kind of every time a new value comes in I can return the top K like up to this point, the K closest, or I can wait until it completes, if we know that it will complete, which would you prefer?

Indelible Raven: The input will never end, so what I want is it to return the top K at a given point, it's to at some point quit and say this is the top case.

Nimble Pumpkin: Okay um and how are you going to notify me that it's done, so at some point you want to stop. So if you give me a stream.

Indelible Raven: I was gonna say I want you to decide when to quit, so I want you to come up with a way to stop it, yeah. Something that says hey I think I've seen enough, here's the top K.

Nimble Pumpkin: Sure um yeah I've got you know... I can do that in different ways. I can just stop you know when a certain number points come through, I can do after a certain amount of time. You know, either anyway, so I stop it at some point and return the top K. I think... so basically what I came up with here was sorting originally was using a sort and then we kind of moved to this one, it's sort of greedy algorithm which makes more sense when you're looking at an infinite stream of points obviously you can't just like sort them with an infinite stream, you just want to store the top results that you've seen to date. So this sort of approach makes a lot more sense. Yeah, so it's going to be something similar to this, this idea but essentially just translated to using streams. Do you... can I use? Like how do you want me to model this? Like I can use rxjs, which the API I know, I don't know if I'm able to like require random libraries here, I don't know if you want me to try to like... because I need to model the stream somehow, I mean I can spend time doing that, but I don't think that's a great use of time.

Indelible Raven: Rxjs works, I don't actually know how that works, but yeah by all means feel free to use that or something else.

Nimble Pumpkin: Am I able to like include stuff here, or it's just library.

Indelible Raven: Actually I don't know, but yeah I feel free to try.

Nimble Pumpkin: Okay, yeah it doesn't look like I can include just like my own like any NPM library here, so it won't run, I mean I can try to just require it and see what happens. It might just blow up or maybe it'll work. Let's try it.

Indelible Raven: It's not really about code, it's more of your thoughts on...

Nimble Pumpkin: Okay yeah, got it. Okay, you want me to just... okay I mean I would, so I would use rxjs for this, which allows me to basically model a stream input as well as operate on it using, you know, any... there's built-in operators, I can write custom ones as well, but essentially the thought process behind it if I were to kind of write steps is to... at each point we want to... we want to pass to the front to the the operator essentially in my stream, my stream operator will want to receive the top K points to date, as well as the current point that I'm looking at, and I would basically do this logic here, just kind of inside of a stream operator, and then I would update K, so how would that work. Essentially saying that... yeah the trickiest part here that I'm thinking of is trying to think of how I update K and kind of pass it back into the stream, into my operator. I actually know I can do a... the operators can be stateful, so I would essentially write a stateful operator that has like a K in it, but I initialize with the K, and as it receives points it's basically just kind of looking through its internal like K closest points array, you know doing this basic logic here to determine if it should be evicting a point or adding the point into it and at some point later in time when the stream completes for whatever reason and I can set that up like I said different ways, but whenever the stream completes, and it can complete say based on you know, ten minutes have passed, or whatever we want to do, I would just return that points array that I have. Does that make sense, does that answer your question.

Indelible Raven: That makes sense, um so I'm not sure if I caught all of that of when you quit, yeah everything so far made sense. So is there like some sort of like error ratio with that, saying hey here is what the top K are but with potential error ratio to say hey I think I've seen enough to justify the top K.

Nimble Pumpkin: Right, yeah. So I mean what is this if I'm going to be talking about error rates, like what is this a stream of that I'm looking at in order to determine like... you know when I'm stopping the stream, so you know what I've explained so far is like how I would do it from a technical standpoint, in order to basically say I can return the top K, great - so we've got that covered, so I guess this part of the question more pertains to what is the like context of the question, what are these points, and what is this stream and based on that I'll try to give you an answer.

Indelible Raven: Well the points is just the input stream of X Y coordinates, or X Y Z or whatever right? So what I was thinking here at least my perspective is hey what if we have some sort of like sliding window, pr hey I've seen so many points that I've seen the max of this, so I feel confidant returning to you or something like that. Any thoughts on that?

Nimble Pumpkin: I'm sorry so you're saying we have a sliding window and based on previous windows and... like, I don't quite understand. Yeah, so based on the windows I've seen to date trying to determine if it's a good spot to... or like what the error rate is on like... if it's a sliding window, then I'm just returning the top key points within each window right? So what do you mean, like I'm a bit of a bit confused by this question, by this part of the question.

Indelible Raven: Yeah so... trying to put it in a good way. So my thoughts are this. So let's say I have this sliding window of two things. So say a number of points, let's say the first one would be 1 billion points, next one will be max distance. I'm going to start out with like 0.001 away. And I'd say if a billion points in my max distance is 0.001 then we're done. If not, let's increase and say this is now one trillion, but now this is 0.1 or something and so on. So it kind of keeps shifting over until both are satisfied, right?

Nimble Pumpkin: Ok so we're looking to end... so it's based... you want me to end based on like what... satisfies each criteria essentially I guess is the question? So you either want to see a max distance like over a certain value, um like what so when I visited a billion points and my max distance is 0.001, like what... why do I decide to continue.

Indelible Raven: Uh well if it's less then you just stop, but if one of those is over then you shift over right?

Nimble Pumpkin: Oh I see I see, I think I understand. So you're saying that that's the threshold essentially, you're saying that 0.001 is kind of a threshold that we're hoping is going to be under and if it's not we want to then like take a bigger sample size and then threshold will increase as well?

Indelible Raven: Yep, at least that's my thought process. So that was more of a discussion of seeing, hey what would you do in this case. So let's stop here, it's been roughly thirty five to forty minutes, and now I can give you your feedback, we could discuss it, you could ask me any questions you have if that sounds good.

Nimble Pumpkin: Yeah that sounds great, yeah I'd love feedback.

Indelible Raven: So I actually don't have anything negative to say to be honest, you did really well. Like you're fast, you came up with a good starting solution, the only thing I wish you would have done for the second part was say hey, let's store it in something efficient like a priority queue to where you can see the maximum in O(1) time. You considered all the edge cases, you said hey we're going to test this out, here are the cases I would test with, it worked pretty... actually I don't even know if you ran into any errors, or if it worked the first time.

Nimble Pumpkin: It did, it worked the first time.

Indelible Raven: That's impressive!

Nimble Pumpkin: Beginner's luck haha.

Indelible Raven: Your code is clean, like the way you logged everything, it would have been neat to see you try the unit test, but it's not necessary.

Nimble Pumpkin: I mean I know how to write unit test, it's like that yeah.

Indelible Raven: Yeah except for the the wishing... actually there's a couple things, but except for the wishing you pointed out a priority queue instead of keeping it out of lists, you did good. The only other thing I would say, you're missing the edge case of when K is zero and also would you have approached this differently if I said instead of two dimensions like XY, let's give it a million dimensions, so x1 to x1-million?

Nimble Pumpkin: Right, um I think that you need to do... I don't know off the top of my head, I think that I like the distance formula, I believe it's basically the same, I think you just add more like elements into like calculate distance and you need to just look at every dimension of it rather than just two.

Indelible Raven: What about this part?

Nimble Pumpkin: I guess the space is going to be a lot bigger for the points potentially, so you know using O(n) spaces is going to just be like bigger, you know with a million dimensions duplicating the points is going to take up a lot more space. I think I kind of solved that with my second implementation, which was more of like a greedy algorithm, but yeah definitely that make sense like if it's if there's a potentially a lot of points and the dimensions are high it's going to use up more memory.

Indelible Raven: So kind of what I'm thinking is just index instead of a point. So store the index. Beyond that you did really well, I would have totally passed you both on site and the phone screen, so nice job. Do you have any questions, any comments?

Nimble Pumpkin: Yeah I'm curious like how many interviews have you done, I'm just curious what your sample sizes is.

Indelible Raven: I don't know the total number but I'm probably over 500 now, not just here.

Nimble Pumpkin: Alright, that's a pretty big sample size.

Indelible Raven: Not just here but at jobs themselves and everything else, like I'm probably over 500, I've done a ton.

Nimble Pumpkin: Got it, cool. Okay well that's good to hear, it makes me feel, yeah.

Indelible Raven: It takes a lot for me to pass someone.

Nimble Pumpkin: Okay cool well that's good, that makes me feel good that I have this.

Indelible Raven: Yeah, if you perform like this with your future interviews, you'll be fine, so hopefully this helps get rid of some like nervousness or anything that might come up.

Nimble Pumpkin: Yeah, it definitely helps. Doesn't hurt, that's for sure. I think that's pretty good, I think you were a good interviewer. I think I was pretty good, if you're open to... do you live in the Bay Area or where are you from?

Indelible Raven: I'm in Seattle now. I used to work at Google and Microsoft. I just got an offer over in Boston now, so.

Nimble Pumpkin: Okay cool. What... I'm actually this just random out of curiosity question, but why are you interviewing on the platform, like is it for experience? I mean you have a lot of experience interviewing, why do you do it?

Indelible Raven: I actually started up a non-profit to help people get into tech and Aline, the CEO, reached out and said hey, you like giving interviews, you like helping people out, we have this really cool platform that works a whole lot better than what you're doing, do you want to give this a shot instead for that portion of it? And I said yeah, so it's a really neat platform and also we get a little bit of a kickback as well, so just kind of a thank you for helping out.

Nimble Pumpkin: Got it, cool. Alright well I think that's good, I appreciate the feedback a lot and I really appreciate you taking the time, it's very helpful for me and yeah.

Indelible Raven: So I'm going to write some written feedback. It's going to be along the same lines, and at the end you'll get the chance to write me so feedback. Since it went so well, I'm going to say showcase it, what that basically means is there's a list of videos on the site to say, hey here are good videos, we want to show other people. Completely anonymous still, but if you want to do that, you can select that showcase as well and it'll go public.

Nimble Pumpkin: Cool, yeah why not, sure.

Indelible Raven: Awesome, it was a pleasure, have a good weekend. It's Thursday, so yeah nearly weekend.

Nimble Pumpkin: It's almost the weekend. Getting there.

Indelible Raven: Take care.

Nimble Pumpkin: Well thank you, Indelible Raven.

Indelible Raven: Yeah, no problems, bye.