Python Interview with a Google engineer

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 ˜15 mins, 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? No
• 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

1. 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.
   Redolent Unicorn: Just like random values for now, what I'm expecting from you.
   Samurai Gyroscope: 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.
   Redolent Unicorn: Okay, so if I delete three.
   Samurai Gyroscope: Yes.

2. Redolent Unicorn: Okay.
   Samurai Gyroscope: So what I need to 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.

Edge Cases

1. If the tree provided to you is empty, what would be the expected result?
2. If all nodes are deleted, what happens to the tree structure?
3. If the nodes to delete are not present in the tree, do you get the original tree back?