C++ Interview with a Microsoft engineer

Watch someone solve the k closest points problem in an interview with a Microsoft engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

K closest points

Interview question

1) Write a square root function. 2) Find the K closest points

Interview Feedback

Feedback about Supreme Gyro (the interviewee)

Advance this person to the next round?

How were their technical skills?

3/4

How was their problem solving ability?

3/4

What about their communication ability?

3/4

You did pretty good on the interview. There were some trouble spots but mostly it was good. You worked through the code quickly, it was decently efficient (especially the square root question) and it's obvious that your algo / ds knowledge is pretty high. Some of the things I wanted to note is that you should look at edge cases / test for when things could go wrong. Using C++ is fine but I'd take a look at how exceptions are handled as well as llambda functions. Finally, remember that your code could be looked at by people who didn't interview you, so you want to make sure it's readable. Variables like a, b, e don't really do anything for that. So I would think about more readable variables. Overall, nice job, I wish you the best of luck in your upcoming interviews.

Feedback about Indelible Raven (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

4/4

How good were the questions?

4/4

How helpful was your interviewer in guiding you to the solution(s)?

4/4

1/4

Interview Transcript

Indelible Raven: Hey, how's it going? Supreme Gyro: Hello can you hear me? Indelible Raven: Yeah, I could hear you. Alright, great. Have you used this platform before? Supreme Gyro: I'm sorry? Indelible Raven: Have you used this platform before? Supreme Gyro: Ah, yes. Indelible Raven: Okay cool, so you kind of know how it works. So what language do you want to use? Supreme Gyro: C++ if that's okay. Indelible Raven: Yep, oh you already selected it, cool. So I saw that you were a junior engineer roughly? Supreme Gyro: Yeah, less than one year full-time experience. Indelible Raven: Okay, so I'm going to give you... I'm gonna start you out with this and I want you to just start with a square root function. Supreme Gyro: So obviously you know we don't want to use any library functions right? Indelible Raven: Right. Supreme Gyro: Okay, so there's lots of different ways that you can find square roots in different languages. You can use assembly, you can use different approximation methods. Unfortunately, I don't have them all memorized. I only know one - the Babylonian method. And I also know how to find other roots as well, but let's just start off with the Babylonian method. Indelible Raven: What is that? Supreme Gyro: It's an approximation, so like let's say we had the square root of a hundred right? You know, that's easy, it's just ten right? But what it was like something like 47, right? We need to approximate that. So what we do is we take our value and then we take the number one and then we try and make 100 smaller and one bigger until such time that it becomes less than some epsilon, where epsilon is some error value, so we can get within some error value. Indelible Raven: Right. Supreme Gyro: Okay, are you familiar with the method or should I...? Indelible Raven: I've never heard it called that, but I think it's very familiar to what I expect so that works for me. Supreme Gyro: Okay, you might know it by Newtonian method maybe? Indelible Raven: Yeah, I've heard that. Supreme Gyro: Okay, great. So let's see. So we'll take A is equal to a value. B is equal to number one for now, and then our error epsilon, which we'll do 0.01. Indelible Raven: How about six digits? Supreme Gyro: So do you mean like... okay great. So let's see. While the difference between A and B is greater than E, we're going to try and make B smaller and make A bigger. And then once we're done, we'll just return A or B because they will be close enough. Indelible Raven: Okay. Supreme Gyro: So let's take a look at the example 100 and 1. So what we want to do is take 100, add it to one, that's 101 divide by 2, that's 50.5. So how does this help us? Well I just made A a lot smaller, right, I cut it in half. Indelible Raven: Right. Supreme Gyro: So let's see. That is A is equal to (A + B) / 2. Okay, so now that's 50.5. Now we will set let... let's see, B was 1, so let's set B equal to the original value, which was 100, divided by 50.5. So I'm gonna... if it's alright with you, I'll pull out a calculator so I can prove that this is working. Indelible Raven: Sure. Supreme Gyro: Okay, so let's see. If I do one hundred divided by 50.5, I end up with 1.98 approximately right? We're getting closer. We're going to be done in like three iterations, so just let's just do it three more times. So let's see. So now we're going to do 50.5 + 1.98, divide that by 2. Now we have 26.24. So I'm just dividing it in two again. Right? Indelible Raven: Yeah. Supreme Gyro: Okay, so now I'll do 100 divided by 26.24 and you know that's like around 4, it's like 3.81. We're getting closer and we're going to be done in two more iterations. Let's see, 26.24 + 3.81, divide that by two = 15.025. Almost done. This is 6.66. We're almost there, I think in one more iteration, we won't get in between six digits, but we'll get close enough to where I can prove that this is working. So let's do that one more time. 15.025 + 6.66. Sorry, I don't have a physical calculator, so I'm using the one on my computer. Indelible Raven: It's fine. Supreme Gyro: This becomes 7.845. 100 / 7.845 is 9.222. So I won't do it anymore, but I think it's very obvious that we're approaching, you know, some limiting value, which is ten. I might need to do a couple more iterations, but I think it's obvious now. Indelible Raven: Right, and when you run it, we'll be able to see it, so. Supreme Gyro: Sure, so you want to run it now or? Indelible Raven: Yeah, just to see if it comes up with it. Supreme Gyro: Okay, so let's do 100, which is easy. You know we'll get a value equal to ten, and then let's do something like forty seven. Okay so, if that looks good to you, I'll go ahead and run it. Indelible Raven: What? Supreme Gyro: I said if it's alright with you, I'll go ahead and run this now. Indelible Raven: Sure. Supreme Gyro: Here we go. So that's 10 and let's... I'm just going to check my calculator... and yup the square root of 47 is 6.85565. Indelible Raven: How about 2? Supreme Gyro: Let's see. Indelible Raven: I've done this question so many times I already know what the square root of two is now. Supreme Gyro: Okay yeah. Indelible Raven: So when does this fail? Supreme Gyro: Let's see, maybe if we have negative numbers. Well you don't want to take the square root of a negative number because it will be imaginary. You can deal with it however you want. You could maybe make some imaginary object or you could just make it absolute value, so... Indelible Raven: Let's just throw an error. Supreme Gyro: Okay. Going to have to remember my... my java wires crossed here. I mean if you want to do a try/catch or do you want to just return like negative one or something? Indelible Raven: Well I would just throw right? Supreme Gyro: Okay, I'm really gonna get my java wires crossed. What's that called... number exception? Indelible Raven: I just usually just throw exception or throw the comment right? Let's also try 0.25. Supreme Gyro: Okay. That is double. So 0.25 is... Indelible Raven: Right, you'll have to switch it to double as input. Supreme Gyro: Sure, let's switch that up. Okay so I'm pretty sure, you know, 0.25 square rooted should be 0.5. Indelible Raven: Yeah. Supreme Gyro: So let's see what happened here. It shouldn't be because of this, I don't believe. Indelible Raven: Well look at B right? You're trying to find the value under one right? Supreme Gyro: Right, right. Okay so what's happening is we're doing 0.25 - 1, we end up with a negative number. So instead of defaulting to 1... we want it to be smaller, so maybe I can just default to... I don't know maybe value divided by some constant like... let's see? Indelible Raven: Why not just set it to zero? Supreme Gyro: So A minus B... Well, let's see. We're not dividing by B, so I think that should be fine. A plus 100 divided by 2 becomes 50. I'm not sure, I've actually never done that before. Can I run the code and see what happens? Indelible Raven: Yeah. Supreme Gyro: Okay, yeah so it fills it a little bit, yeah. So I don't know. Indelible Raven: So do you notice a pattern with a square root underneath 1? Supreme Gyro: Being divided... well for two... the only pattern I see right now is um... under one you said? 0.25 becomes 0.5. Indelible Raven: Right. Supreme Gyro: Hmm, well I mean 0.3, doesn't become 0.6 so... Indelible Raven: Right, but it does become something greater than 0.3 right? Supreme Gyro: Oh, right, okay. So in this case, this algorithm is trying to make A smaller and B larger, but we don't actually want to make it smaller, it's going to break right? Indelible Raven: Yeah. Supreme Gyro: So let's see, for numbers smaller than 1... if I had 0.25 and I did minus some very small number, I would end up making point two five smaller. I don't know, maybe we can do some multiplication to get that to work. Indelible Raven: Well let's think about it this way, above one you want to find a number less than right? And below you want to find a number greater than right? So basically you just invert the logic, right? Supreme Gyro: Okay so maybe I'll say if number is less than 1, then instead... well I'm not sure if I can just change these to multiplications. Indelible Raven: Right. Okay so I'm going to move on to my second question. Supreme Gyro: Yeah, that's fine. Indelible Raven: I'm going to give you a point class or just these could be tuples or pairs. Actually let's just do that, right? Finally someone who programs in my language. So I say, these will be like (-1, 1), (1, 13) (2, 0), (1, 1) and so on right? And then I'm going to give you a point class which is parent, origin which will be the center of the graph, so let's make it (1,1) right? And then I'm going to give you a k=2. What I want you to do is find the K closest points around the origin based on distance, so in this case it could be like (2,0) and (1, 1) right? Supreme Gyro: Okay. Okay so let's see what I could do is iterate through this points array, take note of each distance value, right? Maybe store the those in a hash map, so let's see, we'll just make up some imaginary numbers. I don't know what that what that actual distance is but let's say the distance is 1 away. So we can determine that ok, well here are the two points and you know those are the two closest. If K was 3, then I might be able to do something like this. Get those two, then move on to the next one. Indelible Raven: Sure. Supreme Gyro: So let's see. For now, I'm just going to use an ordered map, I think we might be able to get away with using a bucket afterwards, but let's just do an ordered map for now. Let's see. I guess you want to return a vector of points as well. And I'll take in this input. So let's make an ordered map for now. Indelible Raven: So you want to pass in all three, right? K, origin, and points. Supreme Gyro: I'm sorry. Indelible Raven: You want to pass in all three, right? So points, origin, and K. Supreme Gyro: Oh, right. There's the vector of points. Okay. So what is our hash map look like. Well it's going to be int key for distance and it will have one or more points. Indelible Raven: Right. Supreme Gyro: We can do point dot first and second to get X and we have our origin so let's just do distance formula. Indelible Raven: Which one? Oh yeah, they're squared and then the square root of that. Supreme Gyro: Okay, so they are both squared. Should we use our square root function or can we use math? Indelible Raven: Just use the built-in one. Supreme Gyro: I think that's in cmath so it should be something like out squared, then that whole thing square rooted. Well this is just going to use our square root function but I'm pretty sure there's no math if we're using math. Indelible Raven: That's fine, we'll just change this back to... of you already changed it. Supreme Gyro: Okay, so now let's see what kind of a... what should we do. Now we have a hash map, or in this case an ordered map, which is a b-tree of T's distance and all the points associated with that key. Okay so now let's do something like this. Indelible Raven: I have a question. What happens when the distance is the same? Supreme Gyro: It will store... well that's the... I mean do we consider that a very close point? Indelible Raven: Oh I see, you have a vector so you just push them. Never mind. Supreme Gyro: Okay, so while P is greater than zero, so let's say K is 1. We'll get one point and then we'll print this out. So walk through our map. Oh, actually... Let's actually do it this way. Walk through the map, then walk through the iterator, and the value is a vector, so walk through that vector, and we'll decrement K as we're walking through the vector. You want to return a vector, so let's make a result set as we're walking through. Let me get rid of this. As we're walking through, we will do... you'll push one at a time, we'll decrement K and if K once again becomes zero, we can just return the result set we actually go through this. Or maybe we won't walk through it at all and we'll return an empty results set. Okay. So that looks okay. Does that look okay with you? Indelible Raven: Yeah, let me just look through it. Yeah it looks about right, we can probably run it and test it. Supreme Gyro: Okay. Before we do that, I'm gonna have to... and I guess I'll just use your example. Indelible Raven: Well that probably won't work fully but... Supreme Gyro: Okay we need to... let's see... vector and pair of points. Yeah so this isn't already a pair. Well, actually I'm not sure if you can instantiate pairs like that, I've never done it like that before. Indelible Raven: You can probably just use make pair right? Supreme Gyro: Yeah that should work. It's a lot of make pairs though, but that's okay. Let's do this. Calculate results set. Each point's going to be a pair, so how about we do it like this. Okay. Make pair I think works like this I'm not mistaken. Okay that looks good. There might be some bugs, so we're gonna have to run it. Okay let's take a look. Oh I need cmath and let me go and comment out our square root code. Oh well I don't have map made properly. So let's call this memo for now. Okay, that looks all right. Argument 2 is invalid. A vector of pairs. We should be allowed to have a vector of pairs. Indelible Raven: I mean you could probably just do this. Supreme Gyro: I'm sorry. Indelible Raven: Like the vector pairs should be something like this right? Ideally. Supreme Gyro: Yeah I guess so. Okay. I mean I feel like I've done it before with just curly braces, but yeah that's fine. Indelible Raven: Yeah your distances should be double. Supreme Gyro: We are square rooting, so yeah. Looks good. I shouldn't have to make the points double though I think it'll be okay. Indelible Raven: Click right here, 2 y2s. Supreme Gyro: Oh ok,x2 and x1 y2 and y1. Okay. This one I'm still confused by, I swear the other day I did an arrow though. Okay, so let's see. That is the correct answer, given what you gave from your example. Indelible Raven: Right, so how can we improve this? Supreme Gyro: How can I prove it? Indelible Raven: Improve it, yeah. Supreme Gyro: Oh improve it, okay. Well let's see. The time complexity of an ordered map is O(log n). So right now, this looks like an O(n log n) algorithm right, for each point. We're keeping them sorted. I don't think we actually need to keep them sorted, we might be able to use a bucket. So let's see. Indelible Raven: I mean that's what you're already doing, right? Supreme Gyro: I mean, sort of... but what I can do is map points to distance as well as distance to points. Indelible Raven: Right. I'll give you a small hint. What if we started thinking about an O(n log k) implementation. Supreme Gyro: We could maybe use a heap, but let's see. Okay so what I could do is calculate this distance. Hold on, I mean let's look at the example again. A max heap where we keep points sorted based on their distance and we're only interested in the first two points for now. So let's see. I would take a look at 0 and negative 1. That's interesting. Oh I thought the origin was (0, 0) for a second, okay. So I'll take a look at (0, -1) and calculate the distance from (1, 1). I'll put... how about I just push those first two points on the heap and then once I get to (2, 0), I'll realize that its distance is smaller. Then I guess the top of the heap arguably. And then we'll just push that on... we'll pop and then we'll push it on. Indelible Raven: Sure. Supreme Gyro: Okay, let's see. What I need is a priority queue of points and we have to change it from a max-heap into a min heap, so I'll have to vector of pair and a lower, also pairs. I think we're gonna need a custom operator. I'm not sure if I remember how to overload the priority queue's operator. Indelible Raven: Just lambda function. Supreme Gyro: I'm sorry. Indelible Raven: Just a lambda function. Supreme Gyro: Lambda? Yeah, I don't remember the lambda. Okay hold on. Since we're kind of crunching time here, can I just do that later? Indelible Raven: Yeah. Supreme Gyro: Now let's just assume that this priority 2 is working the way we're intending it to work and we obviously want it to be a size K. Okay. Now as we iterate through these points instead of storing anything in distance, let's just do the old distance. Print current min, sure. The next is going to be queue... priority queues use pop, and they're pairs. So if the new distance is less than... what if they're the same? I guess we can just ignore it right? We don't care if... like if we have three points and K is 2 and points 2 & 3 are the same distance, I guess we just don't care right? Indelible Raven: Yeah. Supreme Gyro: Okay so we'll do queue dot pop. We'll make a new pair using that new X... oh actually no, we already have points, it's a new point, that's right. So pop and then push that new point on. Indelible Raven: Is your comparator going to say that, hey I want to re calculate the distance every time? Supreme Gyro: Yeah, that looks like what it's doing. Square root and pow are a little bit expensive, we could probably optimize that further. Possibly instead of forgoing a map entirely, we might be able to use the map to have distance to pairs, but let me come back to that in a second. Well what if queue size is greater than K? Then you can pop. Otherwise you don't need to pop, you can just push. Right okay. So that looks good instead of pushing this onto the memo. So now we just need to get all the points from the queue. Okay, and yeah the rest of our code should work, assuming queue works. So, we are recalculating distance every time for the Q, let's see if we can optimize that further. Indelible Raven: I think I am happy with this, so we should stop. I do like the typical 45-minute interview, where 35 minutes is tech and then I get into your feedback if you want to hear it, and then give you a chance to ask any questions and discuss any feedback. Do you want to hear it or? Supreme Gyro: Yeah, absolutely! Before you do that though, I do just want to mention, and you already mentioned I think, you know the time complexity of this is O(n log k) and the size is O(k). We wanted to use this hash map for other stuff, then the size could go up a bit. Indelible Raven: Yeah, cool. So I guess for me and my feedback, I've never seen someone solve the square root like that, I thought you were going to do a binary search. It's very similar, but it's not. But it's a cool implantation, it clearly works. You'd have to figure out how it works with the underneath one, but. Supreme Gyro: Yeah, I've done the binary search method before, but I think this actual has better time complexity. I think this is actually O(log(log n)), but I'm not a hundred percent sure. I'm not like super into numerical analysis, I just read it in passing one time. With that said, the whole less than one thing, I think I just remembered a way to fix it, so I'll definitely take a look at this afterwards. It's in regards to... because this algorithm, you can actually use it to find any root, like you can find the tenth root, all you need is multiply a by some n minus or something. So I think that may have been the issue, but I'm sorry go, please continue. Indelible Raven: No, I liked it. It was a good implementation for sure and I'm gonna have to look into this myself because I've never done that. I've always done it with the binary search, but if it's better... it'd be neat to know it. Anyway, couple of things I've seen throughout is one, you don't really check for edge cases at all. Like, one thing that I kind of look for in the beginning is like hey, this is the question I understand it, here's what the input is, output, edge cases, here's the potential solutions I would use. Here's what I'm going to use because of X, alright let's code. You're just kind of missing the edge cases and the proper testing of those such cases. One other thing I would note would be, it'd be nice to have a little bit better, cleaner code, like better variable names and stuff like instead of A, B, and E, just like left and right, or low and high, and so on. One thing you gotta remember is if you go to the hiring committee several weeks down the road, you have to assume that people will be looking at your code that did not interview you and you want them to be able to read it. It does look like it follows a style guide some pretty well, just not the variable naming. So for K nearest neighbors, K closest points. I would trying to step back and practice lambda functions and functions in general in C++. Oh also, exception handling is one thing I would look at as well because you... yeah you were mixing up Java and C++ and yeah, I would just take a look at how exceptions are done in C++. Yeah, I know I'm jumping all over the place. So anyway, back the K closest points. I'd look at lambda functions or std functions, see how they work and then down here this is a little weird, you're checking to see if the distance is less than min distance. What I think you're wanting to do is max distance, but I would have put this size of K above it instead of below and said hey, this is the first K, then everything after check that the distance is less than, not the other way around. One thing I did notice beyond, hey we're re-comparing every single time with the square root and all that is what if I did this instead of XY coordinates, what if I did like 10,000 dimensions, instead like X 1 2... X 10,000 right? It gets a bit costly, right. Even when you were doing the map where you did the distances pair, you're still copying the pair each time. One thing I would note, instead I would do... think about like the size of the data and say hey, instead of that let's just keep the distance and maybe the index of where the original point is. So, at this point I'm kind of nitpicking because you actually did really well, I would definitely move you on to the next round, so nice job. Supreme Gyro: Okay, thank you so much. Indelible Raven: Anything you want to comment, on any questions you have? Supreme Gyro: I was just wondering if you want to tell me what company you work for? Indelible Raven: Right now I guess I don't. I was at Microsoft last week, but I'm switching up jobs so I'm kind of in the interim vacation right now so. I worked at Google and Microsoft before this. Supreme Gyro: What did you do specifically? I have a couple of on-sites coming up, that why I am on this platform, studying. Indelible Raven: Sure, so Google I worked on YouTube's enforcement team. I was responsible for taking down spam videos and any video that was flagged that wasn't content related, so stuff like DCMAs did not go through us, but like porn and spam and anything else like harassment stuff did. I dealt with the Machine Learning side of that. At Microsoft, I worked on SharePoint. Some of the networking stuff and like the development infrastructure. So more of, hey let's build tools for other devs to do their work. Supreme Gyro: Okay, that's cool. I was just curious. Indelible Raven: Oh yeah, no. Yeah now I'm going somewhere else. I'm in a quick vacation. Vacation that apparently I decided that I was going to be sick during. Supreme Gyro: Ok, I just recently got out of the plane, so I understand. Indelible Raven: Yeah, any other questions? Supreme Gyro: No, I think I'm good. Indelible Raven: Awesome. I think you'd do well enough to obviously make it on-site and I think if you were doing it on-site with me at your level, I might say you were a weak hire, saying hey yeah let's uh let's move them forward to hiring committee so, there are a couple things that I was nitpicking on, if you did well in that, you would be much stronger of a hire. I didn't see it just quite yet, so. Supreme Gyro: Yeah, I'll take a look at that stuff. Indelible Raven: Yeah, if you're able to rewatch it and everything and see what you did, so cool. Anyway if you don't have any other questions, I'm going to jump off, write your feedback. It'll be along the same lines, but you can review it later as well. Besides that, I wish you the best of luck on your on-sites. Supreme Gyro: Yeah, thank you for your time. You have a good one. Indelible Raven: You too, bye.