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 quick dinner and it's settling down really good. Have you done this before?
Inventive Wind: Not on this platform, I have not.
Indelible Raven: Okay. So kinda 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 10 minutes after, roughly.
Inventive Wind: Okay.
Indelible Raven: I'll be filling that out after.
Inventive Wind: Okay.
Indelible Raven: Sound good?
Inventive Wind: Yes, it does.
Indelible Raven: You ready then?
Inventive Wind: Yes I am.
Indelible Raven: Sweet. A quick question, uh 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, um I'm going to give you this question then.
Inventive Wind: Okay.
Indelible Raven: Um by this, I know you don't see it yet, but I... so I don't know Java, so I might be asking questions that may sound weird, I just don't know Java.
Inventive Wind: Yeah no problem. Yeah.
Indelible Raven: So I'm going to give you a list of points, it'll be XY coordinates.
Inventive Wind: Okay.
Indelible Raven: Let's just say it's a class... I'm gonna write it like C++, feel free to change it. Right, so that you're gonna 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 the 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. I want, in this case, I would want you to return the ten closest points around vertex.
Inventive Wind: Okay, all right. All right that makes sense.
Indelible Raven: Great.
Inventive Wind: What's the approximate number of points that I could be expected to have to handle?
Indelible Raven: Um for now let's just say it'll fit in memory.
Inventive Wind: Okay.
Indelible Raven: What are your thoughts on this?
Inventive Wind: I'm trying to think of if there's any other edge cases or any edge cases or any other bits of information that are important to collect before I start thinking about the solution too much.
Indelible Raven: Sure.
Inventive Wind: Are the coordinates are going to be positive or could be negative?
Indelible Raven: They could be anything. It could be any double, even though I put int, it's yeah um double. It could be anywhere in the plane. Negative, positive, all that.
Inventive Wind: Sure, okay. And I can assume, I mean there's going to be at least ten points and the vertex is not going to come in as null?
Indelible Raven: The vertex will will not come in as null. I cannot guarantee anything with k.
Inventive Wind: All right, okay. So you return, you know, all points if the number of points is less than k.
Indelible Raven: Yes.
Inventive Wind: Okay, all right. 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, some other bits of information to collect later, but what my first thought is... is that it might be useful to 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 the vertex. Were you going to say something else?
Indelible Raven: Um no I'm actually kind of curious... if you continue down that route, how that's going to work, I've never seen somebody attempt that, so...
Inventive Wind: Okay, I know uh... well let's see... Yeah I mean... that I mean, the other obvious or the brute force solution is, you know, you could take every... I mean we have the vertex up front, we've got the list of points, you know. You could iterate over the list and... yeah, no this would... this seems better. Um calculate the distance between each point and as we scan the list and the vertex and then put them into a a priority queue and then it begins you would take the first K elements out of the priority queue ordered by distance and if the priority... you know if you reach the... priority queue is empty before you get to k, you know then you've got... yeah either way you have your answer. That would be a... I think that would be an O(n)..., go ahead?
Indelible Raven: I was going to say, sounds like a reasonable approach.
Inventive Wind: Yeah, so I think that would be an O(n log n) solution, for looking up N points, and calculating their distance and then a O(log n) insertion into the priority queue.
Indelible Raven: So, sounds like a good answer, but my question is, do you actually need to store every single point in that queue?
Inventive Wind: Uh, no you'd only need to maintain the ten 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 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... so that the naive solution would be the the lowest element goes into the zero slot and 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 the... to which slot is currently the lowest we've ever found, and then if we find a lower one insert to the head minus one spot mod K and then update your head pointer.
Indelible Raven: Um, so I get what you're going at, but is there a type of queue that can just do that for you? At least maintain where the max element is?
Inventive Wind: Right, that would be the priority queue. But wouldn't maintain... but finding like the kth largest would be a problem...
Indelible Raven: Why not go the other way instead?
Inventive Wind: Oh yeah, right, yeah, maintain priority queue of 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 in.
Indelible Raven: Sounds better actually. I don't know if you're satisfied with that, but like a reasonable thing to start with.
Inventive Wind: Yeah, yeah I can get started with that. Okay, yeah I think I'll start with implementing distance. Should distance take a... I'm assuming should take the vertex like this or...?
Indelible Raven: Or just a point in general, yeah.
Inventive Wind: Yeah. The sheets... That'll work for the distance function. So then I'll have a... so I guess...
Indelible Raven: I don't actually know if list is a thing in Java.
Inventive Wind: It is, yeah.
Indelible Raven: You can use whatever you want.
Inventive Wind: Yeah, list is an interface or an abstract type. Probably, you know, array list and linked list would be the most common implementations.
Indelible Raven: Okay. I think it was arraylist that I was thinking of, just an array of points. I haven't touched Java in like five or six years, so...
Inventive Wind: Yeah, no problem. I think... oh I did not mean to do that. That is a hotkey I'm not familiar with. Right. Okay, so then we would create a priority queue, which is a Java class and it's a concrete implementation... and then actually... so yeah, so the second parameter 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 we can use that to... so we want to make sure that it's properly a distance function as the compare between points. The other way we could do this in Java is you could have 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.
Indelible Raven: Um your call, I mean I I don't even know if that point class would work in my case so... I assume it does, so if you want to add it there, that works.
Inventive Wind: I can do that. Actually that's uh... and I believe 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 if it's the... if you know positives... oh yeah no this won't work because of the vertex, but we could we could actually do this with... down here in the closure. I believe with this Java actually would now allow us to do this. So yeah, like I was going to say, I forget whether p1 greater than p2 implies a negative one or the other way, but that would be easy enough to figure out in the real world. Okay so now when we put the points into the priority queue, and the priority queue will store them in either min or max order, it's easy enough to flip that if necessary.So then fairly... we've got to add the point to the priority queue. So if we, if the priority queue isn't full yet, we can just add the point without checking whether it's needs to go into the queue or not. So I guess that you see.... so I guess it's easier to...They're going to be mutually exclusive of what we do in each 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.
Indelible Raven: Looks right so far.
Inventive Wind: Yeah so I'm 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 it's thinking about whether there's anything else I missed before I'm ready to do that.
Indelible Raven: There's something you can do to optimize it like that.
Inventive Wind: Uh sorry what was that?
Indelible Raven: There is something you could do to optimize it at that point.
Inventive Wind: At the point of building the output list?
Indelible Raven: No, the point of the queue.
Inventive Wind: Um I think I'm just going to finish building the list and then I will come back to that to think about some more. Might pop into my head as I'm doing this. All right. Let's... is this... so the right side, and 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 workspace here to see if there's any tools like... I can't write on the right side right, but there's a draw thing. Okay. I don't know if that's... Okay, so how to optimize this, let's see. So a lot of times when I get a problem like this, I mean I do like to walk through some just simple test cases. This problems I guess is a little bit trickier and that like some of the doing the calculating, which to I mean you can choose points that are very obviously closer and not closer, so I'm gonna try to do that 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 k plus one closest.
Indelible Raven: No. The closest by numerical distance.
Inventive Wind: Okay. So the priority queue will take care of the order in here and if distance is correct and the comparator function is correct, but so we go in look at the first point. The size of the queue is less than K, so we'll just add (1,1), and we'll do that for the first three, so we'll have negative one and I mean this isn't going to be very interesting because I put them all at the front, um I can move this guy... So that's what we get. And then we come in and we look at so now we're looking at one negative one. And the k low so far size is three, equal to k, I guess really this we don't need the greater than. And okay, the priority queue is going to be ordered, so it should be like this. So we'll uh... so kth is now going to be 2, where their distance for two two is going to 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 if then we come in with negative two negative two, we peak 1 1, but the negative 2 negative 2 is greater distance than 1 1 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 run it, or do you have like input you want to give it or...?
Indelible Raven: Um whatever you just used, that would work.
Inventive Wind: Okay. I can't get too clever. Let's run it. Oh really... oh yeah okay, so it's complaining because distance returns doubles and the comparator functions returning is returning it, but that's... I mean I could cast it to an int, but yeah that should work.
Indelible Raven: I'd cast the whole thing, not the first.
Inventive Wind: Yeah. I guess there... yeah, so it could be that there's a rounding error there. Well in this case it shouldn't be... Looks good.
Indelible Raven: We should stop with this one, I have something to extend on this. Um I want to change this a little bit. Um I don't know Java has a data stream like C++ or Python, so the data stream, if you don't know what it is, basically continuous input of points. It works very much the same with like a for each or put in yeah. It wouldn't change much in terms of how it's read, so I... the trick to it is the data stream will never end. How do we adjust the return to get k closest. So it always starts at the beginning.
Inventive Wind: So you want this to like return synchronously and like so I'm imagining like this stream is, you know this is like a maybe... it's like a like a sensor value, right? And it like you know, we want to get the K closest so far then.
Indelible Raven: No because what it'll do is it'll give you the very beginning of the list and then just continuous keep continuously come, keep coming in. What I want is the K nearest for the entire list. We know that it will never end, so how do we say it ends?
Inventive Wind: Sorry what... how do we?
Indelible Raven: If it never ends, how do we end it and say these are the K closest? At some point you should stop, right?
Inventive Wind: Right, yeah. Is there a... I mean do we know anything... are the points ordered well? Are there any other...?
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, it's just like that k closest.
Indelible Raven: Well, let's go down the line of precision, and I guess within a number of points as well. Do we create some sort of like precision/threshold that we call it quits after we reach it?
Inventive Wind: I mean if you had K points that were equal to the vertex then you would obviously... I mean you're doing a double comparison here. Double is the... double representation is imprecise, and so you could... If you had, I mean I think that if you're comparing double equality, that the language would probably or the runtime would take care of being within you know the like rounding error through double math. But like if one point is close enough to the vertex so that the distance is indistinguishable by the double data type, that it 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: Um, I mean if we knew that we wanted to get K points that were within a certain arbitrary distance of the vertex, that'd be you know that being easy a stopping point to find. But when you add the k...
Indelible Raven: Let's look at that then, right? We want an arbitrary threshold error ratio right? But you also don't want to, let's say the first six elements are under that, you just don't want it... so should it be factored in some sort of number of points seen as well?
Inventive Wind: Right yeah. I know that there is a that there's like some sort of like 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 up front to kind of get a sense of what your data stream looks like and then what you can expect the kth best to 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 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, with requirements having to be met, both the threshold and the number of points and if you don't meet it, you increase both, right? Would something like that work?
Inventive Wind: So you're saying we would have so we'd have some sort of a window, like a window number of points. It'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 a thousand points or something and then this is you know two, right? If we don't have K points within two of the vertex in our last thousand points we've seen, we would 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 um that would make sense.
Indelible Raven: Is this the 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 seeming like an experiment to me and like when I'm doing as an experiment I try to you know keep one very you know try to only change one variable, so what I was thinking in my head was like would it make sense to potentially on alternate iterations like like we last increase the threshold so then we increase the window and then if we can't satisfy 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.
Indelible Raven: I can reason I would say 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 two thousand light-years away, something you have to worry about. Let's uh stop here. Did you want to hear kind of your verbal feedback before I write it out and what are your thoughts on that?
Inventive Wind: Um I'm fine with whatever you you want to? I would hear my feedback if you are ready to give it.
Indelible Raven: Sure um so let's start from the beginning. I'm glad you clarified all of... most of the edge cases. You missed a couple of like what if K was negative.So I'm happy you did that uh, but you have actually doing like all the conditions can still be done. I would have liked to see it being 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 where it could compile and run, but your code wasn't 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 you're recomputing the distance every time you insert or check and stuff like that. So I check four things when I evaluate someone: first one is you 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 good see kind of classes and stuff worked out. Ih so I have a question Java wise. Every other person I talk to with Java started the main with creating an instance of solution, but you didn't. Clearly it's not required from the looks of things. I just don't know why they would think to do that?
Inventive Wind: Do you want an answer or?
Indelible Raven: Yeah sure.
Inventive Wind: 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, wouldn't really you know if you're building a big Java system would probably be discouraged, but you know these these sort of problems are pretty self-contained and that's just the quickest easiest and clearest way to just solve it my opinion.
Indelible Raven: Okay um anyway back to my feedback, it took you a little bit, I had a couple hints but only a couple really, so you're able to get it when I asked about if you can let's say use the max upfront instead of the min. It took you a couple of times of me asking 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, I did like that you were considering edge cases, but we don't really have the chance to be on one thing to test. Your code was a little bit slow. At a mid-level engineer, I kind of expect people to go a little bit faster, to be able to get a good point so it's running probably in half the time and then start optimizing and start using stuff like that. So I've worked on speeding things up a little bit.
Inventive Wind: So you would you would prefer running test cases through the platform instead of working through them my hand, is that one of your um?
Indelible Raven: Yes 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 then tell me the rest. Okay so part two of what I look at is your knowledge of algorithms and data structures. I didn't really see any bad thing. 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 it allows you to not look at every element and be able to determine with an error threshold what the top K is, so it might have been very similar to that. We just didn't investigate it hard. So yeah, generally speaking I would love for you to catch max heap faster, but overall algorithms and data structures was fine uh and you can code. 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 problem solving. We need to know you could solve problems more than you can code, even though we still need you to code. Um I get a little bit of that with 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, I seem like a held your hand in a direction but once you figure out what I was getting at, it became a little bit more clear and you started working on, at least idea wise on what it was I was looking for, or what a possible option could be, I mean. So your problem something is from what I could tell decent, but not, again this is an interview thing. it is probably great, but from what I could tell in 35 minutes, it needs a little bit of work. Again, that's not on your ability to actually solve problems, it's just what you could 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 going through a design meeting or your writing system design doc, what are your initial thoughts and can you come up with the 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: Um I guess for the problem-solving part, like you're talking about like the stream and then we have 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 a terminating point right, you need to come up with some reasonable criteria, um yeah. I guess I used what might have been kind of trained or like thought that maybe just I'm doing practice with like online things where you don't get to talk to a human and like you know like engage with them. You know the problem is kind of is what is stated and like there might be hidden information 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, if in this case you know like the question is like you have an infinite stream when you like you want the k smallest or the K closest in the stream, it's like well it's as stated like that that's like not possible.
Indelible Raven: It's not possible with the perfect k, unless like sorted or something, but as far as is it possible with the threshold, yeah very possible. Um yeah, so people do it differently. I throw in a question that you're not going to solve in that remaining time, if at all. But I want to see how you tackle something that you don't know and see if you could take subtle hint to bring that aha moment this could work, what if I did this type of place in the interview. But if you go there, you went really really really well. And I asked the same question to everyone except for I changed 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 as a mid-level, senior level engineer, I do want to see some effort with it into some direction. Keep in mind, not everyone does this, not everyone will give you something like that, they'll evaluate you in their way, or they just won't evaluate it. I'm just one example of what could happen so... If that makes sense, I don't know if that answered your question fully.
Inventive Wind: It helps, and I think it is just kind of a question, like I guess my thought is like when'd you'd ask me that and I said well as like as stated that's not possible, but if we you know you know, we have some additional condition, then we you know then the problem is possible, like would that have been a good answer?
Indelible Raven: Yeah, that would have been great and I would love for you to go into what those conditions were. Some ideas on what conditions may be. Obviously you wouldn't know right away, but kind of hey what if we started looking at this. That's why I give it to you, I give 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, like I said the problem solving, that's how I evaluate people because you can evaluate someone's basic problem solving with the first part of hey how do you yeah. I just don't get the full range of what you can do with that. 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 have definitely advanced you. If this was very hire/no hire decision, um I would swing to a very weak no higher, which means I'm on the edge of saying hire or no hire. But the reason being is because your level, I kind of expect you to go a little bit faster with this. And then spend more time on a bigger problem solving part, if anything. If you were like junior, I would have passed you, so as you go up in the levels, the more criteria I look for. So hopefully that's a good learning point, PS please feel free to come by and interview with other people as well. I'd probably ask people like can you do system design or something like that and see, look at that perspective as well. Just some food for thought.
Inventive Wind: Yeah, no make sense, I appreciate it.
Indelible Raven: Yeah, no problem, I had a blast collecting data as well so.
Inventive Wind: Yeah this was very helpful, you're a good interviewer and I do appreciate the feedback. It's much more informative than basically any other way of practicing, so thank you.
Indelible Raven: Great um, have a good one.
Inventive Wind: Thank you.
Indelible Raven: I'll be submitting your feedback here very shortly. Fill out the survey for what you think about me as well, so feel free to be honest with that. Take care.
Inventive Wind: Yeah, you too, have a goodnight.
Indelible Raven: Bye.