We helped write the sequel to "Cracking the Coding Interview". Read 9 chapters for free

Python Interview with a Google engineer

Watch someone solve the delete nodes and return forest 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

Delete Nodes and Return Forest

Interview question

You are given the root of a binary tree and an array of integers called to_delete. Each node in the binary tree has: * a value val * a left child left * a right child right Task: Delete all nodes whose values are present in the to_delete array. After deleting these nodes, some children of deleted nodes may become new roots of separate subtrees. Return a list of the roots of all remaining trees (the resulting forest). The order of roots in the output list does not matter.

Interview Feedback

Feedback about Redolent Unicorn (the interviewee)

Advance this person to the next round?

Yes

How were their technical skills?

4/4

How was their problem solving ability?

3/4

What about their communication ability?

4/4

What went well: - You've started well by asking detailed questions to make sure you've understood the question. Next, you've applied this understanding on simpler cases and iterated from there. All this together helped you to scope the question well and arrive at & explain an optimal solution in ˜15min, which is a good velocity. - You were proactively guiding the session and introduced structure to it (asking questions, clearly and smoothly moving to the next sections). Both of these meet Google L4 expectations (and even lower band of L5). - You've correctly estimated and argumented time and space complexities for your suggested approach. Moreover, you've improved your time complexity by O(n) multiple by transforming to_delete as a set. - You've written highly readable, well structured code. What could be improved: - (important) It would be good to generate and discuss edge cases and make sure your solution handles them before coding as it would guarantee your solution is complete and also saves you time down the road while debugging this. Edge cases not handled were: - empty tree - deleting a node and its immediate child(ren) - (small & negligible) Make sure you brush up the basics of the language you're going to use in your tech interview. In this interview these were: Python deque creation bug or which collection is deque in.

Feedback about Samurai Gyroscope (the interviewer)

Would you want to work with this person?

How good were the questions?

4/4

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

4/4

Very nice question

Interview Transcript

Samurai Gyroscope: So the question looks like this. Imagine you are given a binary tree. Okay.

Redolent Unicorn: Yeah.

Samurai Gyroscope: And then it has some nodes. Does it look good to you?

Redolent Unicorn: Yep, looks great.

Samurai Gyroscope: Okay, and imagine, I mean by regular node representations, you have like node right, node left and node value right. And this whole tree can be represented as node1. And all of the nodes are connected under the hood. You will be given the root of this binary tree. And then you will be given something called to delete, which is going to be an array of integers. So not nodes, just integers. So you have for example, 3 and 5, just like random values for now, what I'm expecting from you. So this will be your input argument. And then as an output, I'm expecting from you to go through your tree and then delete the nodes if their values are contained in that, to delete. So in this case, imagine we are deleting this 3 and 5. And if you delete, you will see that 1, 2 and 4 now separated from the rest, and then they are still connected to each other and their root is 1 and 6 and 7 are orphaned and became separate trees. What you need to return is root of leftover subtrees. So what we have here is node 1 because it's still root node 6 because it's now a separate subtree. And similarly node 7. So the order here is not important as long as you return all of the roots and. Yes, and that's it for now.

Redolent Unicorn: Okay. Does it binary search tree or just a binary tree?

Samurai Gyroscope: Yeah, good question. So it's just a binary tree.

Redolent Unicorn: Just a binary tree. And does the numbers to delete, like the values necessarily exist in the tree or they can not be in the tree also.

Samurai Gyroscope: Yeah, they might not exist in the tree.

Redolent Unicorn: They might not exist in the tree. Okay, so let me just rephrase the question to see that I'm fully understand it. I'm giving some node of a binary tree and then does the node like the node exists? So it can be have no children, but the node exists, right? The input.

Samurai Gyroscope: So do you mean those values which exist into delete?

Redolent Unicorn: I mean like I can edit the. I can edit the stuff.

Samurai Gyroscope: Yeah, sure.

Redolent Unicorn: I can have like this node. It's a valid input, right?

Samurai Gyroscope: Yes.

