C++ Interview with a Google engineer

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

Interview Summary

Problem type

Closest coin

Interview question

1) Write a function to determine the coin closest to you from a list of positions using Manhattan Distance 2) Find the cutoff at which to switch over to a breadth first search algorithm 3) Determine which is the optimal coin to collect when there are opponents present (each opponent only collects one coin)

Interview Feedback

Feedback about Sergeant Koala (the interviewee)

Advance this person to the next round?

Yes

How were their technical skills?

3/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

Very well done. You did a good job of explaining your thought process throughout and coming up with a working solution. As the problem got more vague and open-ended, you asked the right questions to disambiguate things and move towards a suitable answer. My only suggestion for improvement would be in the coding speed of the initial algorithm. It felt just a little clunky, for example first iterating through the elements in the list and then changing it to iterating over indices. Thing like iterating through containers, finding min/max of a list, etc, should come really fast. I'm sure with time it will get simpler. Keep up the good work!

Feedback about Intergalactic Avenger (the interviewer)

Would you want to work with this person?

Yes

How excited would you be to work with them?

2/4

How good were the questions?

3/4

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

3/4

Good interview. Helpful feedback. Maybe could've provided a little more verbal feedback, I guess I'll see how detailed the comments are on the feedback sheet.

Interview Transcript

Sergeant Koala: Hello?

Intergalactic Avenger: Can you hear me?

Sergeant Koala: Yes, am I loud enough?

Intergalactic Avenger: Yeah, I can hear you.

Sergeant Koala: Okay, great yeah. It was mad at me. It was telling me I wasn't loud enough.

Intergalactic Avenger: So, are you familiar with the platform and how it works and everything?

Sergeant Koala: Yes, I have done one of these before, so this will be my second one.

Intergalactic Avenger: Okay, well I hope this one goes as well or better than the last one. So, I see that you've already picked C++, bold move. I like it. So, I'm just going to dive right in with a technical question, unless you have any other questions?

Sergeant Koala: No, go right ahead.

Intergalactic Avenger: So, this is going to be kind of an algorithms thing. The idea is you're kind of writing an AI for some sort of 2D map game, where you have a grid. I'm just gonna draw out the grid here. So you're going to have this 2D grid that you can sort of conceptualize. And, you're going to have your position somewhere on that grid. And let's just say there will be these coins strewn about in the space. You're going to want to collect these coins. So you're moving around on this grid and you're finding these coins. So, let's start with something pretty basic and let's just say given the positions of all of the coins in the grid and your own position, find an algorithm that will find the closest one. And let's just say for purposes of this exercise, let's just use the Manhattan distance. Let's just say you can only go up, left, down, right. So for example, the distance from x to y, which is (2,1) to the coin down at (1,3). We'll just say that distance is 3, which is one left and two down. Does that make sense?

Sergeant Koala: So essentially the distance is just the difference between x0, y0 and a coin at x1, y1. Then it's just like (x0 - x1) + (y0 - y1). Something like that?

Intergalactic Avenger: Yup, exactly.

Sergeant Koala: And so you're telling me that I know the location of all of the coins, I have an array of their locations let's say.

Intergalactic Avenger: Yeah, let's define a couple of classes here to help this along. So we'll just create a class Point which will have int x,y. And let's say that what you're trying to do is return the Point closestPoint() given your position and a vector Point, which is the coin positions. You're going to return the position of the coin which is closest to you.

Sergeant Koala: Okay, I'm assuming we have some sort of constructor for Point?

Intergalactic Avenger: Ah, right yeah. Or you can write one. However you want.

Sergeant Koala: Let me so, so my input is the vector coinPositions. Okay so, I get my position and a vector of their positions and I need to return a coin that is closest to me. Well actually they're public so I could just say... I could just put those at the bottom once I figure them out. Okay, and then I would just return result at the end. Okay so, in terms of developing this algorithm, two things initially come into my mind. Obviously the simplest solution is to do the algebra for each point and keep a running distance. So currently the closest one is 7, I'll calculate the distance to the next one. Oh it's 6, so I'll replace it or oh it's 9, so I won't. And then probably along with that shortest distance I'd keep a running index. The shortest one is the third index in the vector currently. And at the end I'd just grab the values from the third one in that vector and then I would return that. The other thought, which may be sort of overkill, I mean you can do a breadth first search and that would return the value of the closest coin. But given that we already know the locations of the coins, that would probably not need to be that complicated about it.

