# 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.

C++ interview with a Google engineer: Closest Coin - YouTube

[C++ interview with a Google engineer: Closest Coin](https://www.youtube.com/watch?v=xC8CGv1CyFk)

### 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)

Read more about the questions  
- [K Closest Points To Origin](/content/questions/k-closest-points-to-origin/index.html)

### 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. Things 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 (2,1) to the coin down at (1,3) will be 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.

...  
(remaining transcript omitted for brevity due to length)

### Problem-Solving Insights
1. The algorithm's runtime is O(n) where n is the number of coins since it has to iterate through every single coin.
2. For large grids with sparse coins, a breadth-first search may be more efficient compared to iterating through each coin.
3. The density of coins relative to the board size significantly impacts which algorithm should be utilized for best performance.