Redolent Unicorn: Okay, so I given some head of a tree input values to delete and I need to return all the. All the roots after deleting the nodes in the to delete? Yes, the to delete array. Okay, so let's for example, if I just need to delete one value, I will go around this. So have this 245. So first, like I think in order to make the lookup faster, I will create some. I will convert this array into set. So I'll have a set of delete. So I need this in order to just have ookups. But now when I have the set of nodes to delete, I'm starting at the root. Since I don't need to delete the root, I will search its children. So say I'm doing some kind of BFS traversal. So now I will look at the left kid, left child. It's two. It's not equal to one of my values. I'm searching the set. I'm searching three in the set. Three is a value in the set. So let's say if I delete it or just mark it somehow. Now what it created disconnect all the children from the set. So just in this case the output is like the same is 167. This is the expected output, right? If my tudelity is just to.

Samurai Gyroscope: Yes, yes.

Redolent Unicorn: Okay, so if I delete three. Sorry, one more question. Does all the values into delete array are unique or they can be duplicates?

Samurai Gyroscope: That's a good question. They could be duplicates. But for the sake we can assume that there will be unique.

Redolent Unicorn: So for the sake of the we can assume that they are all unique. Okay, so let's go back to the simple example of just three. So if I remove the node three now I created two disconnected twists, six of seven, let's say six and seven and my original tree is still. My original tree is disconnected from 6 and 7. So what I can do if I start with this res output. I'm starting with the original node. If I don't delete it and now go BFS to 2. So, so 2 is okay, 2 is not part of the set. Now I go BFS to 3, 3 is a part of the set. So I delete it and I attach his children to the result array. So for example, if he had no children. If he had no children, the result will be just one, right? Because we have still just the original tree. So this is with the result, right?

Samurai Gyroscope: Yes.

Redolent Unicorn: Yes. Okay, so this is in the simple case. Let's see. What if we have also five in the to delete. So in the set we have three. Five. After, after we disconnected three, we continue our BFS and we check if four is in the set is not. Now Next in the BFS we check if 5 is in the set. This is. This is holds true. So we disconnect five and attach its children to the result. So since it it has no children, the result is still 1, 6, 7 and in 6, then we continue with BFS467 and they're both not in the set of nodes to delete. So we end our iteration and return 167. Let's see. Let me. I finished this example. But let's see. Five has some children. Let's call them eight and nine. Those are children of five. So if we disconnected five, we attach. We would attach his children to the result array. So you said that the order doesn't matter, right? The order of the output. So we attach his children and 6, 7 are the same logic. So we had 1, this subtree 8, subtree 9, subtree 6 and 7. So this sounds okay for me. Do you have any question about my logic? This makes sense to you?

Samurai Gyroscope: Yeah, makes sense.

Redolent Unicorn: Okay. Regarding the time complexity of this of the solution, so I need to convert the set. So the 3 has n nodes and 3 as let's say the 3 has n nodes. So time of creating the set is O of N creating the set, then we need to iterate bfs. So we're iterating over all the values. So it's o of n iteration plus lookup of o of 1. So it's still O of n for the iterating. Deleting. Yeah, yeah. So deleting is o of 1. And so overall time complexity is O where n is the number of nodes. The number of edges are like the same as the number of nodes because it's graphs with no cycle connected graph with no cycle. So the same and space we have array, we have the set that is O of N. We have the result that is can be possibly like half of the nodes. So let's see. So it's also O of N space and for the BFS we need to have a Q that is also O of N. So overall is also three times O of N. Space and time complexity are both O of N. Okay, sounds logical.

Samurai Gyroscope: Yes, sounds good. Do you think either of these can be improved further?

Redolent Unicorn: Let's. I'm thinking about the space because for time I will have to iterate over all the nodes no matter what. So it will stay over N. But for space if I'm doing. If I'm doing a bfs. So the numbers in the queue would be half of all the values if the tree is balanced. So it will be. Okay, let me think if I can solve this problem without BFS. So without the queue of BFS. So the input is just a 1. The input is the head of the tree away to delete I can give up on the set and search. Search with inside the array of the to delete values. Ah, now okay, the question does the two delete array it bounded or it unbounded in the size the this to delete array?