Intergalactic Avenger: Okay, let's try the simple one just so we're on the same page.

Sergeant Koala: Okay, so for (Point p : coinPositions) so I'm just going to itteratate. I have to change this into a for loop with an i in case I need the index. I probably will, because I will need to change it from the index. Let's do int xDistance, int yDistance, and the xDistance is going to be equal to yourPosition.x - p.x and then yDistance is equal to yourPosition.y - p.y and then totalDistance is equal to xDistance + yDistance. That's pretty much the algorithm that we talked about in terms of calculating the distance. And then now that we got the totalDistance, we'll start out with... I'm trying to think about if I want to subtract them the other way. For example of the case of I'm at (1,1) and the other ones at (3,3). That would give us a negative number for each of them, and we don't want a negative distance. But of course it could be the other way. It could be (3,3) and (1,1) and then I did it the other way. So I think I'm gonna take the absolute value of each of these, because that way I get the actual difference between then, and it's always going to be a positive number. And once they've been absolute value'd, I don't need to do it for that one. And then I'm going to define up here int shortestPath = 0. That'll indicate that it'll be the length, so that will be that. And then int shortestIndex = -1 at the moment, because I don't have one. I'm going to change this for(unsigned int i = 0; i < coinPositions.size() i++);. because size() returns an unsigned int and otherwise the compiler will complain about that. And then the first thing I'll do is I'll grab that Point p = coinPositions[i]. I've got that. And now I can determine if I want to use this distance. if (totalDistance < shortestPath). Oh that's a problem, shortestPath should not start out at 0. I'll have it start out at -1 to indicate that we do not have the shortest total distance. if(shortestPath == -1 || totalDistance < shortestPath). And then I will say that shortestPath = totalDistance and shortestIndex = i. shortestPath was my overall shortest path and totalDistance is the one I calculated here. So shortestPath becomes totalDistance if totalDistance is shorter than current shortestPath or if the shortestPath is uninitialized. So that seems like that would work, and then... Yeah, we missed a bracket there, so we'll get that bracket there so these brackets match up and those brackets match up. Then after I've gone through all of the points, I should have the shortest distance. Then I would actually want to declare shortest distance as these two... Those need to be outside of the for loop or they would go out of scope, which would be silly. Use them later, which would be bad. And then, that's next to that. And once I've gotten out of this, shortestIndex is really the thing I care about. result.y = coinPositions[shortestIndex]. This is all constant time. And then yeah, I just return result. I think that should work. Let me try an example. For example, in this case I'm at (1,1) and coin at (3,3) and (5,5). Well I'd go through, and I'd first have a coins at (3,3) and so I'd calculate the xDistance, would be myPosition.x, which is 1 minus 3, so I'd get -2, so I'd get an xDistance of 2. yDistance would be myPosition.y, so it would be 1 - 3 again. I'd get the absolute value to be 2. So the total distance would be 4 and then I see shortestPath is -1, so that would get set. And then I'd go through and the (5,5) would yield a value of 8, which would be greater than the total distance, and so that wouldn't change it, and then it should go down here, and then yeah. So that should work.

Intergalactic Avenger: Looks good. I'm just going to create a little... I'm going to take that example that you gave, and I'm going to... And let's see whether this can actually run. And then I'll say Point result = closestCoint(Point(1,1), coinPositions). You're at (1,1)?

Sergeant Koala: I'm at (1,1), yup.

Intergalactic Avenger: And then we'll put coinPositions. And then we will cout result.

Sergeant Koala: I think we might need another...

Intergalactic Avenger: Okay, let's see how this works. I don't think we need that anymore.

Sergeant Koala: Do we not need that anymore? Don't we need a ; after the class?

Intergalactic Avenger: Oh sorry, yes. You do need a ; after the class.

