Inventive Wind: Hello.
Indelible Raven: Hi.
Inventive Wind: Hi.
Indelible Raven: How's it going?
Inventive Wind: Good. How are you?
Indelible Raven: I'm doing pretty good. Just cook dinner and it's settling down really good. So yeah. Hey, have you done this before?
Inventive Wind: Not on this platform. I have not.
Indelible Raven: Okay. So kind of how this works. I don't know if you read up on it or saw examples, but hey, in the game, we do typical interviews. In my case, I've worked for Google and Microsoft. So I generally just give the 35 minute tech interview that we would there. Following that, I give you the option to hear your feedback verbally. So I just tell you after if you want, but after that, you'll get feedback on the site, about ten minutes after roughly. Sound good?
Inventive Wind: Yes. It does.
Indelible Raven: You ready then?
Inventive Wind: Yes, I am.
Indelible Raven: Sweet. Quick question. Two questions. Roughly, what level are you at in your career? And what programming language do you want to use?
Inventive Wind: I was going to use Java. And I would say, I'm like a mid level engineer. I've got about six or seven years experience.
Indelible Raven: All right. I'm going to give you this question then.
Inventive Wind: Okay.
Indelible Raven: And by this, I know you don't see it yet. So I don't know Java, so I might be asking questions that may sound weird.
Inventive Wind: No problem. Yeah.
Indelible Raven: So I'm going to give you a list of points, there'll be (X,Y) coordinates. Let's just say it's a class. I'm going to write it like C++, feel free to change it. And then let's see distance in here. Right. So that, you're going to fill in, but also, I'm going to give you a list of points... It'll just be a two dimensional plane in this case with a ton of points around it. I'm going to give you the vertex. So it's not going to be (0,0) in most cases. And what I want you to do is find the nearest points around the vertex, and I'm going to give you an integer k, and that'll be your count. So let's say like 10. In this case, I would want you to return the 10 closest points around the vertex.
Inventive Wind: All right. That makes sense.
Indelible Raven: Great. See, what's the the approximate number of points that I could be expected that have to handle?
Inventive Wind: For now, let's just say it'll fit in memory.
Indelible Raven: Okay.
Inventive Wind: What are your thoughts on this?
Indelible Raven: I'm, first I'm trying to think of, if there's any other edge cases or any other bits of information that are important to collect before I start thinking about the solution too much.
Inventive Wind: Sure.
Indelible Raven: Are the coordinates going to be positive or could be negative?
Inventive Wind: They could be anything, it could be any double. Anywhere in the plane.
Indelible Raven: Okay. All right.
Inventive Wind: Negative, positive all that.
Indelible Raven: Sure, okay. And I can assume, there's going to be at least 10 points and the vertex is not going to come in as null?
Inventive Wind: The vertex will not come in as null. I cannot guarantee anything with k.
Indelible Raven: Okay. So the return, you know, all points if the number of points is less than k.
Inventive Wind: Yes.
Indelible Raven: Alright, I'm going to, you know, so I think I'm ready to at least start thinking about how I'd approach this. I might think of some other things to, to some other bits of information to collect later. But what my first thought is, is that it might be useful to order the points by their position on either axis, and then you could potentially do some, like a binary search type of thing within each access to find points that are likely to be the closest to to the vertex. Were you gonna say something else?
Inventive Wind: Um, no, I'm actually kind of curious. If you continue down that route, how that's gonna work. I've never seen somebody attempt that. So...
Indelible Raven: Okay. I guess? Well, let's see. Yeah, yeah. I mean, that, I mean, the other I mean, the obvious, or the brute force solution is you take every, I mean, we have the vertex upfront, we got the list of points, you know, you could iterate over the list, and yeah, no, this would, this seems better. Calculate the distance between each point. And as we scan the list, and the vertex, and then put them into a priority queue, and then at the end, you would take the first k elements out of the priority queue, ordered by distance. And if the priority, you know, you reach the priority queue is empty before you get to candidate k, then you know, then you've you've got your... Yeah, either way, you have your answer. That would be a... Go ahead.
Inventive Wind: I was just going to say, sounds like a reasonable approach.
Indelible Raven: Yeah. So I think that'd be an O(n log n) solution for n... looking up n points and calculating their distance, and then log n insertion into the priority queue.
Inventive Wind: So, sounds like a good answer. But my question is, do you actually need to see every single? Or do you need to store every single point in that queue?
Indelible Raven: No, you'd only need to maintain the 10 lowest you have. Yeah, so I guess that's a good point. Right, you wouldn't need to, you just need to save the k, the k lowest. So you could do that with like, you could have a point array, that is k elements long, and then you would maintain like a pointer into the reader like the so the naive solution would be, you know, the lowest element goes into the zeroth slot, and the kth element goes into the k minus one slot, right. But then every time that you find another lower one, you would have to shift all the elements. So what you could do instead is maintain a pointer to the head of which slot is currently the lowest we've ever found. And then, if we find a lower one, insert to the, you know, the head minus one, spot, mod k, and then update your head pointer.
Inventive Wind: So I get what you're gonna, but is there a type of queue like you that can just do that for you, at least maintain where the max element is?
Indelible Raven: Right, that'd be the priority queue. But would it maintain... but finding like the kth largest would be a problem or the you know?
Inventive Wind: Why not go the other way instead?
Indelible Raven: Oh, yeah. Right. Yeah. Maintain priority to you have the farthest elements from the farthest like the kth farthest element from the vertex we found so far. And then when we look up a new one, if the new one is closer to the vertex, then the head of the priority queue pops the head off the priority queue and insert the new one.
Inventive Wind: Sounds better actually.
Indelible Raven: Yeah.
Inventive Wind: If you're satisfied with that, a reasonable thing to start with.
Indelible Raven: Yeah. Yeah, I can get started with that. Okay. Yeah, I think I'll start with implementing distance... should distance take a... take the vertex like this?
Inventive Wind: Or just the point in general? Yeah.
Indelible Raven: Yeah. That'll be work for the distance function. So I guess...
Inventive Wind: I don't actually know if list is a thing in Java.
Indelible Raven: It is, yeah. Yeah, list is just an interface or an abstract type. Probably, you know, ArrayList, and LinkedList would be the most common implementations.
Inventive Wind: Okay. I think it was ArrayList I was thinking of, just an array of points.
Indelible Raven: Yeah.
Inventive Wind: I haven't touched Java in like five or six years. So...
Indelible Raven: Yeah, no problem, I think... Oh, I did not mean to do that. That is a hotkey I'm not familiar with.
Inventive Wind: Don't forget to...
Indelible Raven: So then we would create a priority queue, which is a Java class and it's a concrete implement. Then actually, so, yeah, so, the second parameter to the priority queue is... or to get to the priority queue constructor is a comparator, which takes in two elements of whatever the templated type is, and then it's a function that returns an integer negative one zero or one to compare the two elements. So, that would, so we can use that to... So we want to make sure that it is properly, this assumption as the compare between points. The other way we could do this in Java is you can make, you could add this implements comparable and then implement a method on the class. I can do that if you want but this way should also work fine.
Inventive Wind: Your call I mean, I don't even know that point class would work in my case, so I assume it does. If you want to add it there that works.
Indelible Raven: I can do that. Actually, I believe that that you have to declare what it compares to if it's a subclass, but in this case, we don't have to worry about that too much. And that would look like... I never, I don't remember essentially if, you know, positive is... Oh, yeah. No, this one, right, this won't work because of the vertex. But we could we could actually do this with down here. And in the closure with this Java actually would now allows us to do this. So yeah, like I was going to say, I forget whether p one greater than p two implies negative one or the other way. That'd be easy enough to figure out in the real world. Okay, so now, when we put, we can put points into the priority queue, and the priority queue will store them in either min or max order. And it's easy enough to slip that if necessary. So then, finally we got to add the points to the priority queue. If we, if the priority queue isn't full yet, we can just you can just add the point without doing checking whether it needs to go into the queue or not. I guess so I guess that you see. So I guess it's easier to do that I think it's going to be... they're going to be mutually exclusive. What we do in each use case. So peek just takes a look at the top of the queue, pull will take it off of the top. So I'm going to start by just peeking and then if we have to remove it, we'll pull.
Inventive Wind: Looks alright so far.
Indelible Raven: Yeah. So thinking about whether there's anything else I need to do here? I mean, I know I need to construct the list at the end and return that. But just thinking about whether there's anything else I missed before I'm ready to do that.
Inventive Wind: There's something you can do to optimize it.
Indelible Raven: Sorry, what was that.
Inventive Wind: So there is something you could do to optimize it. At that point.
Indelible Raven: At the point of building the output list?
Inventive Wind: No, the point of the queue.
Indelible Raven: I think I'm just gonna finish building the list, and then I will come back to that, think about some more, some optimization might pop into my head as I'm doing this. So the right side, there's a just kind of looking around the... So what I'm thinking to do now is to walk through the code and make sure that this seems to work. And then also seeing if, you know, I can think of any optimizations in the process of doing that. So I was just looking around the, like the workspace here to see if there's any tools like it's like I can't write on the right side, right? But there's a draw thing. Okay. Okay, so how to optimize? Let's see. So a lot of times when I get a problem like this, I mean, I do like to walk through some simple test cases. The problem is, I guess, a little bit trickier. And that, like some of the doing the calculating which two, I mean, you can choose points that are very obviously. Yeah, closer and not closer. So I try to do here, but... Oh, yeah. Okay. So that actually does bring up a... Is there any preferred ordering if there's a tie for, you know, the K and the kth plus one closest.
Inventive Wind: No, just return the closest in numerical distance.
Indelible Raven: Okay, so. So the priority queue will take care of the ordering here. And it's just as correct in the comparateur function is correct. But so we go and look at the first point. The K, the the size of the queue is less than k. So we'll just add one. We do that for the first three. So we'll have negative one. I mean, this isn't gonna be very interesting cuz I put them all at the front. So that's always a good that. And then we come in and we look at now we're looking at one negative one. Or, and the K so far size is three is equal to k. I guess really this, you don't need the greater than should be bad I guess. And okay, yeah, and the priorities, the priority queue is going to be ordered. So it doesn't know should be like this. So we'll, so kth is now going to be to two, two. Compare their distance, the distance for two two is gonna be greater than the distance for one negative one. So we take it out of the queue, and then we add one negative one, and then do the same thing. Then we come in with the negative two, negative two. We peek one negative one. But the negative two negative two is greater distance than one one. So we should just continue and then we build the list. So at least for this relatively simple example, I think it works. Oh, yeah. Do you? Yeah. Do you have a run it or do you have like a input you want to give it or?
Inventive Wind: Whatever you just used. Yeah, that would work.
Indelible Raven: Okay, sure. I probably shouldn't get too clever. Yeah. Okay, so it's complaining. Distance returns doubles and comparative functions returns ints. But that's... what I could do. Like I could just cast it, should work.
Inventive Wind: I'd cast the whole thing, not the first.
Indelible Raven: Yeah. I guess there. Yeah. So it could be that there's a rounding error there. Cuz, you know, in this case, it shouldn't be.
Inventive Wind: We should stop with this one. One other, I have something to extend on... I want to change this a little bit. I don't know if Java has a data stream, like C++ or Python. But a data stream, if you don't know what it is basically a continuous input of points. It works very much the same with like, a fourEach. Yeah. So it wouldn't change much in terms of how to read. So the trick to it is the data stream will never end. How do we adjust the return value? So it always starts at the beginning.
Indelible Raven: Right. So. So you want this to, like, return synchronously. Like, so I'm imagining, like, the stream is, you know, this is like a, maybe it's like a sensor value, right? And you know, we want to get the the K closest, or, yeah, the K closest, so far, but then, you know.
Inventive Wind: No, because what it'll do is it'll give you the very beginning of the list. And then just continuously keep coming in. What I want is K closest for the entire list. We know that it will never end. So... how do we say it ends?
Indelible Raven: Sorry, what? How do we?
Inventive Wind: If it never ends, how do we end it and say these are the key closest?
Indelible Raven: At some point you should stop. Right?
Inventive Wind: Right. Yeah. Is there a... I mean, do we know anything? Are the points ordered at all?
Indelible Raven: No.
Inventive Wind: And we're not looking for the K closest within some degree of... within some distance or within some precision?
Indelible Raven: Well, let's go down the line of precision. And I guess, within a number of points as well, can we create some sort of like precision/threshold that we call it quits after we reach it?
Inventive Wind: I mean, if you had, if you had k points that were equal to the vertex, you know, then you would write obviously, it was the ideal return. Yeah. I mean, you know, I mean, you're doing we're doing a double comparison here. Double is the double representation is imprecise. So you could if you had, I mean, I think that if you're comparing double equality, that you know that the language would probably or the runtime would take care of being within you know, the like rounding error through double math. That like if one point is close enough to the vertex so that the different distances indistinguishable by the double data type they would they would evaluate to equals. I can't, not really certain what... I mean if the stream is infinite.
Indelible Raven: Let's go back to your precision, what was in your head when you said that? What were your thought process on that?
Inventive Wind: I mean, if we knew that we wanted to get k points that were within a certain arbitrary distance of the vertex, that would be, you know, that would be an easy stopping point to find.
Indelible Raven: Right. So let's look at that, then, right? We want an arbitrary threshold error ratio, right? You also don't want to, let's say the first six elements are under that. You just don't want to break? Right? Should we factor in some sort of number of points seen as well.
Inventive Wind: Right. Yeah, I know that there is a, there's like some sort of, like a, this sort of problem, I have heard about some sort of like a theorem or an algorithm that, yeah, you're supposed to collect a certain number upfront, to kind of get a sense of what your data stream looks like. And then, like what you can expect the case best to be and then you after you've determined you've collected enough data, you set your threshold yourself. And then and then after that the first k elements that that satisfy the threshold, you would return. I don't know the, like the the math behind that for like, what the optimal ratio is, I remember, I know that there's some sort of...
Indelible Raven: What if you created like a sliding window? Like, the two requirements, having been met both thresholds and the number of points? And if you don't meet it, you increase both? Right? Would something like that work?
Inventive Wind: You'd have, so you're saying we would have? So we'd have some sort of window, like window points, number of points. That's a long name, but I would shorten it, but and then we'd have the threshold, like termination threshold. And then if within, so let's say this is, you know, like 1000 points or something, and then this is, you know, like, this is two, right? If we don't have k points within two of the vertex, in our last 1000 points we've seen, we would, then we, then we increase the window, somehow, that's what you're suggesting?
Indelible Raven: Yeah, the window and like the threshold, right?
Inventive Wind: So that makes sense.
Indelible Raven: Seems like an appropriate way to do it.
Inventive Wind: I could certainly. One thing I was thinking, you know, like, I guess... Like, this is kind of sound seeming like an experiment to me. And like, when I'm dealing with an experiment, I try to, you know, keep one, you know, try to only change one variable. So what I was thinking in my head was like, would it makes sense to potentially on alternate iterations, like, we last increase the threshold, so then we increase the window. And then if we can't satisfy it in the window, then we increase the threshold. And then that way, you know, it's possible that just increasing one of the conditions would have satisfied your... but I don't know if that's a worthwhile complication to add.
Indelible Raven: I would see it that way. Is because... Let's imagine we're working with space? And you're not two miles away. The next item is like 2000 light years away. Something you have to worry about. Let's stop here. Do you want to hear kind of your verbal feedback before I write it out or and what are your thoughts?
Inventive Wind: I'm fine with whatever you want to. I would hear my feedback if you are ready to give it.
Indelible Raven: Sure. So let's start from the beginning. I'm glad you clarified most of the edge cases, you missed a couple of like, what if k was negative? Yeah. So I'm happy you did that. But you didn't actually do it. Like all the conditions are, we can still be done. I would have liked to see it implemented. You also might have taken a little bit longer than I would have preferred because you didn't really get a working solution. You got to work and compile and run. But you're totally right. I mentioned that there's an optimization with the queue. I'm not going to hit on that just because it's a little bit better. But if you're curious, think about how often you're recomputing the distance. Every time you fire insert or check and stuff, right?
Inventive Wind: Yeah, that makes sense.
Indelible Raven: So I check for things when I evaluate someone. First one is your technical ability. Do you write code? Do you follow a style guide? Do you check edge cases? Do you throw exceptions when needed? And so on. And surprisingly, for the first time of on this platform, I interview elsewhere as well, someone has actually had non vague variable names. I don't know why it's so hard to write normal names that make sense. Most people are just like i and something else, like two letter names. So nice on that. Also great to kind of classes and stuff worked out. So as a question Java wise, every other person I talked to with Java started the main with creating an instance of solution. But you didn't it? Clearly, it's not required. I just don't know why they would think to do that.
Inventive Wind: Do you want an answer? Or? I mean, the big thing is, I mean, in Java, typically, static methods like this are typically not encouraged by most Java style guides. But that would be the closest thing to just like a pure function that Java has, for the most part. And for the sake of, you know, a problem like this. It wouldn't exactly to make a static method for doing this, when really, you know, if you're building a big Java system would probably be discouraged. But certainly know, these sort of problems are pretty self contained. And that's just the quickest, easiest and clearest way to solve it, in my opinion.
Indelible Raven: Anyway, back to my feedback. With you, it took you a little bit, I had to give you a couple of hints, but only a couple really. So you're able to get it when I asked about if you can, let's say use math up front. It took you a couple of times in me asking me in different ways for you to finally click what I was asking. But you did get it eventually. So overall, technical ability was pretty good. Not perfect. Not bad, either. So if I did like that you were considering edge cases. So you don't really have the chance to be on one thing to test. Your code was a little bit slow. In a mid level, senior level engineer, I kind of expect people to go a little bit faster, to be able to get a good point towards running probably half the time, and then start optimizing and start using test cases. So I've worked on things up a little bit.
Inventive Wind: So you would you would prefer running test cases through the platform instead of working through them by hand, is that one of your?
Indelible Raven: Yeah, because I want to see it working. If it's a whiteboard, obviously, that's not the case. But I'd like to still see code that worked. Yeah. So even when it's on the whiteboard, what I would do is just say, hey, write out at least one test case and focus, only the rest. Okay, so Part Two I look at is your knowledge of algorithms, data structures. I didn't really see any bad things. You knew it... I, the only thing that questions me was, what the binary search thing was in the beginning. And I generally have an idea of what you're going for, because there's an algorithm called the KD tree. And it allows you to not look at every element and be able to determine with an error threshold, what this half k is. So it might have been very similar to that. We just didn't do it. So yeah, generally speaking, I would have loved to, for you to catch max heap faster, but overall algorithm data structure was fine. And then I get into communications, I have no problems with that. And then we get into the big part for me, and that is your problem solving. So technical ability is kind of a small part compared to the problem solving, we need to know you can solve problems when you code, you know. I get a little bit of that with the the main algorithm itself. But the part I mostly look at when it comes to problem solving is one of four things and you got the one that was, hey, if there's an infinite number of points, how do you change this? How do you look at a different approach and take something that you clearly probably do not know how to solve, most people don't, because it's a whole different concept, and how do you find a way even with subtle hints to come up with a reasonable solution. And for that, I'm up in the air because I gave you, it seemed like I held your hand in a direction, but once you figured out what I was getting at, it became a little bit more clear. And you started working on the idea was on what it was I was looking for, or what a possible option could be, I mean. So your problem solving is from what I can tell, decent, but not, again, this is an interview thing, it's probably great. But from what I could tell in 35 minutes was a little bit of work. Again, that's not on your ability to actually solve problems. It's just what you can do in 35 minutes. So I'd work on maybe trying to work on stuff that you don't know and see if you can quickly come up with possible solutions. The key here is that you're not going to be writing code for it. So it's more of a if you go into a design meeting or you're running a system design, a design doc... What are your initial thoughts? And can you come up with a solution basically asking someone kind of their opinion or thoughts and so on like that? Does that make sense?
Inventive Wind: Yeah, it does.
Indelible Raven: You have any questions?
Inventive Wind: I guess, for the the problem solving part, like you're talking about like the stream and then we had to kind of change the conceptualization of the problem, right? Like, the way the problem is asked, you can't just choose a starting point, or terminating point, right, you need to come up with some reasonable criteria. Yeah, I guess, is what might have been kind of trained or like thought that maybe just some doing practice with like online things where you don't get to talk to a human and like, you know, have like engaged with them to like, you know, the problem is kind of is what is stated and like there might be hidden information and the in the sense of, you know, edge cases aren't mentioned or like there might be a property in the data that's useful that, you know, you have to ask about to be able to take advantage of, but then, you know, kind of well, I guess, yeah. In this case, you know, like, the question is like, you have an infinite stream, would you like you want the k? k smallest? Or the K closest in the stream? It's like, well, as stated like that, that's like, not possible.
Indelible Raven: It's not possible with a perfect, k. Unless, like sorted or something. But as far as, is it possible with the threshold? Yeah. Very possible. Yeah. So some people do it differently, I throw in a question that you're not going to solve in the remaining time, if at all. But I want to see how you tackle something that you don't know and see if you can take subtle hints to bring that aha moment, this could work. What if I did this type of place in the interval? And I asked the same question to everyone. Except for, I change one of the really hard ones to one of four things. Most people I don't expect to actually solve it. But I do want to see some progression, depending on what level you're at. And there's a mid level senior senior level engineer, I do want to see some effort within into some direction. Keep in mind, not everyone does. It's not everyone will give you something like they'll evaluate you within their own way, or they just won't evaluate it. I'm just one example of what could happen. If that makes sense? I don't know if that answered your question.
Inventive Wind: Definitely. It helps. And I think it is kind of just a question. Like, I guess my thought is, like, if you'd asked me that, and I'd said, well, as like, as stated, that's not possible. But if we, you know, we have some additional condition, then we you know, then the problem is possible, like, would that have been a good answer or?
Indelible Raven: Yes. Yeah, that would have been great. I would love for you to go into what those conditions were some ideas and on those conditions, maybe? Obviously, you wouldn't know right away, but kind of, hey, what if we started looking at this? That's why I gave it to you, I gave you an impossible question that with some sort of modification with conditions is possible. That's kind of the problem solving part is how does he take something impossible and make it possible? So, again, not everyone asks like that. It's just kind of my thing. When it comes to problem solving. That's how I evaluate people. Because you can evaluate someone's basic problem solving with the first part. Hey, how does he do? Yeah, I just don't get the full range of what you can do with that.
Inventive Wind: Sure. That makes sense.
Indelible Raven: I got time for like one last question.
Inventive Wind: I don't know.
Indelible Raven: Yeah, well, if not, I could just jump off, give you your feedback. So as far as like a result, if you're on a phone screen, I would definitely pass you. If this was very higher, no higher decision. I would swing to a very weak no higher, which means I'm on the edge of saying higher, no higher. And the reason being is because your level I kind of expected to go a little bit faster with that and then spend more time on a bigger problem solving part, if anything. If you were like junior, I would have passed you. So it as you go up in the levels, the more criteria I look for. So hopefully that's a good starting point. Yeah, please feel free to come by and interview with other people as well. I'd probably ask people like, can you do a system design or something like that and see that perspective as well. Just some food for thought.
Inventive Wind: Yeah, no, that makes sense. I appreciate it.
Indelible Raven: Yeah, no problem. I had a blast. Hopefully you did as well. So, yeah.
Inventive Wind: This was very helpful. It was a good, you're a good interviewer. And I do appreciate the feedback, it's so much more informative than basically any other way of practicing. So, yes, thank you.
Indelible Raven: Great. Have a good one. I'll be submitting feedback here very shortly. And we'll have a survey for what you think about me as well. So feel free to be honest with that.
Inventive Wind: Okay. Have a good night.
Indelible Raven: Yeah, you too. Bye.