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?
Nimble Pumpkin: Cool, yeah sounds great.
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.
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?
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.
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?
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.