Sergeant Koala: Do you want me to go ahead and run it?

Intergalactic Avenger: We need a ; after this one too maybe? I don't know.

Sergeant Koala: I don't think you need it after main(), I think it's just classes.

Intergalactic Avenger: Oh no, I mean the constructor here.

Sergeant Koala: Oh, so actually this method Point closestCoin() is not in the class. I think it has to be in the class, doesn't it?

Intergalactic Avenger: No, I don't think so. Does it?

Sergeant Koala: I'm used to sticking the definitions into the .h file and then this would all be in the .cpp file, so I'm not entirely sure what the rules are if you stick it all in the same file. Let me just run it.

Intergalactic Avenger: Let's see what happens. Oof ouch. Okay, well.

Sergeant Koala: Missing terminating character.

Intergalactic Avenger: Oh well that's just for this. That was that line, that's easy.

Sergeant Koala: It's still upset.

Intergalactic Avenger: This is a pointer. That was my error. vector is not declared, so we need to add vector.

Sergeant Koala: I think I just didn't name something so that's what those first 5 are.

Intergalactic Avenger: Oh woah, what just happened? Suggested alternatives. vector was not declared. It totally was declared.

Sergeant Koala: I think you have to reset it. Point was not declared in this scope. Point result... Oh that has to be capitalized, that's the problem there. Error coinPosition was not declared in this scope. Oh I put an s on it, it probably should be... No, that should be the same.

Intergalactic Avenger: Oh no, it's misspelled, yeah.

Sergeant Koala: Where did I misspell it.