Samurai Gyroscope: Yeah, so it's going to be bounded. So it will be limited to the number of nodes at your tree.

Redolent Unicorn: Ah, okay, so so the search is. The search in the array is still O. If it's unsorted I assume it's like general array not sorted.

Samurai Gyroscope: Yeah.

Redolent Unicorn: Yes. So if I give up on this creating set from the array I can get rid of the oven space. I still have the queue of the queue of the bfs. But now the searching the time complexity becomes much higher so it becomes oven squared. Because for each node I need to search in the array so it's oven square time and they still have oven space due to the bfs. So even like if I would get rid of the BFS I still be in O square time. So I think it's better to have space than O square time and O space over.

Samurai Gyroscope: Yeah. So if you were to choose between these two options.

Redolent Unicorn: Yes, so if I would need to choose between those two options, I will choose the current one that is on screen. So oven time and oven space both.

Samurai Gyroscope: Yeah, sounds good to me. If you have any additions, feel free to add, but feel free to start coding otherwise.

Redolent Unicorn: Okay, I will just copy it. I'm not sure if it will be converted to python.

Samurai Gyroscope: Yeah, you should. Yeah.

Redolent Unicorn: Okay, so this is strange.

Samurai Gyroscope: It didn't save right the previous I copied it.

Redolent Unicorn: I copied it because I wasn't sure if it will be copied. Okay, so I would call this function so subtweez and it take root and to delete, do you want me to also implement the node class?

Samurai Gyroscope: No, like it's fine for you to just like write the definition for node class. Like. Oh, actually you don't even have. I mean. Yes, just write the general.

Redolent Unicorn: So what do you mean by general? Just write the. Write the class.

Samurai Gyroscope: Yes.

Redolent Unicorn: Okay. Sorry. Yeah, so selval. So self val equals value and self left is none. And self right is also none. Okay, this should return array of nodes. Okay, so I need to convert this to set since it is array. Fortunately, it's quite easy in Python to do this conversion. After that need to create a Q Q of the wood. Create Q from the wood and I need the result array. And while the queue is not empty, I need to pop the node. So pop from the left because this is a need to use it as a queue. So pop left and I will push to the cued children. So Q push. If. If the if it has node dot left I will push its left child. Same for its y child. If it exists, will push it. And I forgot I need to add. So this is for the bfs. Now for the logic of creating the output of the function. So if. If the value of the node is in the subtree is in the the to delete set in to delete set what I need to do is to push is both children. So I need to append this right Chin. Let's be consistent. We start with left. So let's be left and sorry, should be. I need to return the nodes, not the values. Okay, so I push the node node dot write append node dot write. But I'm missing something because in the in the start I need to have the initial node, but if I'm disconnecting it it if the initial load is into delete I need to remove it. So what I can do is I can append the root. And if if root.value if root value is in the to delete set I will immediately remove the root because it's not part of the of the result. So let's just remove the first value. So if I'm deleting from the set I'm appending and let's see if I'm missing some logic, then return the result. It would be okay if I will dry one against some test cases because it will be easier for me to see if I'm Missing something or have some bugs?

Samurai Gyroscope: Yeah, sure.

