K closest points
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?
Read more about the questions
Feedback about Nimble Pumpkin (the interviewee)
Advance this person to the next round?
How were their technical skills?
How was their problem solving ability?
What about their communication ability?
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?
How good were the questions?
How helpful was your interviewer in guiding you to the solution(s)?
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.
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
(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
Klet'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
(1, 1). Nimble Pumpkin: Okay. So find the... you give me
K, and so I want to find the
(b2 - b1)^2 + (a2 - a1)^2and 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
Kis 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 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
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
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)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
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.