Java Interview with a Google engineer

Watch someone solve the highest peak 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

Highest peak

Interview question

1) Given a 2D array of true and false, determine the height of the highest peak where true represents water and false represents land. The largest transition between land heights can be at most 1. 2) Determine the highest peak and optimize for the most beaches. A beach is any land with a height of 0.

Interview Feedback

Feedback about Analog Nebula (the interviewee)

Advance this person to the next round?

How were their technical skills?

4/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

Good stuff: - The candidate came up with BFS witout any hints - Good use of helper classes - Nice intuition about solving the extended problem Possible areas of improvement: - The candidate checked some corner cases which is good (though I assume H == 0 check should go before accessing map[0]), but missed some other (e.g. what if we don't have any water tiles?) - A bit of a premature optimization with the extended problem: it's always better to have working non-optiomal solution than to have non-working optimal solution:)

Feedback about Ironic Bratwurst (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

1/4

How good were the questions?

1/4

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

1/4

1/4

Interview Transcript

Ironic Bratwurst: Hello.

Analog Nebula: Hello.

Ironic Bratwurst: Hi, can you hear me?

Analog Nebula: Yes, I can hear you.

Ironic Bratwurst: My name is Andre, I work for Google, and we can have a mock interview today, okay? What programming language do you use usually?

Analog Nebula: I use Java my name is Orcom by the way. I have some interviews coming up in about a month.

Ironic Bratwurst: So are these onsite interview or is it phone?

Analog Nebula: It's gonna be an on-site interview. So just for reference, I have about four years of experience. I'm interviewing for backend position and so onsite level three, okay?

Ironic Bratwurst: Okay, sounds good. So if you are ready, then we can start. Okay, so maybe for the beginning, just like as a warm-up, can you name some of the sorting algorithms you know? Just main idea, complexity.

Analog Nebula: Sure, quick sort, merge sort...

Ironic Bratwurst: Can you quickly explain like the main idea here?

Analog Nebula: Sure, quick sort, we can do it the good quality in place with constant space and O(n log n) time, so what we do is basically we use divide and conquer idea, and what we're trying to do is we take one piece, we generally divide... so given an array, we pick an element, and then we try to put all the values smaller than that element to the left and all the values bigger than that element to the right of that value and then we do the same thing for the left side and the right side.

Ironic Bratwurst: So what's the complexity of this operation when we move to the left?

Analog Nebula: So that's going to be O(n log n) time.

Ironic Bratwurst: I said specifically of this operation.

Analog Nebula: Oh, of this operation. That's going to be one thing to do it O(n) time. So we're going to do one of them in O(n) time and we're going to...

Ironic Bratwurst: Quickly explain how they do this in linear time.

Analog Nebula: So this operation in linear time? So there are two ways to do it. So we select this value called pivot value. There are two approaches. Either we can pick it randomly any value in the range or we could just pick any value, like let's say the first value and what we do, let's say we pick the first value and then what we do is that we maintain two pointers: one to the beginning of the array, I mean assuming we skip the first one start at index one, and one at the end. And what we do is we move the left one to the right until we come across a value that's bigger than the pivot value and we move the right pointer to the left and keep moving to the left until we come across the value that's smaller than this pivot value and then we swap them, and we keep doing that. And at the end we swap the pivot value with the with the larger value pointer.

Ironic Bratwurst: Yeah, okay, so can you name any sorting algorithms that is slower than O(n log n)?

Analog Nebula: Slower than O(n log n), that will be from like bubble sort.

Ironic Bratwurst: Okay, so what can we expect from bubble sort.

Analog Nebula: It's O(n^2), all insertion sort.

Ironic Bratwurst: Do you know any algorithm that's faster than O(n log n)?

Analog Nebula: Yes, there's counting sort, that is O(n), but there's space complexity, that is that it can be large. So what we do is we maintain an array at the size equal to the largest value and then we're basically count how many times each value appears and we increment the value in the corresponding index of the array and then we go over the array and then we count each value and return how many times we saw it.

Ironic Bratwurst: Okay makes sense. Okay, thank you. So yeah, I'll paste the question.

Analog Nebula: So given a 2D array where true represents water and false represent land, generate a map with the highest possible peak. Rules are, the height of any water cell is zero. The height opening land cell cannot differ for more than one from any of the neighboring sharing one inch cells. So false represents the land. Okay, so I want to represent the height thing for the land, the height of inner lands cell cannot differ for more than one from any of the neighboring. Okay.

Ironic Bratwurst: Yeah, so for instance, you have a sample map for the input provided. This is a valid map and the second one is not valid because you have two, which is different more than like one.

Analog Nebula: So yeah, so the water is always going to be zero. So if it's true, it is always going to be zero and if it's not true, then the neighboring cells, the difference between the neighboring cells has to be at max one. And does it need to be bigger? It needs to be bigger right?

Ironic Bratwurst: Your job is to generate map which follow the rules and which has the highest possible peak, right?

Analog Nebula: So can you repeat the question again, what am I supposed to return?

Ironic Bratwurst: Basically the height of the highest possible peak.

Analog Nebula: Okay, so I'm given like this...

Ironic Bratwurst: If you generate all possible maps which satisfies this rule, and then of all this maps you calculated the height of the highest peak, so you need to return the one that's actually highest.

Analog Nebula: I see okay, so I'm given this one, and I need to return if I were generating the highest peak, what would be the height of that?

Ironic Bratwurst: Yes.

Analog Nebula: Okay, sure. Okay, so what should I do if... wait a minute. I see. okay. So let's see. So I'm gonna be given a 2D array. So it's a 2D array of true/false values, and the neighboring. Okay, so let's see. First example for this one, so this is gonna be zero and this is gonna be zero, so this can be at max one. So when we see a neighbor, we look right left, so we do horizontal or vertical, or no diagonals.

Ironic Bratwurst: Mhm, no diagonals.

Analog Nebula: Okay, so this can be one. And this one, we look at the left, right, bottom, top. So this is one. So this can be two. So how about this one? This is two, this is zero, so this can be only one. So this cannot be two. Okay, so let's see. So this is one. So what we don't know this one and what can it be? Okay, so there's two sides to this problem. There's this one thing where okay, so we generate, so there's this question of how do we start. So what we probably need to do is we start assigning values, right? So we know the trues, right? If you did see, we know it's a zero. So what we can do probably, we can start from the neighbors of these true values and then we can start setting values for the false values neighboring to the true values. But to state in a more abstract way, we need to start assigning values to the ones that we can, if I may. So let's see... but here's the thing. So well let's say this is true, okay this is true, so this is zero. So how about this one? So we can go ahead and set one to this one right? So there's no need to think about this one. So as long as we are sure that we can start from this one, that is that we should not do this one before this one, we can just just set one, right? So all the values, all the false values next to the true values are going to be one, for sure. Okay, so we can start from there. Okay so I need some space here to kind of test out some things. Okay, so let me use additional one. So what I'm going to do is, this is so... let me do this... Okay, so this is zero and zero. And then so neighbor to the zero, this is neighbor one, one, one. Okay. Now which one is going to be next? Now that is an interesting question. Now if it was this one, so this is a false and so we want to assign... so if we know this is one, this can be a max two, so it cannot be higher than two. Okay, so what it means also is that any value next to one can be at max two, right? So what we can do is just okay, we start with the zeros and we pick all the elements next to zeros and set them to one. Okay, then we pick all the values that are next to ones and set them to two. And then so on, like two to three three to four and so on okay? Now the question is, how can we do this? So I think this reminds me of a version of the topological sort where what we do is we store... so what we do is go ahead first, pick the initial values, which is going to be the true values and put them in kind of a queue. And then what we do is we go ahead, maybe not topological sort, but let's yeah... yeah, okay. So we pick the value from the queue, so first we do this, so for this example, we're gonna have two values in the queue. Then we pick the value from the queue. And then we assign a value to it.What we do is we we put in a queue, but we also put in a queue like the previous value there as well. Or we put there the value that there should be, we're gonna already know that. So and then when we would pick that, so let's say we picked the first trues. What we do is we go ahead and take all the neighbors of that value, we can store the x and y values, the indexes of that coordinate, we can pick all the neighboring ones and then put them into the queue, right? And with the value that they're supposed to be, which is going to be one bigger than the current one. And then we just need to maintain a visited, so that we don't put duplicate times and when we pick from the queue we're going to check does this have one, if yes we're going to skip that, and then that way we're going to just keep visiting all the values and we can maintain like a max value integer that's going to store the maximum value and then we're going to return that max value.

Ironic Bratwurst: Okay, yes that sounds good, so what's the algorithm? So what algorithm is that?

Analog Nebula: So this is a breadth first search.

Ironic Bratwurst: So what's the complexity?

Analog Nebula: So the complex is going to be O(n) in time.

Ironic Bratwurst: Where n is what?

Analog Nebula: N is the total number of elements in the array. And the space complexity is going to be the O(n) again.

Ironic Bratwurst: Okay yeah, sounds good. So can we implement the solution then?

Analog Nebula: Yes, so let's go ahead and implement this. So how am I given the input?

Ironic Bratwurst: Yeah, just 2D array of boolean. Is map a reserved word in Java?

Analog Nebula: I think it's a map, it's fine. So what we're going to do is we're going to just iterate over this and set a value and then first we are going to need a... so in order to put it into the queue, we're probably need to define a separate class. So because we're going to solve the step difference where we're going to store the next value. So let's also define that. So let's do private static class. Call it node. That's fine. What else would we need to have we need to have? It needs to have the coordinates so that I can take the the next ones. So int i, j, what else do I need to store? So I need coordinates, I need the next value and I think that is it basically. So what I'm going to do is so I will along the way I will need a function that is going to get me the neighbors but I'm going to get to that in a moment. So first what I'm going to do, I'm going to define this queue that I'm going to use and to do that I'm going to set the queue of nodes. So there's a couple of ways to use this queue. One of them is like queue interface with a link list. I like to use this one because this is after though not thread safe. And then we're going... okay, we need a visited one. So we're going to maintain a visited. That's going to be the same two dimensional array. It's going to be of the size map.length. So let's do this. So water is true right? what I'm going to do is. There might be a few edge cases, but I don't think that's going to affect the algorithm, so I'm going to consider them at the end. Now one thing we forgot to do... okay is there any need to actually maintain the output map, like one and zeros? Let's see. I'm going to go to neighbor's. Yes there is because I'm going to... Hmm is there a need to maintain that? So I'm not going to maintain the actual map of the ones and zeros. I think we can we can resolve it without. So, because I'm using the visited, I'm going to know... so the downside is that... is that a downside? Not really. So I know the current value. Here's the thing, so I'm going to have this, so let me know this. I'm gonna have this method that's going to get me the neighbors. So it's going to be the list of coordinates basically that is i j, so we can do list of integers. We don't need to pass the map, we can just pass the heights value. This is going to return me all the values that are nearby. And then I'm going to implement this in a minute, so let me first get back to this. So what this is going to be is this is going to do something now so I can get the neighbors. I'm going to do four. And then I'm going to. So for every element, I'm going to add this to the queue. So I'm just going to use it for now like this. So okay and then we're going to basically turn our next value. So there are a couple ways to do this since we're doing just horizontal and vertical. We're hard coding four, which is not a great idea... But if we decide to change...

Ironic Bratwurst: Given that we always have four, so that's kind of reasonable, right?

Analog Nebula: I mean, so what if I'm like what if we change it so that all you can go to diagonals as well, so that's why. But for now, I think we can assume this. So okay, so what we're going to do now is we're going to check. So one thing we're going to check, so what is it that we want to do. Okay, so this looks like it, but let's quickly go over. So this is gonna be true or false, so values can be a... we can basically change this to either zero, so we can set this to zero as well. It's gonna be maximum is always equal to zero. So we defined each plane. So above the input, can I assume that there's gonna be like non empty inputs, or should I take care of that? Should I return something here?

Ironic Bratwurst: Yes, sure.

Analog Nebula: Okay, so what we do basically is we create this visited. And then we go over the array, we pick the value that is equal true and we add them to the queue first. So these values we already know.

Ironic Bratwurst: Can you run this for the the example I gave you?

Analog Nebula: So let's do this. Okay.

Ironic Bratwurst: Okay, cool. The only question I have is with visited. My question is do we need it? So basically when you add things to the queue, you always add the nearest neighbor.

Analog Nebula: Yeah, so we can check that and not add them. So we're only going to add them if they're not visited. So then the question would be do I need this one though? And then like get rid of this.

Ironic Bratwurst: Just make sure you use the right coordinates.

Analog Nebula: Yeah, so... I am going to to yes, so what I'm going to do is this one.

Ironic Bratwurst: Yeah, okay yeah cool so additional question. So basically the problem is the same but we had also have a second optimization criteria. We also want to maximize the amount... So basically let's say... Let's define every land point as a height of zero, so it's like beach. So we want to still have the highest peak possible but we also want to maximize the amount of these.

Analog Nebula: So we'll if you want to add secondary optimization goal, maximize amount of features land tiles with the height of zero. Tiles with the height of 0 while keeping max peak height. Okay so, what would be the beach? Right next to the water?

Ironic Bratwurst: Not necessarily, any land tile that is the height of zero.

Analog Nebula: Any land of height 0, okay...

Ironic Bratwurst: When you generate maps with the highest peak, it might be that you can generate many maps which all share in the same height of the maximum peak. And then of all this kind of maps, I want you to pick the one where we have the maximum amount of beaches.

Analog Nebula: Maximum number of beaches?

Ironic Bratwurst: Maximum number of tiles with height 0.

Analog Nebula: Okay, so the idea is that like next to the water, I could have either zero, like land next to the water could be either zero or one, right?

Ironic Bratwurst: Yeah.

Analog Nebula: So if it's zero, then that's a beach.

Ironic Bratwurst: Yeah, it does not have to be near the water.

Analog Nebula: Right sure, like okay, it does not need to, we can set all of them as zero, and so that's going to be valid?

Ironic Bratwurst: Yeah, right. The only problem is that you need to also maximize the height of the peak.

Analog Nebula: Exactly, we want to have the maximum height at the same time. So the idea is, so what is the question how?

Ironic Bratwurst: How would you do this?

Analog Nebula: How would we do that? Okay. So how can we change in order to maximize my number of number of beaches? Okay, here's the thing, let's say we generate this, right? And then what we could do is we could like, this is one way - I'm just brainstorming, we could try to go back and like set some of the ones to zero, right? That would be one approach. But I need to make sure that I am maintaining the rules. So, in order to do that, there's going to be... So when when I'm picking the maximum one, I'm just picking the one that is next to the water and adding one to it. So in that way, basically what I'm trying to do is I'm going to try to set the highest value to the land, right? Land values maintain the highest value possible in any combination, right?

Ironic Bratwurst: So a small example might help you.

Analog Nebula: So let's say we generate... so the one thing I'm thinking is that okay we generate this, so we did this thing, maybe we can use the result of this in order to arrive at that one.

Ironic Bratwurst: So for the example they have, what do you think is the answer to that?

Analog Nebula: So this is going to be... So this needs to be one... And then this is going to be two. So maximum value is going to be two. So this is two and this is one and this is one. The rest of them can be zero. So what we could do... Let's say we generate all of them, right? So we generate what we just did. And then, let's say the value is three, the maximum height is three, okay. We could have a number of the three's in our max. We just pick one and we try to maintain that. The way we maintain that is we start from that one and make sure all of the values next to that one are one smaller and then values next to that are one smaller until we reach zero. And any other value can be zero. So we need to maintain that, make sure that all the neighbors contain the one smaller value, but not two, so the difference that's going to be so we can just maintain one peak and keep reducing the neighbors of that until we reach zero.

Ironic Bratwurst: So let's say we handle these peaks, what do we do next? In the procedure that you described, what do you do next?

Analog Nebula: What we do is in the meantime we take notes of all the values that we maintain and then we iterate over the math again, and if for any value that's not one of those values, we just set that value to zero. And then if we need to return number of beaches, for example, like we just do something, we count them. But one question becomes like okay, how do we pick the peak to maximize. Yeah, so how could we just make sure that we're picking the peak that is so that we maximize. Okay, so what is the difference? So difference is going to be, let's say for this case over here, the peak is going to be in the corner, right? So all we need is just these values next to it, and they can be one and one and rest of them can be can be zero. Well, we don't have a lot of choice over here. But basically what I'm trying to arrive at, by getting a value that's next to the corner, we are basically just reducing number of the heights because like to the top of that, or to the right of that value, there's not going to be another value. We could pick one way maybe, we could pick a height that is toward the corner, maximum toward the corner. Does that makes sense?

Ironic Bratwurst: Just to clarify, for each peak, we know how to calculate the maximum amount of height. And then we have a number minimum and maximum.

Analog Nebula: So what we could do, we could just iterate over each of them and like try each one of them and see like how many beaches we would get for each of them. And then like so... I thought maybe there's like a explicit quick way to know.

Ironic Bratwurst: There might be, but I'm not sure I can think of anything. Yeah, okay that sounds like a correct solution. Yeah, basically we go through all like the highest peaks and then we kind of go backwards.

Analog Nebula: So we select that as the only peak.

Ironic Bratwurst: Yeah. Okay, yeah. That sounds good. Do you have any questions?

Analog Nebula: No, not much. Just a couple of things. Like what do you think in terms of speed? Like what was it expected to implement let's say the solution that we talked about, like the last one?

Ironic Bratwurst: So one thing which is a big difference here is that, or usually in like Google on the interview, you don't really run the program that you wrote. Usually you just write the program and then you kind of you do like a mental compilation of everything. So probably that makes it a bit easier, because well, you can cut some corners and, so I'm not quite sure how to adjust that. So probably it will take you like a bit less time to implement your code. But I think you did like a reasonable pace. So that was the expected solution. Yeah.

Analog Nebula: So, I mean, like in order to implement the other one next.

Ironic Bratwurst: Yeah, so I don't expect anyone to do the second problem in in the forty five minute interview.

Analog Nebula: Oh well, so that was basically what I was asking. So within the 45 minutes, like what would you expect?

Ironic Bratwurst: Yeah, my expectation would be: implement the first solution and describe the algorithm to the second.

Analog Nebula: I see.

Ironic Bratwurst: I think that's reasonable to expect.

Analog Nebula: Yeah, basically so what do you think about in terms of coding. So is it clean or is it like something can be improved?

Ironic Bratwurst: The thing is, I'm not really that familiar with Java, so I'm not always know like the best practices in Java. But yeah, overall it looks reasonable yeah.

Analog Nebula: Okay, yeah and I mean yeah, I don't have much questions. Any other feedback?

Ironic Bratwurst: I'm gonna be able to give feedback after the interview.

Analog Nebula: Sure okay. So maybe one thing I can ask you that's what, if anything, that comes to mind, like what would you advise I could work on to improve in any way. I always like to improve, so like what would be your advice?

Ironic Bratwurst: Based on my experience, I don't know have anything in particular. You were as comfortable as I was expecting. But yeah, we only covered a certain algorithm.

Analog Nebula: I mean yeah basically, that's yeah sure, I mean that's from what you know, I mean, yeah like anything like you noted that could be improved. Anyway, yeah one thing maybe last thing I could ask you. So like for a person that has that four years, what kind of other than the regular coding like this one coding interviews would be expected? Like maybe not too hard of a system design, but any kind of other like caliber of questions that are being asked?

Ironic Bratwurst: I guess they are usually like one system design and three or for coding interviews.

Analog Nebula: And what do you think about, so we just have like five more minutes I'm just counting towards the end of the hour that's why I'm like I'm curious about a couple of things about Google specifically. So like let's say I go to interview and there's gonna be I think four technical interviews and one behavioral interior. So from those technical, so let's focus on technical one, like how many... let me ask you the other way... how bad could I do and still get a good enough feedback to get an offer.

Ironic Bratwurst: So basically what could happen like that. So somebody interviews you. Then they write feedback and they say well I the questions. Then they maybe they point like okay here candidate, come up with a great algorithm quickly, great, or maybe if I describe a lot of hints for him to achieve that. And then you have a hiring committee. They look through all this feedback and they think okay, what do we think is the reason why we should hire him. Obviously there is no kind of easy way of saying hire, no hire. Otherwise it wouldn't spend so much effort and time of the highly paid individuals which goes into hiring people. Easy way of saying, okay can we calculate some numbers and if it's more than 10, then we hire, if it doesn't then not. Obviously we should do something that they would much rather do that, than spend an hour or so yeah engineering time yeah.

Analog Nebula: I see your point and that totally makes sense. If there was one quality you think that is like probably most important, what would that be?

Ironic Bratwurst: Well again, being able to solve the problems and write the code.

Analog Nebula: Because they do behavioral interviews and that's like the ask the person to describe a moment when you have this, I think that's more of like they want to understand like your business ethic, like how you work with other people and stuff like that, so I'm just wondering like is that how important that is during the evaluation.

Ironic Bratwurst: I never did them. I guess that they brought this in not very long time ago.

Analog Nebula: I was told by a recruiter that I'm gonna have that one.

Ironic Bratwurst: Sorry, I cannot tell you much about it, but that's not technical, right? It's more like yeah do you really want to work for Google?

Analog Nebula: It's more of a leadership thing, I think. Like describe a the time when you had like a conflict kind of or you had a hardship on a certain project, how would you deal with that kind of stuff. Yeah, I mean those are things, but other than that, thank you for your time. Thanks for answering my questions.

Ironic Bratwurst: Yeah, no worries, have a good one.

Analog Nebula: Yeah, alright, thank you, you too. Bye.