Redolent Unicorn: Okay. So initially I want to try just the one root. This is my input, this one. So my to delete set is 1. Q is 1. Root val is in to the Ah, I need also to delete. So let's say to delete set is empty. So to delete. Sorry. To delete is empty. This is the empty array. It's part of the input, not not the variables. And so root VAL is not in delete set, so we don't pop. Q is not empty. Q is not empty, so we pop 1. So node is 1. Q is now empty. Node left and node right are none. Node val is not in the delete set. Forgot to initial initialize the result. So we return the result 1. Let's say if we have to delete, let's say we have this problem from before and to delete is 3, 5, 3, 5. To delete set is 3, 5. Q is 1 root res is the root and it's not the value is not in the delete set. Sorry. This is 3, 5. So we start with node 1. We pop it where is the queue and we push left and right. So we push 2, 3. Node Val is in the delete set. So node that val is not in the delete set. So we continue to next iteration. We we pop from the left. So we pop two. And now the value is two. We append these children. So we append four and five to the queue. Note that val is not into delete is not in the delete set. So we continue to the next iteration. We pop. I'm popping from the left. Yeah, pop from the left. So node is 3. Now this 3 append is children 6 and 7 to the queue. Now it's in the delete set. So if it's to if is in the delete set, we append still when we append his children and next iteration 4. 4 has no children and it's not in the delete set. So next iteration we pop five. Five has no children, is in the delete set, but it has no children, so we don't append to the res. Same for 6 and 7. They are not in the delete set. So we finish iterating and return the result. 167. Okay, let's if I miss something in the logic, let's say I have node 2 and 3. Does it still work? I start with 1 in the result, 1 in the result. Then it should be 1, 4, 5, 6, 7. Yeah, so yeah, it still work. Okay, so I Think it's okay if you have any question or you want to point something.

Samurai Gyroscope: Okay, so the expectation here is to have a working code. Will you be able to write like a main function calling this function and then provide.

Redolent Unicorn: Yeah, sure. Yeah, yeah. So from. Actually I don't remember where to import dequeue from. Can I look it up or.

Samurai Gyroscope: Yeah, sure.

Redolent Unicorn: Okay. DQ DQ In Python it's from collections. Everything is from collections. Okay, so the tree. How do I define a node? Here is node. This is. You want to print the subtwist with three and to delete let's say it is empty. In this case expect 1, 1. If the delete. If I delete this. If I delete it, I expect an empty set. Now, now let's create some children. So root dot left. So I will just. I will copy paste it because was a good example. Copy paste. Okay, so node two, node light. It's no, there's three. It is not. So it is root and root left left, root left right. This is 4 and 6, 4 and and 5. Sorry, not 6 and vice versa. So this is node right left and node right right. It is 6 and 7 and we're passing 3 and 5. Passing 3 and 5, not 4 and we expect 1, 6 and 7. Can I run it?

Samurai Gyroscope: Yeah.

Redolent Unicorn: Okay, now the object is not iterable in line 38. Ah, 920. Ah, maybe I cannot convert it. I need the value. Okay, so I'm trying.

Samurai Gyroscope: Okay, so if your object is not iterable, what are the alternative ways to put things into deck?

Redolent Unicorn: Yeah, so I can create a queue and append. Append. Append this boot. Okay, I will run it again. Sorry, this is. I think it's append. Yes.

Samurai Gyroscope: Okay. Okay.

Redolent Unicorn: I need the. It's. Yeah, it's object. So yeah, I will take the result and print it. So friends, this should take 25 and this should be not. I don't need this. Print this one. This is empty and this is one six, seven. Is it one? Okay. Okay. It as. As I expected. Doubtfully as I expected.

Samurai Gyroscope: Great. So do you think we can test with more edge cases?

Redolent Unicorn: Now.

Samurai Gyroscope: What could be a potential edge case for this problem?

Redolent Unicorn: If let's say I want to remove a leaf. Or am I testing it? Ah yes, I'm testing with five. I'm removing a leaf. But let's say I'm removing two children. So in this I will remove two and three. I will expect this. So let's test removing two children.

Samurai Gyroscope: You can actually directly modify. Oh yeah. Oh, you can just do this here.

Redolent Unicorn: Deleting two children. And other than that, if I delete two and three, this is deleting two children. Deleting leaf. I'm testing. Deleting the root. I'm also testing.

Samurai Gyroscope: So what would be the expected output in deleting two children?

Redolent Unicorn: Yeah, it should be 1, 4, 5, 6, 7. This should be the output.

Samurai Gyroscope: Okay.

