Java Interview with a Google engineer

Watch someone solve the max heap 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

Max heap

Interview question

Design a max heap.

Interview Feedback

Feedback about Double Pizza (the interviewee)

Advance this person to the next round?

How were their technical skills?

3/4

How was their problem solving ability?

1/4

What about their communication ability?

3/4

Pretty solid. It took a little bit of coaxing to get the second, optimal solution but you got there. And you obviously are very comfortable with Java, even the new Java 8 features, which is a plus.

Feedback about Intergalactic Avenger (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?

4/4

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

4/4

Really good breadcrumbs to get to the final answer. Hopefully I wasn't too infuriating to work with :-p.

Interview Transcript

Double Pizza: Hello.

Intergalactic Avenger: Hello, how's it going!

Double Pizza: Oh it's going, how are you?

Intergalactic Avenger: Pretty good, pretty good. Can you hear me alright?

Double Pizza: I can hear you, can you hear me?

Intergalactic Avenger: Uh yeah, it's a little bit... it kind of goes in and out a little bit but...

Double Pizza: Let me adjust mic, how's that?

Intergalactic Avenger: Okay, yeah that's better. Alright. So um, if you don't mind, I'm just going to jump right in with a technical question, if you're up for it.

Double Pizza: Yeah, sounds good to me.

Intergalactic Avenger: Um yeah, so are you familiar with the data structure called a max-heap?

Double Pizza: Max heap? Oh God, it's been a while... vaguely. I mean, I know binary heaps so yeah.

Intergalactic Avenger: Yeah okay, so um, so just want to yeah... I'll give you the brief overview of it and then we'll have you code one up maybe with a couple little tricks and modifications along the way. And we'll do this in a language, whatever language you are comfortable with, keeping in mind that it's going to be just sort of an algorithmic thing, so whatever like high leveling would just tend to be a little bit easier for this kind of thing.

Double Pizza: Okay, I mean I write Java in my life, so see how that goes.

Intergalactic Avenger: Okay, then let's switch over into Java mode and now you can take this little sample and just delete it or gut it and we can start writing our real stuff. Okay, so the basic idea with a max-heap or a min-heap, we'll just choose the max one, is that it's a binary tree where every node in the tree is larger than all of its children on both sides, so a very simple max heap would be something like 5 2 1 or something like that, so five is greater than 2 and 1 and then if it keeps going down then you could also have something like that.

Double Pizza: Just to be clear, the one on the bottom that on line 34, that's just a child of the two, not...

Intergalactic Avenger: Right, yeah. It's a binary tree. Yeah so you get the basic idea and so it's... it has this nice property that if you're trying to find the max of this collection of numbers, then it's always right at the top. But then there's some tricks with if you want to start adding numbers or subtracting them or popping them off, then some things get kind of hairy and that's the sort of thing we're going to go over today. So the first thing... one way to about how one would implement one of these things is a sub-problem and that is if you're given a... if you're given two pairs or two max-heap trees and you want to merge them together into one max-heap tree, how would that work?

Double Pizza: Okay, so if I was given two max-heap trees, how would you merge them together into one? Alright, well I'm just going to abbreviate this here. Alright, so my first thought is to figure out the total number, like the set of every value. Not set, list of every single value and put them into a new structure. So I will put this in kind of pseudo code right here... for each tree, for each element... and for everything in x, let's pretend I spelled that right... add that element to a new heap. Because I remember... God it's been so long since I took algorithms, is like a heapify thing to take... anyway let's just start. Can I just assume these are integers not any other?

Intergalactic Avenger: Yeah, that's totally fine.

Double Pizza: Alright.

Intergalactic Avenger: I think you mean the node first and second right?

Double Pizza: Oh yeah, thank you.

Intergalactic Avenger: And just to clarify, just to make sure we're on the same page. So the node is the representative of the root and then it's got all of the the children down beneath it. y

Double Pizza: Correct, yeah so first is the first even, or the root of first even. Second is the root of the second even.

Intergalactic Avenger: Yep okay.

Double Pizza: Alright. Now, I'm going to assume I didn't write there, that I could do that, that would be way too easy. This isn't going to implement... that's not going to work. Alright so my thought was you know I can recursively do like a... Oh actually, order doesn't matter, fine. I don't know if in Java it's called queue, but I know you can do...

Intergalactic Avenger: I think it's a deque. I think there's a queue and then I think queue is the old one and then there's one deque is the new one. Yeah.

Double Pizza: I'm going to look at the Javadoc, but can I just assumed there's a push or add?

Intergalactic Avenger: Yeah.

Double Pizza: Let's assume those exist. Alright, so we're just going to do like breadth first iteration of each list. Alright, so that will collect every element from our heap, from the first one.

Intergalactic Avenger: Are we assuming that getNext() is going to remove it from the queue?

Double Pizza: Yeah. I assumed that getNext() will remove it from and return it.

Intergalactic Avenger: Okay, that's fine, yeah okay.

Double Pizza: Alright. Now I wish I was in an IDE, because I'm going to start refactoring things. Oh this is going to be... okay that actually worked out fairly well. Alright cool, so now we can redo this list. Whoops. Okay so now we have a list that contains every element that we care about. One thing I'm going to assume is that if there are duplicates, they should be added multiple times right?

Intergalactic Avenger: Yeah.

Double Pizza: Okay, perfect. Okay, so now the real kind of crux of the problem is how do we generate a heap out of this. So, obviously the first thing is going to be the root right? Actually, the largest element is going to be the root. Oh, yeah okay. So I'm kind of thinking out loud now. So that little thing, just add that element to a new heap is really big, not very specific but that's you know good for you. Alright, okay so sort the list. Now from what I remember... right okay, so parts my algorithm class are coming back to me. I remember now that binary heaps have this really interesting property when you store them as arrays. So if you have 10 9 8 in an array...

Intergalactic Avenger: Then you can think of it that like 10 is the root and 9 and...

Double Pizza: Now it's coming back to me. The left child, or left child... left child of i is going to be an element of index two times i. And the right child of i is going to be at 1 plus two times i. Okay, right.

Intergalactic Avenger: Well so, this is true that you can think of a an array as a binary heap by doing this kind of indexing, but I'm curious as to what you gain out of that because we're dealing with a heap as a node class, we're not dealing with it as an array, so it strikes me that what you'd have to do is you'd still have to create a properly laid out max heap and then turn that into nodes, although I guess if you... yeah if you sorted it then yeah...

Double Pizza: I'm going to end up with this and then you can build...

Intergalactic Avenger: Yeah, that's an interesting approach, yeah okay I think that'll work.

Double Pizza: Alright, so... and then I can go over the array and sort. So I just want to convince myself that this work because I'm not 100% convinced of it. Although this is going to sort in the wrong order so.

Intergalactic Avenger: Yeah, I'm sure there's some way to.

Double Pizza: There is, you can do a new comparator. I could write all that out but this is way fewer lines of code. Okay so I just want to convince myself that this will work. So then this heap is going to be 10. This is going to be weird to format. And then 9 and then 8 and then 9 is at index 1, so it's... okay so I guess there's probably more than one solution right?

Intergalactic Avenger: There's definitely more than one solution.

Double Pizza: I mean more than one valid heap that's compliant.

Intergalactic Avenger: Yes, absolutely. But I think that if you do this sorting like you're talking about, then you know that all numbers... every number in your array is greater than every number after it and the way that you're thinking of the children is set up, then the children are always to the right of the root, so I think that's definitely a valid...

Double Pizza: Okay, so I've turned everything into nodes. So I'm going to add a constructor here. That will basically go through every integer in my all elements list, or my sorted list, all the constructor will do is return the new node and then build a new node list out of it, which Java makes so nice. Alright, so now we have to set up the links right? Okay.

Intergalactic Avenger: So this is just assigning the values to the...

Double Pizza: Yeah so essentially this will return my list that was like you know say 10 9 8. That will turn it into... so it's just convenient so that you don't have to write all the iteration code and it's awful. Alright, anyway. Okay, so... and we can leave the reference as null if it goes off the end of the list, because clearly that means it's a leaf. And just to be explicit, we don't really need this. Awesome. Oh this does not work because that would mean the left child of index zero is zero, so this is actually 2*i + 1 and then this will be 2*i + 2. Awesome. Okay, so that will set up all of the links properly, all the references, and we just return. And then we should probably do some checks here.

Intergalactic Avenger: Yeah, you don't have to worry about the checks. That's good. Excellent, looks correct. Um quick question about its runtime efficiency. So how much time and space does it take up.

Double Pizza: Alright, let's talk about time first. So we create a new arraylist, that's constant time. Alright, so we collect all elements. Let's talk about collect all elements. Essentially, we go through every node in the list, or in the heap, so collect all elements is O(n), is linear. We do it twice, so O(2n). We sort reverse, so sorting in Java by default uses mergesort and O(n log n). Reversing is linear time, so far O(n log n + 3n), there's another linear operation because we have to go through every node in a collection and then we go through linear again and then which for when we iterated through the tree. And then we return the root, which is constant time. So this is for time, it's O(n log n + 5n) and so I would just say O(n log n) since that's the biggest element.

Intergalactic Avenger: Yep, okay, excellent. And yeah, now it's space.

Double Pizza: Let's talk space. So, we allocate a list here of all elements, so that's n, because it grows linearly with the input. We sort the list, we create another n list over here for our nodes, so we're at O(2n), and then... well actually, I do allocate another list in collect all elements but that's still valid.

Intergalactic Avenger: So O(n) space. Ok, very good. And in many applications, an O(n log n) run time with an extra O(n) worth of space is just fine, but let's say that we had some tighter resource constraints and we wanted to do this a little bit more efficiently. So can you think of a way to reduce either the time complexity or the space complexity without increasing the other one?

Double Pizza: Alright, reduce time or space without... alright let's think about this. So this collect all elements thing... So the first thing I think about is like I can use a priority queue, but I know priority queues are implement as queues, which rely...

Intergalactic Avenger: Yeah, that'd be a little bit of cheating yes.

Double Pizza: Right, kind that's kind of cheating, alright.

Intergalactic Avenger: Because, we're basically implementing it.

Double Pizza: Eight we're implementing a priority queue, yeah ok. Alright. So my first idea, first inclination, which I'm not quite sure how to pull this off yet, is building up the heap instead of kinda what I'm doing, collecting everything actually into a data structure and then building links after the fact, I wonder if how bad it would be to just build a heap, you know, insert one node, okay and now insert the next node and resetting you know any pointers that needed to be reset. I mean, I'm guessing this has to be balanced right? Because the cheating way would be like have 10 and then its left child is nine and then it's left child is 8 and it's left child.. you know, essentially I just made a links list, instead of anything that's actually particularly interesting right?

Intergalactic Avenger: Yeah, I mean it... there definitely are... depending on the input heap that you get, there's going to be sort of best case and worst case issues and sort of one nice thing about your implementation is that the best case is the worst case, so it doesn't matter if it's balanced, and in fact you return a balanced tree on the way out just for free, so that that part is nice. Um, but there's... if you think of sort of a best-case or median case where the tree is somewhat balanced then there are some more efficient ways to do it. And you're definitely on the right track in one sense with the building up the tree as you go, that's an interesting idea to think about.

Double Pizza: Okay, I think I've got an idea. Sorry, I didn't mean to cut you off there. Alright, I'm gonna kind of write some pseudocode, or at least like my thoughts. Okay so, we know that the biggest... this is kind of like merging two sorted arrays in a way, trying to think through this. So we know that the root of the new heap is going to either be the value at the root of the first or second right, so okay... I'm going to kind of write a new function here just so I don't start messing with... So, I'm just going to start writing code and I think about this as I go through it. I can switch over C I suppose, I'll have stars all over the place and I won't know what's going on. Alright, the curse of Android. Okay, so... I'm just going to pretend I have a default value constructor here. Okay so... so this is going to get the root, correct? We know the root has to be one of those.

Intergalactic Avenger: So actually, just to get you going here, you're definitely on the right track, but listen to the exactly the way you phrased that last statement, which is correct but there's even a stronger thing you can say about it. So you said the value of the root node must be either the value of the root of the first or the value of the root of the second. To make an even stronger statement, maybe that doesn't... so for example can you think of a way that maybe you don't create a new node.

Double Pizza: So now I started to see about you know best case, worst case, maybe this will happen, maybe this won't. I had it, now I'm trying to think of how I want to do it. So if I just start inserting elements from say the first key into the second, you know, I'll end up with something that satisfies you know the property of the heap. But then I have to figure out what to do with everything. Alright.

Intergalactic Avenger: So here's a hint. So, let's say we have our two heaps, you know we have a heap on the left that starts with like a 2 and a heap on the right that is rooted at a five. What about just taking that five node and making it the root. Just make it the root with all of its children, everything. That is now the root of the new tree. And what then becomes, like what do you have to do next. So if you just said, well the right one is the new tree, well obviously that's not the answer, that's not quite right. But the answer is sort of just a small tweak on what you, what you're already sort of looking at. So we have these two trees, we have the tree that's rooted in the five, and that's going to the root of the new heap, and then you have this other thing sort of sitting on the side, this barnacle. How can you now merge these two trees with this extra little bit of information that you know?

Double Pizza: Okay, so I'm trying to digest everything in a second. Okay, so if I ever created starts five in the tree starts at two, and I take that two node and I chuck it in...

Intergalactic Avenger: Well you don't really do anything with the two node just yet, but we're just going to say that five node and all of its children are going to be the the new heap, the combined heap.

Double Pizza: Okay, okay.

Intergalactic Avenger: And now you need to sort of do something, because you've got this extra little thing, this two rooted tree, hanging off on the side, and you need to somehow incorporate it into your new tree.

Double Pizza: Right, okay. So if I say I had 5 3 1. Oh, I'm on line 130/131. So, I had it. I really thought I had it. So for a case like this, I can just put the nine as a new root, attached the entire tree as one of the children. So now is the node is smaller, I'm trying to think about what I want to do. Oh, okay. I can make five... I was going to say I can make five the new key or the new root, which it would have to be. But the problem is I have two children over here that I need to do something with. I'm not quite sure where to put them.

Intergalactic Avenger: So, if... so you have the 5 3 1 and you have the 2. Where could you attach the two in the tree with the five three and one.

Double Pizza: So I could attach the two at the end of the three, from the node that leads to the three.

Intergalactic Avenger: Yeah, and where else might it go?

Double Pizza: I could put it in place of the one and then move the one below the 2. I feel like there's something obvious that you're leading me towards and I am not seeing it.

Intergalactic Avenger: So if you think about it, let's say that we have this...just get rid of your five there for a second and we have like the two trees here are the five and then we'll have like a 1 and a 0. So when we we merge them, we are going to take the 5 and where you put at the top because we know that's correct, that's guaranteed, that's definitely going to be the answer. And now, what do we have as children of the 5? We have two max heaps, right? We know that those are max heaps. We just need to make sure that whatever we attach to those sides are both max heaps. So if you take a look at the trees that are left, we have a three, we have a one, and we have the 2 1 0. So, and we know that all of these are max heaps. So how about, we attach the larger one to the five and then we figure out what to do with the next two heaps. And now we sort of have the same problem that we had before, that we have to max heaps that we want to combine into one and attach that as the other child of the five.

Double Pizza: Right, okay okay, I see we're going with this.

Intergalactic Avenger: So the problem is sort of repeating itself.

Double Pizza: Right, yeah so you can do this recursively. Alright, so if... so I don't need my pointers anymore, because we're just gonna do... This is the first time I wish I had a whiteboard to doodle on.

Intergalactic Avenger: I know right, especially with graph problems, like being able to draw the lines is always really nice.

Double Pizza: So going back to your example, so if we're merging you know these two to 5 3 1 and then 2 1 0, we want to take the five and... so we make that... and then we have the one I made 2 1 0.

Intergalactic Avenger: Okay, so here is the first question. So we know the five, it belongs to the root and we know that we have three max heaps left, we have the three, the one, and 2 1 0. Which one of those are valid to just add directly as the bottom, as one of the children of the five?

Double Pizza: So the 2 1 0 we know is the max heap because we just got it in.

Intergalactic Avenger: Yup. So you could add the two, the 2 1 0 subtree to the five, so that's fine. And the three and the one sub trees were already attached to the five, so they're valid. So basically any of them.

Double Pizza: Okay, yeah okay. And we just do it all over again because we have two slots, or we have three things with two slots and then we can just recursively do it again. Alright. Let's get this written. So if the first root is greater than the second root, we can just... I'm like waving my hands in the air right now. Alright, so the old sub tree is equal to... let's pick, one we're going to take the first...

Intergalactic Avenger: Hmm, there's a couple issues with that last line, 115. The first thing is... if you're returning it, then you're actually... Oh I see... oh I see what you did, okay yeah yeah yeah yeah. Alright, yeah ok. No that will work.

Double Pizza: And of course we can do the same for the second case. Alright... right because we know the whole subtree is definitely a heap, that's how heaps work. Yeah, alright.

Intergalactic Avenger: Okay, so now... what is our time and space complexity of this new one?

Double Pizza: Alright, so this is... we're not actually allocating any new memory, we're doing everything in place, we're just really... we're just changing out pointers so that is...

Intergalactic Avenger: Oh actually, wait wait wait, sorry sorry sorry. There was a second problem with line 115. If you're returning it... oh no, you're right sorry. Yeah okay, we're good.

Double Pizza: Okay... no you're right, as I'm going to be returning some child node, am I?

Intergalactic Avenger: So I mean, the other thing is that with with recursion, you always want to have some kind of base case, so that it doesn't keep going on into infinity. So, let's just hide that up and then that will clean up all the loose edges there.

Double Pizza: Oh, I can control that side of them. Alright so, that's right if second is null, that's where I'm putting my subtree. Then we just want to return... yeah no you are right, because I'm returning something very strange here.

Intergalactic Avenger: No this actually will work, if you set up the base case correctly.

Double Pizza: Okay so here... so the next time I call it, this will be here. I wish you could see my hands right now. I was going to say I'll assume the first call always have a non-null thing.

Intergalactic Avenger: For our purposes, that's really fine, and yeah and the fact that you're calling combined heap, but even passed to the recursive call, where you know that the first one is valid, then then this is fine. Okay, so yeah, so now that will work. And yeah, what's the time and space complexity?

Double Pizza: Okay, so this is constant time, I mean except for the whole actual callback, but... sorry this is constant space. We're just changing our pointers, not actually allocating new memory. Alright so for time, we have to do a recursive call, each call this whole thing. So lines 110 to 112, constant time. Line 115 is constant, 116 is constant. 117 is constant time. Then we have to do our combo. So everything except our recursive is basically constant times, because we're just shifting things around. But we have to go through every single subtree which is essentially every single node right? So going back to this example, this would be... Yeah so it's going to be linear time, I believe. I'm not even convinced of that because my thought was you have to go through essentially every node, but you don't. Because this is it's actually O(log n). Yeah.

Intergalactic Avenger: Because look what you did with this first dot left equals second. You don't even look at all at the second tree right? And then everything below it just comes from the tree.

Double Pizza: Yeah. Wow that's very nice.

Intergalactic Avenger: Yeah and just to tighten up all loose ends, why is it O(log n)?

Double Pizza: So it's O(log n) because we're going down... we're only looking at half the tree every time we go down a level. And since every... there's only two possible tree lines... looking at half of... I don't know how to phrase this.

Intergalactic Avenger: Yeah the classic way to phrase it would be that you are execute... you're doing a recursive call for every layer in the tree, so the the number of times you call it...

Double Pizza: Is proportional to the height of the tree, which is log n because it's a binary tree.

Intergalactic Avenger: Yeah and yet, if this... so that's in sort of the best-case, balanced case... and let's say that you get some kind of really weird and unbalanced tree, what would the time complexity be there?

Double Pizza: So in the worst case where we have that kind of like, cheating thing where you have to look at everything, it would devolve down into linear.

Intergalactic Avenger: Okay, yeah perfect. Alright. That's exactly the the solution I was looking for. So fantastic. Yeah so no, this is good. That generally shows like an excellent kind of a pattern for these kinds of questions where you had this sort of more brute-force approach at the beginning that was correct but just could use a little bit of extra optimization and then the second one with a little bit of extra thinking and playing around with it, then you got to the optimal solution which is a lot more efficient, so very well done, great. Good job. Alright, so did you have any more questions or do you want to call it a day?

Double Pizza: That was, yeah... so I've... this is the first time I've done this interviewing.io as being interviewed. I've done it many times on the other side of the table.

Intergalactic Avenger: Oh interesting, okay. Yeah no, I every once in a while switch over sides to and I'll definitely admit it's much easier to do the interviewing than to be interviewed because I have to come into it and I have this like very specific idea of what I'm going to ask and where on the other side it's like it could be anything. Alright, well... excellent, well great job and good luck with with your future interviewing.

Double Pizza: Thank you, thank you very much. Have a good one.

Intergalactic Avenger: Bye.