Python Interview with a Google engineer

Watch someone solve the binary tree upside down 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

Binary tree upside down

Interview question

1) Given a binary tree where every node has either 0 or 2 children and every right node is a leaf node, flip it upside down turning it into a binary tree where all left nodes are leafs. 2) Find all palindromic decompositions of a given string s. A palindromic decomposition of string is a decomposition of the string into substrings, such that all those substrings are valid palindromes.

Interview Feedback

Feedback about Occam's Malamute (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

Discussed in the call, overall really great technically sound. Map out approach is the only improvement and is minor.

Feedback about Ferocious Chameleon (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

4/4

How good were the questions?

4/4

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

4/4

Good combination of pushing an interviewee in a direction you want them to go and letting them work on a problem! You also did a great job quickly coming out with very applicable questions

Interview Transcript

Occam's Malamute: Hello.

Ferocious Chameleon: Hello. How's it going?

Occam's Malamute: It's going well, thank you. How are you doing?

Ferocious Chameleon: Pretty well. Can you give me a little, a little background about yourself?

Occam's Malamute: Yes, sure. I am coming from a more academical background. And what I do now is called machine learning. And I work in one of the big tech company, and I'm interviewing with another big tech company. And I somehow landed to the final round, that will happen, like in four weeks. And I'm just have to prepare for my final round. And I originally have no computer science background. So everything I learned, I learned on my own, pretty much. And that's pretty much it. So I'm trying to focus on solving problems that are kinda on the medium level, but I'm trying to solve them efficiently, fast and without too much typos. Because I think that is, so I don't, I'm trying not to solve, you know, some very exotic problems that take an hour, I would rather work on something more straightforward, that, but I would rather try to do it, ideally.

Ferocious Chameleon: Okay, so, I'll go ahead and paste the problem I have for you. So what I'm gonna do is I'm gonna paste the description first. And then I'm gonna go ahead and give you an example in the draw section. So I'm going to paste this right here. Okay. So this is the description. The problem itself is called upside down. And I'll draw it out out, I'm going to draw an example here.

Occam's Malamute: So are you going to draw it or I need to start working?

Ferocious Chameleon: Yeah, so if you look at the draw section.

Occam's Malamute: Okay, I'm sorry. Gotcha. Gotcha. Gotcha. And, uh huh. Yeah, thank you.

Ferocious Chameleon: Yeah. Give me one second to finish this up. See? Okay. Okay, so I'm gonna draw the binary tree right here okay. And we can imagine that this is one, this is two, this is three, this is four, and then this is five. And this is what you get, you have to get the root you be input the root, and then here you draw the output. Okay. And then the output would be something like this. Fill in the numbers and it all makes sense. So this is going to be four, this is going to be five, this will be two. And this is going to be three. It's going to be one.

Occam's Malamute: Okay. Understood. So I just want to clarify a couple of things. So you have put four in the root of a new tree. So, yes, can we say that it's the rule that the left child has to become the new root?

Ferocious Chameleon: Yeah. So, you can you can say that that's a fair assumption.

Occam's Malamute: Okay. So, understood. So, the left child becomes the root the original root, which is one, becomes the right child.

Ferocious Chameleon: So, so, yeah, okay. Yeah, you can assume that as well.

Occam's Malamute: Okay, and finally, the right child, the original right child three becomes the new left child three. So, those are three conditions, I want to keep in mind when I work through a problem. And yeah, so, and obviously, none of us do or whatever, we see the left child has to somehow become the root of the new tree. So, I imagine that we can somehow utilize that structure. So, what I will do is the following, so, I will create a spec, which is essentially a list and I will put a root into the spec and I will keep appending left children of the root. So, in our case, now, let's go back to code and so, it will be easier for me to start right start giving you an idea in the comment section. So, given that we have a tree that is what 12345 Yes, so, we have a tree 12345. So, I pretty much traverse that in a BFS manner. So, it means that my stack will get one and it will get two and four. So, after that, I know that four has to become my new root. So, to do this, I will also initialize an array called res for result, and I will put four in the results. Which is just the last element in the stack. And after that, after that, so we have 124 let's take a look at this chart. After that, I will start popping elements from my spec. I will start popping elements from my spec saving them into some temporary variable called T, stands for temp. So I will do something like this. And by doing this, I will remove four from my stack, which is the root. And I have five and two, they have to become children of my four. So now here I have four and all that two to become my right child, based on the chart, so, what I will write... I will write some things that obviously t right should become this and by doing this we arrive child of four will become two. Okay, which is right. And one has to become the right child of two. So it means that. Okay. So I put my t right is, what if I put my t left as that minus one? Right. So what I did here? I know that my stack minus one was stack is four but it's probably one of this now, it's at this point it's two. So, to the right element have to based on the chart is one. Yes. And this one problem and this... Yes, I guess so. And after that, yes, and it's all will be done in a loop. And the loop will go to my stack has more than one element. I need to have more than one element because I can just take a step back. Otherwise I will give them index error. Yes. And so if we approach and to build this thing, I want you to traverse the whole tree once, which gives us a big O of n time complexity. And I have to build a stack. Which, again, essentially will bring us to asymptotically will bring us to a big o space complexity. So I think it's fair to say that it's O(n) for time and space.

Ferocious Chameleon: Okay. Okay, I agree with you. So, as far as... So, so as you proceed, how will you set two as right and? Or sorry, how will you set two as left?

Occam's Malamute: Understood, so I guess I do it here. And let's think what it does. So my T is four and I'm saying that my left child of for should become five? Yep. Oh, well, I will do it in the following way. So that will be in the loop. All the stuff we're doing will be in a loop and then I will say... Something along those lines.

Ferocious Chameleon: Okay, so when do you push onto the stack?

Occam's Malamute: When do I push onto the stack? At the beginning? I will, right? So, we'll work in the beginning, I will put both into the stack. And I will put all left children as well.

Ferocious Chameleon: Okay, so you'll put all the left children. So you'll say, you'll put one, two and four. And then which is right, okay. And then you're going to pop from the stack. And there you go set the right child to the two, which is the last element in the stack after you've popped in either set the left child for two to two's right child, which is five. Yeah, and so when you loop again, you're going to pop two and then you go set two as the right child to the last child, which is just to re so that's a while. Okay, that's right. You guys set two's left child, two ones, right child and one's right child is three. Okay. That seems right. And then yeah, I mean, it looks good. So, do you want to do this as long as the length of stack is greater than one or or greater than zero?

Occam's Malamute: I guess one. Because I do it two steps back. So, it should be more than one. Because I start with my original root. If I remove my original root, I will not be able to take care of the right portion of the original tree.

Ferocious Chameleon: Okay. All right. So do you want to go ahead and, and code it out? Seems like pretty much almost done.

Occam's Malamute: Okay. Yes, let's let's try. So, I will call it upside down.

Ferocious Chameleon: I've also tasted in a tree node class.

Occam's Malamute: Thank you. So, I guess it takes root as an input and also return a tree node, a pointer to the root. So, I will start with some edge cases like this, and I will initialize my stack and I will initialize my res and my stack will get my original root and my res will be originally empty. And then, I will start my... I will start adding elements to my stack by saying while stack... Well, while stack's element has a left child, please put this thing on my stack. Yes, then I will know that the very last child the last element on the stack has to become a new root. So I will say res equals to stack's left element and then I start another loop, let's say while length stack is more than one, two equals take an element from my stack. And the right will become my stack minus first element. And my left will become my last element right? After that outside the loop, I will do this thing. Yes. And at the end of the day what I want to return I want to return probably a base, or you know what we are what that will return, at least with the return at least with the node and I want to return the node itself. Let's do the following thing. In this case, I will return the node because I want to return a node at the end of the day, not the list with nodes. So, that is the approach. We I think with this sort of a dry run. And if it's if, if you think it's suitable, I would rather try and run it with this provider the tree, do I need to build a tree for this?

Ferocious Chameleon: Also, for this, this specific way, we are initializing t here, right? You're saying T dot right is equal to less when you return res is it shouldn't just return four since you set res equal to stack at negative one and then you never set res's right or it's left?

Occam's Malamute: Yes. That is also correct. I did not. And I did not, should we or no that's the question. Because I return the node, a reference to the node. I return a reference to the node. Let's see. Let's take a look at the original chart. So I'm just switched to the draw portion. So I originally reference to four, which is output. And that's all. Well, I guess we can... Okay, so you're saying that you are suggesting to add children?

Ferocious Chameleon: Yeah, unless you don't think that's necessary? Well, I think it might not be necessary since your since you're referencing the same node that you put in the set.

Occam's Malamute: Yes, I hope so. Yes. And, you know, like if we decided to actually test it, we probably want to, like return this just for the sake of the test. But the idea is to return an actual node. Yeah, so that's the idea. Okay, sure. Do you think I should try and test it.

Ferocious Chameleon: Yeah yeah we'll just go ahead and test it I guess we can we can write like a print like in the order we got right like an order print just to see if it's coming out in the correct in the correct order.

Occam's Malamute: So I'm building a tree okay. There is an old tree that looks like this with that left pointer dot left pointer four and left pointer right is the tree node five. So this is the original tree. And you want the way they want some might want some helper function to print it level by level.

Ferocious Chameleon: Yeah we could do this in order, in order should be fine.

Occam's Malamute: In order certainly should be fine. So I need to write some sort of the get in order function so it will take res and I will say if not None return in order means left then right. So I will go in order and know what to do.

Ferocious Chameleon: You can just print it also, you don't necessarily need to return the... I mean it's up to you but I mean that should be fine too.

Occam's Malamute: So this is in order, right, and then I want to return res I guess... So. Okay, so after that what we want to do we want to take my Upside down... Upside down... We want to play with it my original root and now we want to take this whole thing and pass it as a node to my function. Yep, yep. So I will do it here. Here. And that it will be in order and I need to print it so hopefully that okay... Doesn't have an attribute, which attribute upside down. It doesn't have the attribute upside down because I need to put everything like this I guess.

Ferocious Chameleon: And then you need to like add the self in all of that.

Occam's Malamute: I need to add self. Right and all that. Yeah, exactly. Okay, try again. Because in order doesn't need to be inside the...

Ferocious Chameleon: You need to do l dot in order.

Occam's Malamute: Because it's all sits under the class tree node. Yes, it's because I need to remain with yes to those things. Okay. Where? Where were left and right. Right. Right. 40 to one. They're wrong.

Ferocious Chameleon: No, that's right.

Occam's Malamute: Ah, yes.In order. Yes. Yes, exactly. That's right by 54321.

Ferocious Chameleon: Yes, it's right. It's good. 532 a perfect. Nice, nice. And you already went through the time and space complexity?

Occam's Malamute: Yes, that's correct. And I will just copy paste it here.

Ferocious Chameleon: Okay, looks good. Looks good. Nice job. Do so we have another 30 minutes left. Do you want to? You want to continue with another problem?

Occam's Malamute: Yes, if possible.

Ferocious Chameleon: Okay. Is there any problems that you're there any? I guess, feel that you want to focus in on or your you just want to pick up anything?

Occam's Malamute: Yeah, I would say that I would love to do something string related. You know, pointers, anagrams, palindromes with level stuff.

Ferocious Chameleon: Okay. Give me one second to pull up. Okay. So, I'm gonna just paste this here with the example. So this problem is called palindromic decomposition of a string. I'm going to do a way to clear this out. I'll just clear this out. So, this is the problem okay.

Occam's Malamute: So okay. So, we have a string and we need to return all possible palindromes. Yes. All possible palindromes.

Ferocious Chameleon: And I put my patience constraints at the bottom.

Occam's Malamute: So it means that we need a list of strings where the result will be a list of strings. Okay, understood. So I understand the question. I think the way I should go about is the following. The way it should go about it is the following. So first of all, we need to find them and then we need to actually create them and add to our results? Okay. So the way I'm thinking about it is the following. So we have a string. I always look for some optimized solution from the very beginning, because what we want to avoid is just doing some brute force approach with two pointers, where we check every possible combination. Well, it's because like we assuming that, for example, like, I'll just walk through walk you through the port for suppose just for the sake of doing it, we can assume that every element on its own is a palindrome. Yeah, and, yeah, so we can start two pointers, left and right, pointing to the zero element. And then we can move to our right, and we will check a B, whether it's a palindrome, my right, check whether here we have a palindrome, move right, check whether we have a palindrome. So it's very inefficient approach. What we can do in order to speed in this approach up a little bit is to sacrifice some space. Usually, this is how, and I will use a dynamic programming approach, I will build a 2D list of lists where the number of columns is equal to my total number of characters. And the number of rows is also equal to the number of characters. So it's essentially a square matrix. And I will fill this matrix originally with false. I will put true on the main diagonal, because we know that every letter is a palindrome on its own. After that, after that, I will start working, I will start filling out my... I will start filling out my matrix. From the second to last element, I will initialize a pointer that points to r, essentially will point to the cell that has coordinates it's r and I will emphasize my right pointer that will point to a and I will move my left pointer to the left. And my right pointer will be moving from my left pointer to the right every time. So what does it mean? So for example, let's imagine I'm at my left pointer points to the letter D, which I selected. So it means that my right pointer points to A and it will work through all elements on the right side from my D. And then I will move my left pointer to here and I will do the same. But the good thing is because I'm saving my original source problems. It means that if I see a palindrome like ADA and if I add I it's in just enough for me to check whether C equals to B and I see that he is not equal to be so it means ADA is a palindrome, CADA is not a palindrome. So, and that will avoid rechecking because I'm saving my preliminary not throwing away my temporary resources. And basically every time when I make my every time when I make my cell, when I turn my cell from false to true it means that I need to save the result index start n plus one to some storage and because if I turned my cell into true it means that and this cell is defined by two parameters by left pointer and by the right pointer, it means that this room I want to say that to somewhere else, which is a waste or maybe a set Yeah. So, this approach and this approach as I mentioned will require extra space the space complexity will be big O(n^2), where n is the length of the string and time complexity wise I guess there will be also be O(n^2).

Ferocious Chameleon: So, okay. So, quick question, when it comes to this example. So, if you had something like ABA, technically another output you could possibly have would be something like this something like that. You also have something like this. So yeah, it will be like this. So, how would you cover these cases where there are multiple palindromes in the string.

Occam's Malamute: Aha, so that I can use the same character in different regions of palindromes.

Ferocious Chameleon: Well, not well, yeah. So you can have so since we were placed this this are what a this ABA is a palindrome and ADA is still a palindrome. So you can have multiple palindromes in one combination basically, of your decompositions.

Occam's Malamute: Oh, yes, this is true. And this is something I probably am not covering in my solution or maybe empowering to myself like your. Take a look at this. So Ada will be taking a guess so ADA, so substring ABA is defined by two parameters starting and ending pointers. Start and end left and right. And but the character a on its own also has its own cell. In my matrix, it's on the main diagonal. Yeah, so it means that it will go into my result because the diagonal will be able to true. So, that being said, I will have both ABA in my results in waste, and just a. So because like in this example, the issue is that I should count ADA is a palindrome. And I should call our AA as a palindrome. And this is in the middle, it kinda, it's owned by both palindromes. And we want to make sure that we are not overlooking this scenario. And we're not overlooking this scenario, because the palindrome ADA has different coordinates compared to the palindrome AA, because they, they have different coordinates, they have different cells in my matrix. And that's why I will say that okay.

Ferocious Chameleon: So would you also be covering or what is your output solution will also output this as well. So it would be something like, so it would just be the ABA without the ADA. So these would all be valid decompositions.

Occam's Malamute: Yes, single letters will be valid decompositions, because they are the main diagonal.

Ferocious Chameleon: Yeah, yeah. Okay. All right. So you want to go ahead and code it out?

Occam's Malamute: Okay. Yes, I'll try to do it. So okay, so it's called all vowels, and it takes a string s. So I will quickly do some checks, such as zero, return this is too long for the live, and then I will initialize the y's dp, which is a, which will be a matrix which will originally be filled with false times length s for in the range. This is how I define my dp matrix. Okay, and also I want to save my results somewhere. And let's say we'll save them in res and let's have it be a list, it's probably can also be a set. In case we have like exactly the same palindromes. We don't want to repeat them more than one. But put a comma and this might be I will walk through it a little bit later. So what I want to do, I want to fill out the first diagonal with true, because it's single letters. So I'll go for i in range s. I will say, dp i i, which is the main diagonal equals to true. And as long as my cell becomes true, I need to save this these results into my res. And I can do it on the fly right now. Or I can do the whole matrix and then goes to the symmetrics again. But I guess it's more efficient to do it on the on the go. So to do it on the go, I will need to do append. And what I want to append. I want to append the string with the coordinates. So for example, you have let's say this a with a has coordinates we'll have 2 2? Yes, because it's the second, it has been mixed. Oh, yeah. So basically what is odd if it was used s of two, three, which is essentially just a, yes, because it's just c[2]. Okay, so this is how I, that's how I get my results together. So, after that, I want to do my main portion, starting with the left pointer pointing to the second to last element. And to do this, I will say for start in the range len s minus two, and all the way to the left and my right pointer will go from start to the right. So that's where I'll start my second for m in range plus one, I don't want them to overlap all the way down to them. So, here I will make two checks, I will make checks whether elements at Start and End are the same and if they are the same, whether everything in between them is already a palindrome. To do this, I will say Okay, so, there are two scenarios, if my start and end point to elements that are next to each other and they are the same, this is a palindrome or if my start and end point to elements that are not together, but I will check whether everything in between them is a palindrome. So, I will say if this equals true this from here I have another if. If they are together next to each other or everything in between them is already a palindrome everything in between them is this and I will write it like this, because it means that evaluates to true is everything in between m and start in this is already a palindrome. So if it's a palindrome, so, if this is good, I need to do two things I want to mark this larger string substring as my new palindrome and I also want to save my results here. And you know what, what will happen here? I think I will double count my double count results from the main, the you know, so we might want to come on this one out, but we think about it in a second. So, yeah, so that is pretty much it and return res, this is the one to get back. And I will write that it's the O(n^2) for both. And I I imagine that yes, we will double count results as the main diagonal. So I will put it as such because it will be enough to cover them using this line by 60. So this is approach and we can test it I guess.

Ferocious Chameleon: Okay, yeah. Do you want to go ahead and write a test?

Occam's Malamute: Yes, I can write the test. So first of all, I will use the original one that we already have. Abracadabra? Yes. Interesting. Okay, let's see. Okay, let's see what going on here. It's only returns two A's. It's definitely not enough for us. Okay, so obviously, obviously this plan is not right, because I just can't be faced with this. It shouldn't be this. Well, it's getting better. So why is it happening like this? Let's see if EA is definitely... Ah, okay. Understood. So we somehow didn't cover the main diagonal. Yeah. Let's, let's cover it. Yes. So now it's better now would have every single letter as a palindrome? This is what they want. And originally, we had to do... And ACA which is this one. Yes. So it looks reasonably correct. I think you also gave me earlier, more.

Ferocious Chameleon: Yeah, I gave you a sample. Yeah. Just replaced the R with a.

Occam's Malamute: Yeah. Let's see whether... Yes, you see it. Yeah. And it takes care of ABA as well. This is what we're afraid that this letter that is served by two palindromes will create problems. But yeah.

Ferocious Chameleon: So if you were to rebuild this string with the pipelines, separating them separating the sub strings, how could you use this function to do that? So you want me you don't have to implement that you can just tell me whether I can.

Occam's Malamute: So well, so this is let's say it's just the normal Abracadabra, right. So abracadabra here determines everything one by one. Here it returns it just like combinations. Exactly. They're just combinations of the main diagonal with everything else. Yep. Well, I think for the main diagonal with everything else, well, what I would love to do then I would, it's probably some brute force approach. I will have truly for this, I will have waste for one letter one character drops, where I will save everything. One letter palindromes, yeah. So I will I will populate here and then I will have with four other palindromes that they will populate here after that, I will do two loops and I will insert every element from here. I will just yeah, I mean, I'll just do something like then I will finally initialize my res and I will go for long while in this and then... So, this this this will add elements from my... it will add everything here then I will do okay if I do this it will stop it will not... No, I want to do I don't want to do it twice so, I will populate... Okay I will populate it like this and then I will okay... so, I will populate my res with my long palindromes ada I will populate my this is not the res of this sort of the current... Yeah, so, I have my current and then I will have my ultimate res. So, I will do the following. So, I will populate my current with my will take my walk and then I will do current append and this current should go to my res and then I need to make it empty again. First of all, otherwise, that would give us an error. So, what it does, okay, so what it does is it says go through my Ada ACA did my ADA, add it to cart. And then it says to Ada add this, with rails, there'll be a list of lists, you technically you want you want strings, but then we can do one extra operation to be in charge with the strings. So after that with res, we'll get this thing and then I will go to my so I just did ADA and that's so that I will get to my issue. So, after that my current account will become empty here I will have ACA here I will have pretty much the same thing but with ACA and then this whole thing will be appended to my result and then there was the fleas. And finally if we want to get this like exactly like this, what we want to do so... Okay, so we want to go through my list of lists. And we want to take elements, we want to merge them together and join them together in a string. So I will have my final res and I will go through my four elements in res. This is how I approach this thing. Equals, here's what I will do, I will join these elements into a string called temp, that will be a separator between every element in this joint string. And then this string will go into my final res. This will build my output.

Ferocious Chameleon: Okay. Make sense. All right. I mean, we're, we've reached the end. This is pretty great. For feedback. Would you like to do feedback now? Or would you rather the form up to you?

Occam's Malamute: If you have time, if you have, like, willingness to do it now or if you're more comfortable writing it?

Ferocious Chameleon: I have time to do it now.

Occam's Malamute: I'll take notes.

Ferocious Chameleon: Okay. So for feedback, I think, you know, obviously, you're able to find the most optimal solutions for both questions. And I would say that these issues questions, the first of all, I'd say would be like, a medium question. And you're able to do it within 30 minutes, which is the which I believe is the is the right amount for a question like that. And then I would say this question would probably be a medium, a higher medium question as well. And you're able to approach it with a dp approach, which is, you know, obviously, the optimal solution, and you're able to do that in 30 minutes as well, which is, you know, pretty great. So let's say, technically, you're good, you're pretty, you're pretty good. And communication wise, I was able to follow your thought process at each step. You were communicating very well. So that's obviously, very important. And that was pretty great as well. One thing I would say, to, that I always think helps bring you to the next step is being able to map out your approach, as an interviewer kind of shows your organization skills. So you're able to do that with, you know, writing out your pseudocode. And you're able to run through examples. But I would say if you were able to, like, and this is like a minor, subtle improvement, if you're able to, like, map out your approach, like once you come to your solution, you could, you could write it out in those who say, this is my approach, I'm going to do this, I'm going to have these cover these edge cases, I'm gonna have a while loop. And you did do that. For the first problem of say that, I guess mapping that out with so a little bit more organization and as interviewer, when you're, when you're going through your implementation, the interviewer can always look back to you know, what you've mapped out in your approach to see exactly where you're at. So they can, so they can follow through, you know, accordingly. So I will say that, that is the... The only thing I can really say. But everything else is like, really great. Quiet, like really good. So, yeah, so, yes, yes.

Occam's Malamute: Thank you for this. I really appreciate that. It's really helpful. I will say, the first question to my list of questions. The second one, as I said, I'm trying to solve a lot of string questions. So I was kind of familiar with approach already. Give that I can kind of read the read through a moment to my memory build something from scratch. Yes. Yes. Thank you. It's a good combination of questions. Exactly what I was hoping to work on.