Redolent Unicorn: So let's run it. Yeah, this is the result. I just needed to put a delimiter between two prints. But this is the expected results.

Samurai Gyroscope: Okay. More education that you can think of.

Redolent Unicorn: Let's say I remove. This is my tree and I remove. I remove one. I should expect two and three.

Samurai Gyroscope: Okay.

Redolent Unicorn: And I think it's a good cover. It covers all the cases I can think of. You want me to run it?

Samurai Gyroscope: Yeah.

Redolent Unicorn: Okay, So I delete one and expect two and three. Okay. As expected.

Samurai Gyroscope: I want you to think about more each cases, if possible. Like two more.

Redolent Unicorn: Yeah, yeah, sure. And deleted the wood. This is. Okay. Deleted the wood with children, Deleted the leaf, Deleted two children and deleted two children. Let's look at the input. So input is a. Input is a value to delete. I tested. Yeah, I tested. If to delete is empty. Let's say if to delete consists of a value that are not in there, not in the tree. So let's say to Delete have a 10 here. Sorry, this is not the to delete. This is the result. To delete have 1 and 5 and what more inputs. I have the two deletes and the array of nodes and that's one. This to delete with 15 expect the same result. Yeah, this M. I don't have any other edge cases coming up to my mind currently.

Samurai Gyroscope: Okay, so what happens if the tree provided to you is empty?

Redolent Unicorn: Oh, so let's say I provided an empty tree. Yeah, If I provide an empty tree so the result will not be correct. I have a random error because I will check the fruits val. So if I provided an empty tree, I need to return empty array because I cannot. There's nothing to remove, so there's no subweave.

Samurai Gyroscope: Yeah.

Redolent Unicorn: Yeah. So let's test it. So let's have root equal to none and we delete whatever we expect empty array. Actually, let's print the result because it's not. Let's print the result. It should be an empty array. Yes.

Samurai Gyroscope: Okay. Can you think of more edge cases or is that all?

Redolent Unicorn: I don't have any more edge cases coming to my mat.

Samurai Gyroscope: Okay, so what happens, for example, if we're gonna delete some node and Its immediate child. So let's assume in this case it's gonna be two and five.

Redolent Unicorn: Two and five.

Samurai Gyroscope: Yeah.

Redolent Unicorn: So let's say deleted, delete two. I push his children. Yeah. So in this case my logic will not be correct because five will be in the result set and it should not be. So actually I need to move this logic into. Into here. So if the value. If the node dot value. If the node dot value is into delete set. So let's create a res. Let's create a res. Converting the result into a set so I can pop from it more easily. Can delete from it. Sorry. So if no value is into deleted, so it should not be in the result. So we delete it. For we delete the value. Also remove it. Remove. Remove the node. Remove the node. And yeah, all the logic stay the same. So let's take this three, let's have this simplify tree. So I have 1, 1, 2, 3 and I remove 1 and 2. I expect the result will be three. So yeah, no left for node. So expect the result to be just. Just three. So res should not be append, it should be res. Add. Since it now is set and we need to return an array. So I think this should work. Then return an array. Yeah, so let me run it. Yeah. So this, yeah, this is return three. So can I maybe reset it one again so it will clean? Yeah, so it return three. So yeah, this is the edge case. I didn't think of total.

Samurai Gyroscope: So what happens if two has children below it?

Redolent Unicorn: If two.

Samurai Gyroscope: Yes. So imagine it has something under this, like.

Redolent Unicorn: Yeah, and we. Yeah, and we remove two. So in this iteration in the queue, so we pop left two is in already in the delete set. Maybe two is in the delete set. We remove two from the result and it has children, it has four and five. So we append four and five. Four and five are not. We push four and five for the queue, we iterate over three. So at the start it's like this. The node is 1, 2. Sorry, we delete 1. So it starts with 23 as the result. Now when we iterate over 2, we remove it from the result and append 4 and 5. We iterate over 3 and since it's not into delete set, we do not do anything because it's not. It doesn't have any children. And same for 4 and 5. They're not in the delete set. So we return them. So let's run some test case. So dot left and dot right equals to 4 and 5. This I reset, I delete 1 and 2 and expect 3, 4, 5 the result. Yeah, 3, 4. So the order doesn't matter. So it's okay.