Intergalactic Avenger: Right here, `posisition. In 25. So 23... Yeah.

Sergeant Koala: Oh this is the issue.

Intergalactic Avenger: Yeah, and I think for these ones. Here's where autocomplete really helps. They should get that for CoderPad. That'd be cool.

Sergeant Koala: You hit the reset button and then hit run.

Intergalactic Avenger: Yeah, there's still a couple of positions misspelled. I think in yourPosition, there's an extra s in line 25

Sergeant Koala: yourPosition.x - yourPosition.y.

Intergalactic Avenger: It's position without the s.

Sergeant Koala: p o s i t i o n, right?

Intergalactic Avenger: Yeah, so there was an extra s in there, but I got rid of it.

Sergeant Koala: Oh okay, great!

Intergalactic Avenger: No matching function... Oh, yeah you have to give... Alright, thank you C++. We'll just do this then. Complaining that there's no 0 argument constructor. Alright, that's fine.

Sergeant Koala: Okay, and then the last thing it's mad about is error coinPositions... I probably misspelled that again.

Intergalactic Avenger: Yeah, I think it's just a copy paste with that extra s. And I think also shortestIndex. Oh, that's how it was actually spelled before.

Sergeant Koala: So it returned (3,3), but this is suggest parentheses around comparison, so it just wants...

Intergalactic Avenger: That's not a big deal. Okay, alright. (3,3), there we go. Oh, and one other little thing, I think it totally works in this case, but the single vertical bar is actually bitwise or. And so what it's going to is it's going to take the left side as an integer, and the right side as an integer, and do a bitwise or of those two integers. And that's fine, in this case it actually works. But it's kind of taking advantage of the fact that a boolean gets turned into a 0. Yeah, okay, looks good.

Sergeant Koala: And so I'm not totally aware of... Like in Java, the || is a logical or, is that also a logical or in C++?

Intergalactic Avenger: Correct.

Sergeant Koala: Okay, so if I want to do a logical or, I do that. Okay, that's good then. Yeah, that seems to work. Do you want to write some other test cases?

Intergalactic Avenger: Oh, no, no. I think we're good for that one. So now we're going to crank this up a notch. So first question is: What's the runtime of this algorithm?

Sergeant Koala: Okay. Well, it's going to be proportional in part to the number of coins obviously, because it has to iterate through every single coin. So initially, let's call the number of coins n. There are n coins. And then, it's going to have something also to do, hmm... I guess it doesn't really matter where they are on the board because I already know their locations. And regardless, I mean unless there's... Yeah, as long as they fit within an integer in terms of... Yeah there's a constant time amount of time it takes to run the calculations. You know, because it's distance minus these couple of lines of code here. So that's going to be constant time. So I guess this algorithm would run in O(n) time where n equals the number of coins on the board.

Intergalactic Avenger: Okay, excellent. So, let's say that this is a very large board with a lot of coins on it. Is this going to be a good algorithm for finding that?

Sergeant Koala: No, because you're iterating through every single coin. My initial thought is that if I got some massive board, I would want to maybe cut out a sub-board, like a 10x10 to start and see if there is anything within that board. Also I think breadth first search would look more and more favorable as the board got bigger and bigger, because it's just going to start at x and it's going to look at the squares that are adjacent to x and then the squares that are adjacent to those square and it will stop as soon as it finds a square. So it's going to stop and only hit one coin and if there is a coin relatively nearby, that could be a lot faster than computing the distance between it and a million coins or something.

Intergalactic Avenger: Right. Okay, sounds good. So, let's say, just kind of diving into this tradeoff a little bit. Let's say that it's a really large board but there are very few coins on it. So you mentioned two algorithms already, one that is the search where you look around in a physical way, and then there's the algorithm that you implemented. So which one of those is going to be better in the case that you have a really large board with very few coins in it.

Sergeant Koala: Okay, what do I know about the positions of the coins? Do I have any idea where they're located relative to me?

Intergalactic Avenger: No, you just know it's a big board and you know there's a few coins.

Sergeant Koala: Okay, well I'm going to assume that the coins are maybe on average half way across the board away from me, something like that. Especially maybe a little bit further because there's so few of them. And so, I'm going to have to go a long way and the cost of breadth first search expands outwards. Like, if I was in the middle here on this square. I would have to do all of the squares around me and it basically expands corresponding to the amount of area it's covering. So, in that case I would imagine that the coin algorithm would be better. I mean you said there aren't very many coins, but even if the board were full of coins, like every single square was a coin, then that algorithm would take, let's say the board was n x n, it would take n^2 time because it runs proportional to the number of coins, and there would be n^2 coins. But that's not the situation, there is massively less than n^2 coins, there are a few coins. There might still might be a million of them, but there might be a million of them and there's ten billion squares in the grid or something. And the breadth first search is going to take something proportional to ten billion to find the coin, maybe it has to search half the board around me, maybe it takes it five billion. So the coin algorithm I think would be better in that case. I mean the one I already have would be better.

Intergalactic Avenger: The first one. Okay. So, you've touched upon a very interesting point. There are cases where it's neither good for either one. There's still a lot of work that needs to be done. You talked about this one that's a million by a million wide and there's a million coins on it, there's no easy way to find it. But one of them is clearly going to be better than the other. So, let's just say that all you get is the positions of these coins. And you don't know how big... I mean you know, I guess we'll say you know how big the grid is. How would you choose dynamically which one of those algorithms to choose. So let's say that you basically are told that you want to find the closest coin. And you're given this information of the size of the grid and the positions of the coins. But it's a general problem. Sometimes you're gonna get a grid that's got tons of coins on it. They're very densely packed. And sometimes you're not. And you're gonna have to find some way to choose between the two algorithms.

Sergeant Koala: Okay so I know the size of the grid and I know the number of coins and their positions. Well, it sounds like it's kind of in a hash table and when the hash table gets too full it stops working properly because you get too many collisions. It sounds like I want to develop a ratio or density factor. This density factor should represent the number of coins per grid square. So something like coins / numberOfCells and beyond a certain point, if it's really dense, then I would want to use the breadth first search because there's probably one close by and correspondingly because it's so dense, there's a lot of coins. But if it's very sparse and there aren't very many coins relative to the number of cells, then I would want to use this algorithm that I wrote out.

Intergalactic Avenger: Okay, that sounds very reasonable. So let's dig into this ratio just a little bit. So the number of coins of the number of cells, and you will define some kind of arbitrary constant that that will be over or under in terms of your density to pick one or the other.

Sergeant Koala: I don't think it should be arbitrary.

Intergalactic Avenger: Well I guess, yeah. I guess you would have to find that somehow. And I haven't given you much way to pick that number. But one question I have is, is it that you're going to want some... Are you going to want to have it so if density < lambda, then you do algorithm one else algorithm two. But this is one way to do it. But is this the formula you're going to want. I guess the question is, this is setting up a linear function where there's this linear relationship between the lambda and the density and what point you have this flip.

Sergeant Koala: I think I see what you're saying. So as the grid gets bigger, tell me if this isn't where you're going with this. As the grid gets bigger, the breadth first search is going to perform poorly, not regardless of how dense the grid is. Obviously, if every single square is filled with coins, then no matter what the size of it is, the breadth first search is O(1). But, generally as you have a higher density level, there's still going to be more space. My intuition is that let's say that we take two cases, one where there's a 1,000 squares and then one where there's a 1,000,000 squares. And let's say that in both of them, the coins to cells ratio is 1/4, so there's one coin for every four cells. Now if we assume that the coins are randomly distributed, can I assume that they're not sort of clumped up or anything like that? Then, regardless of how large the overall grid is, there should be a coin about every 4 cells, which means that my breadth first search should have the same running time regardless of how many cells there are. I guess the difference is that the running time of my default algorithm in this case would be much worse because this is going to mean that there are 250,000 coins whereas this means that there are only 250 coins. So while the breadth first search should on average have about the same performance, because it's going to have to go about 4 cells, the cost in the naive algorithm let's call it gets much larger. So we want to include a factor here that represents the fact that the naive algorithm is more expensive regardless of what this ratio is.

Intergalactic Avenger: Okay, very good! And what's the proportion ehre. So, as the size of this grid increases and this density factor stays the same, how does the size of the naive algorithm grow versus how does the size of the search grow?

Sergeant Koala: I'm going to change this, I want to change c to be the number of coins on the board. So that's O(c). And then I'm going to say that n equals the total number of cells. So often times they say n^2 which is the length of the row by the length of the column. I'm just going to say n equals total number of cells. And I think from this example we can tell that as I increase the number of cells a thousand fold from a thousand to a million, that also increased the total number of coins by a factor of one thousand. And so it looks like the increased cost of the naive algorithm is proportional to the total number of cells. So if we increase the board a thousand fold, it increases the cost of the naive algorithm a thousand fold, given the same density.

Intergalactic Avenger: So that's excellent intuition, and now I think you've convinced that just looking at that lambda is not necessarily going to give you the right choice because it works well for some sizes of the boards, but not others. So how are you going to adjust that?

Sergeant Koala: Okay, so I've got the density is less than lambda, let's say lambda is something like 0.8, whatever it happens to be. And then, well I want to think about the absolute cost of the... I know the absolute cost of the naive algorithm. I want to figure out the absolute cost for a given size of the breadth first search algorithm. So if I have a thousand squares and we're dealing with the one fourth, then the cost of breadth first search is going to be four, and that was also true with the one million squares, it's also going to be four. My initial reaction to this is that it seems in most cases that the breadth first search is going to end up being better. But in terms of determining it...

Intergalactic Avenger: Well, if there's a million squares and there's three coins, the other algorithm is certainly better in that case. So there is a cutoff.

Sergeant Koala: That's true, I'm looking at it as 1/4 or 1/8.

Intergalactic Avenger: Yeah, you're certainly right that as that coins per cell number stays the same, that much more often, and as the board grows, it certainly becomes more and more likely that the search algorithm is going to be better. But there definitely is a cutoff.

Sergeant Koala: So if my density is 1/4, density * n is the total cost of naive, right? Because the cost of breadth first search equal... I feel like it's the inverse maybe of the density. So if it's 1/4, yeah it should just be the inverse of the density. So if density * n is less than inverse of the density, then I would choose that. So let's double check this. So for example, there's a 1,000,000/3 coins and the inverse of the density is some tiny little thing. I think that'll work.

Intergalactic Avenger: Yup, there you go! No, that's really good! There's only one tiny piece there that... So you have density * n~ < 1 / density. Can you rewrite that so it looks a little easier.

Sergeant Koala: You still want me to write it as 1/ density, or?

Intergalactic Avenger: So that's definitely right, so is there a little bit of algebra we can do here to make that a little bit... I mean this is very minor points, but um... So look at how density is defined.

Sergeant Koala: That's going to be, let's call it c/n. c/n is this thing. And I suppose I could also make the n's are the same. If I multiplied both sides by n, then this n would... No, no, no... It's 1/c/n which is the same as c I believe.

Intergalactic Avenger: Yup, and then what's this density here.

Sergeant Koala: And this has an n and this density is also c/n. So c/n * n, those n's cancel. So then this is c < n/c I guess.

Intergalactic Avenger: One other multiplication that you can connect to that.

Sergeant Koala: I mean I can multiply both sides by c and say c^2 < n. Like that?

Intergalactic Avenger: Perfect. And you can see here that you've essentially got the runtime of your algorithms on the two sides. So the runtime of your naive algorithm was O(n) and the runtime of your other algorithm is on the other side.

Sergeant Koala: The number of coins?

Intergalactic Avenger: No, the number of cells.

Sergeant Koala: No, I think c was the number of coins on the board and n was the number of cells. What happened? We did something...?

Intergalactic Avenger: Right yes, yes, yes.

Sergeant Koala: n is the total number of cells, c is the total number of coins. Or did I change these and maybe not change it here?

Intergalactic Avenger: Oh, I think it actually is the other way around. Because here they're both with c. Anyway, awesome. Very good. Now. One more piece that I'm going to throw in here, this is again going to be not so much about the coding, but about the methodology. So let's say it's not just you who is on this board. You have some competitors. And your competitors are also going after the same coins. And if they go towards a coin and everyone moves at the same speed, and if they get there faster than you, they take the coin and you don't get anything.

Sergeant Koala: So am I wanting to try to go to coin...? So there could be a lot of coins on this board. Are there a lot of opponents, or is there just one opponent?

Intergalactic Avenger: Well, I mean in the most general sense, there could be any number of each, but as we've seen, the relative number and the relative size do play a big role of which kind of algorithm you want to use. But let's just for sake of discussion to get started, let's just say that it's a board of this size that we have at the bottom, and that there's a small handful of opponents that are also competing with you for the coins.

Sergeant Koala: Okay, well I initially think I don't want to go fro coins that are far away from me, right? So, I think I might want to... I could essentially sort my list of coins by their distance from me. And then I could go through and calculate how close each of the coins is to an opponent and it gets complicated because you might want to think about the fact that if there's a coin that's really close to an opponent, but is relatively far away from me, and it's the closest coin to me, then he might go for that coin and then I could go to a coin that was closer to him, because I know he's not gonna... There's this coin that I want to go for is 10 squares away from him and is 15 squares away from me, but there's a coin that's only 5 squares away from him in the other direction, so he's probably going to go for that coin, so I can still go for the coin that he would otherwise get. So that's one thing that would make it complicated. But in terms of a simple first task, I think I would just get the coins that are closest to me and sort the coins by how close they are to me. And then I would look at them and see how close each of them is to an opponent and maybe provide an equal weighting. I could do two things. One is that I can provide an equal weighting from me to the coin and the distance from an opponent to the coin. Alternatively, I can eliminate any coin that was closer to an opponent than it is to me, assuming that they might go for it and take it before I go for it. The distance from the coin is say 3 for me and it's only 2 from the opponent, I'll eliminate that coin assuming that they're going to get it and I'll find essentially the shortest path to a coin where I'm closer to it than an enemy.

Intergalactic Avenger: Okay, that is an excellent start. So, you have this setup here. So you said that you're going to eliminate any coin that's closer to an opponent than it is to you?

Sergeant Koala: That was my initial thought yeah.

Intergalactic Avenger: So in this world, you get just this coin on line 87 here. That's what you get because the other people are closer to the other coins.

Sergeant Koala: Can they only go for one coin and then they're sort of sated or something?

Intergalactic Avenger: Let's just think about it in terms of a single one. Everyone gets a coin and then you move on to the next map, just to simplify it. So in this case, every coin is closer to an opponent than it is to you. So you don't win any of them outright. But, in terms of this sort of sating as you said, they're sated by the two coins that are closest to them, and that leaves this one down in the corner open to you, because they're not interested anymore.

Sergeant Koala: Okay, well I guess what I can is I could calculate, this is going to sound really computationally intensive, but I can calculate the closest coin to each opponent and assume that they're going to go for that one, and then I can eliminate that coin from my list, and then I could just of the coins that are left, choose the one that is closest to me. Now the one modification that immediately pops into my mind is that when I calculate the coin that is closest to them, I could check and see if I'm closer to it, because then I could just get it away from them before they could get it. But other than that, I think I would calculate the coin that is closer to each opponent, and assuming that I'm not closer to the coin than they are, then I would just eliminate all of those coins, then I would choose the coin that is closest to me of what's left.

Intergalactic Avenger: Okay, so I see that. But what about this one. See if I can move this guy down one to make the map a little easier. So you said you pick the coin that is closest to each opponent and then you eliminate it from what you have access to. So from that algorithm, this coin is closest to opponent number one, but this also closest to opponent number two here. So you would only end up eliminating this one coin from your search.

Sergeant Koala: It's an iterative process, so I would iterate through each of the opponents. Through each of them, I could calculate the currently closest coin to that one and then eliminate it, so I do this guy, I calculate the closest coin to him, and then I would eliminate it. So that would be gone. And then I do this guy, I've already eliminated that coin from my list or data structure, so then I would calculate the closest coin to him given which coins are left. Now obviously if I wanted to make this really comprehensive, I could try and figure out... There's a situation where I calculate this guy, and I think he's going to go for this coin that is closest, but actually there's another person who is closer.

Intergalactic Avenger: Right, I was just going to say that like what order are you... That would work if you are traversing this in this ideal order. But if you had accidentally picked this guy first, you would have said oh, his closest coin is this one over here and then actually that wouldn't have been the correct choice because another opponent who you would have seen later was actually closer.

Sergeant Koala: Yes, so I mean, this is really going to hurt the running time, but what you can do is you could go to a particular opponent, find the closest coin to them. You then have to check all other opponents and see if any of them are closer. If none of them are closer, then you would say this guy goes for that coin and gets it. Otherwise, you would take the other person who's closer and say, no they go for the coin and get it.

Intergalactic Avenger: Right right, so you're getting closer. Sometimes it's a little difficult to come up with the exact answers here. Okay so, let's say we have this setup. You start with this opponent. She is the closest coin, and yet you are going to give that coin to him, even though, he wasn't interested in your coin, even though he is closer to yours, he is still not interested in it, because he has one that is even closer than that.

Sergeant Koala: Okay, I think I need to for each play, calculate closest coins to them. And then, I need to iterate through the players and check if there is a player closer to my desired coin and is that coin their closest coin. So for example, let's say I'm starting on y. Or I can even do it on myself. So I've calculated out the closest coins to everybody, I say here's this coin, I wish one on this map would be closest to me, like this one over here probably. So, let's say that this one was farther away. So I start with this coin because it's closest to me and I'd say, there is a player who is closer, and it is his closest coin. Because it is his closest coin, because he is closer, and to be really sure, I would have to check that no one else was closer than him. So I'd have to check that for Y, all of the other ones aren't closer. Then I would say, he is going to eat this coin, so I can't go for that one. So then I have to get my next closest coin. Y has been removed because he is sated as we said, and then I would say, oh but this one is Y's closest coin, and he is closer than me. So because it is Y's closest coin, we know he is not going to go for another coin, he is going to try and go for this one and he is closer than me, so he is going to win, so I can't get that one either. And then these two are sated, so then I would say the next closest coin for me is this one, and by now I've eliminated all of the other players, so I wouldn't find another player that was closer than me, so I know I would be able to get it. So I would go for that one.

Intergalactic Avenger: Okay, yeah, no that's good. I think that will work. I think the typical way you would do this, and you're really close, for each player, calculate the closest coin to them, and then you sort by their distances. And so you know the person who has the shortest distance to their desired coin will automatically get their coin. And that's actually the only greedy thing that you can say at that point, is that given that group of people and the coins, the opponent or the person, it could be you or it could be one of the opponents, the person who is closest to their coin is going to get it. And then there's kinda something else you can say that at point, because there's all these weird corner cases and stuff. So then you remove the player and you coin, and then you have to repeat the whole thing over again. And then you have to find their closest coin over again, now that there's one less coin and one less person. And then you have to keep going down until you are the person who is closest to their desired coin.

Sergeant Koala: And that has a lot better running time than what I proposed because if I'm checking if there's a player who's closer to my desired coin, this whole step is going to take a lot more time than probably getting the group of people for a given coin and eliminating the person who is closest. As I have to calculate the closest coin to each player and then, yeah that makes sense.

Intergalactic Avenger: Yeah, and there's no quick and easy way to do it. They're all sort of computationally intensive. If you want the true and correct optimal answer, you can't get around the computational complexity. Okay, nice, awesome. That was it, that's all I got, did you have any questions for me or any thoughts before we take off? I'll put some notes in the platform later, but did you have anything before I go?

Sergeant Koala: Yeah, no, I mean, it seemed like a good question, I liked the little grid that you drew, and yeah I mean I'm just practicing interviewing obviously for job interviews, so if you have any suggestions you want to say to me now as opposed to writing them down, I'd be happy to hear them. Otherwise it was good, thank you.

Intergalactic Avenger: I'll fill out some more information, but in general, very well done. The only thing, and this is sort of a minor thing, is that if you are comfortable with other programming languages, they tend to be a little easier for these types of problems. So C++, there's a certain... It's nice to know that you have confidence in it, and it's definitely like a lower level language than something like Python or JavaScript or even Java or something like that, but the thing is that there are a lot of details, like this whole thing with looping through the array, like that's three letters in python, you know? It's all super, super easy whereas, there is a lot of remembering, like wait, it's called size() and all of this kind of stuff. That's really my only comment. I used to do a little bit more C++ programing, and I have done interview questions in C++ and I find that I end up spending unneeded mental energy just trying to get the stupid C++ code to compile, than I am on focusing on the algorithm and the technique, and all that kind of stuff. So yea, I don't know if you have another language that you're comfortable in that is a little bit higher level, but that can be something that is for a lot of these coding challenge style questions.

Sergeant Koala: Yeah, I suppose Verilog is not a good answer. So, I mean I've written the most code in C++ and Java. I have done a little bit of Python, but I feel more... I'm a student right now, and part of it is Python is something that I've done a little bit on the side, but the courses... I'm taking two different courses right now that use C++ right now, so it's kind of more in my mind right now than other stuff.

Intergalactic Avenger: Yeah, that makes sense. And you definitely do want to stick with something that you're comfortable with, because the other position you don't want to be in is you saying that you have familiarity and comfort in a certain language, and then you don't you remember how to do something basic, like how do you get the element out of an array, or how do you get the value for the key in a map. And if you don't have that really down pat, than that also looks a little bit bad. So, definitely #1, stick to what you're most comfortable with. Then I would definitely say going into it, especially with C++, you're going to want to definitely have all of your basic containers down, like vectors and sets and maps and all that kind of stuff. Just like how to insert, how to get elements, remove them, that sort of thing. That kind of stuff is ridiculously simple in things like Python and it's a little more involved in C++, but if you have it down and it's in your fingers, like I know exactly how this works, then it should be just fine.

Sergeant Koala: Yeah, my approach to C++ was that I'm going to use this for my interviewing language, and I'm really going to nail down all those little details, and I'll get it to the point where it's jumping off my fingers like that. Yeah, that was kind of my thought process.

Intergalactic Avenger: Nice, awesome.

Sergeant Koala: Yeah, thanks for taking the time to interview me, I really appreciate it. It was a great question.

Intergalactic Avenger: Yeah, well I hope you enjoy the rest of your evening.

Sergeant Koala: Have a good evening, bye bye.

Intergalactic Avenger: Alright, take care.