Samurai Gyroscope: Yeah, sounds good. So I think with that your solution is now complete. So. Okay, so if you had, let's say like more time, would you change anything in your code or approach or would it remain the same?

Redolent Unicorn: I don't have anything coming to my mind right now.

Samurai Gyroscope: Okay, sounds good. Okay, so we can wrap up the interview part of the session. So I've written some feedback and then I'm gonna brush it up a little bit and then like put it into the feedback session after we finish this. But you had other questions related to the actual Google interview, right? So you can ask them now and then I will send back after this.

Redolent Unicorn: Yeah. So regarding the scoring way of Google, I read that they have three metrics, so problem solving, coding and communication. So what are like the kind of low hanging fruits that a lot of candidates. Candidates fall that like I can easily fix. So the common mistake that a lot of candidates fall in.

Samurai Gyroscope: Okay, so I think like lots of candidates pretty interview as if like it's a one sided evaluation. But as you might know, the interview is more like a teammate discussion. So I think you did pretty well on this kind of in this regard here. So you kind of made sure to explain things and then just like jump to the next session and then you will kind of practice guiding the whole session, which is good because most candidates just wait for the signal from an interviewer to do what is next. So they ask for the things from the interviewer. I don't know like oh, could you provide like test cases or could you do should I like start, should I begin? And so on. So it feels as if really like it's kind of a one sided evaluation and because like depending on the level you are aiming for, you should exhibit certain skills. Like for example, if you're L4, you should be already kind of acting independently like solving your problems and asking for minimal directions. So that interview is also assessing that part as well. I think you did pretty well because like I didn't have to provide many things here. And then you kind of like when you were stuck, we were pretty much discussing things not like me, I'm stuck kind of like unblocking you. And so I believe this is the low hanging fruit, like the way how you treat the interview session. Regarding the problem solving part. Most candidates forget to cover edge cases first, which you also didn't in this session. And as you might know, edge cases are very important in terms of structuring the code, making sure that you took the right approach and luckily your approach was amendable quickly amendable to allow to handle these edge cases after coding it. But most candidates actually end up writing a very rigid code which ends up being very messy after debugging. And it lowers their score by a lot because depending on level again you always need to look very into the future and make sure your solution handles different possible cases. So I think these two are very important. One of them is low hanging. The other one is like, let's say like a basis that you expect from good engineers. And most candidates they don't like exhibit this too in my case.

Redolent Unicorn: Yeah. Cool. Just one small question. I saw that in interview to meta I need to debug to run my test case like a debugger does. It also applies to Google or it's less important than thinking of edge cases running the code like a human debugger.

Samurai Gyroscope: So it depends on an interviewer. So some parts of Google do the actual provide you the actual link to an ID like for example DeepMind, part of Google or like Google Research they also do this but I believe like main Google like if you haven't received in your calendar link any links to IDs that means most probably your interview is going to be held in Google Doc and then there you write your code as if there is no ide and then most probably you're not expected to run a fully running code, debug it fully. But any kind of approximations to that is very much praised. So if you do like dry run through and then if you see any kind of possible errors you could like fix them on the fly and then dry running through it and maybe showing that you're testing things maybe in comments or as you did here by creating edge cases and programs under your solution is very much appreciated. And if you're not sure about the actual approach ID or not id, you can always message your recruiter. But my hunch is that if they didn't provide anything in your calendar link, it's going to be Google Doc.

Redolent Unicorn: Yeah. Okay, sounds great. I would like to have like a more interview with you if it's possible.

Samurai Gyroscope: Okay. Welcome. Yeah, I will mark it like yeah. Or open for rematches. Yeah, should be done.

Redolent Unicorn: Okay, sounds great.

Samurai Gyroscope: Welcome and good luck in your interview.