Python Interview with a Facebook engineer

Watch someone solve the inorder traversal problem in an interview with a Facebook engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Inorder Traversal

Interview question

1) Given the root of a binary tree, return the inorder traversal of its nodes' values. 2) You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's. Increment the large integer by one and return the resulting array of digits.

Interview Feedback

Feedback about Mythic Platypus (the interviewee)

Advance this person to the next round?

How were their technical skills?

3/4

How was their problem solving ability?

3/4

What about their communication ability?

4/4

Strengths: + TC was able to come up with the solution for both of the problems. + TC was able code the second problem by themselves. + TC has good debugging skills. TC debugged issues in their code. + TC was able to communicate their ideas clearly. + TC was good listener. TC took on hints and improved their code for the first problem. + TC was able to analyse the complexity of second problem correctly. Improvement Areas: - TC struggled with redundant code. They should try to avoid this. - TC wrongly analysed the complexity of their first problem's approach. - TC struggled with converting recursion into code. Suggestion: Practice bit more on recursion and binary tree and schedule one another practice interview.

Feedback about Red Maelstrom (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

3/4

How good were the questions?

4/4

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

4/4

This was the first mock interview where I felt totally comfortable and felt like I could ask questions. This is also the first mock interview I've done where I completed two coding questions. In other cases, it took me 45 minutes to get through one. You were very helpful during this interview. Keep up the good work!

Interview Transcript

Red Maelstrom: Hello.\nMythic Platypus: Hi.\nRed Maelstrom: Hi. Can you hear me?\nMythic Platypus: Yes.\nRed Maelstrom: Cool. Awesome. So we'll spend like 45 minutes on coding problem, last 10-15 minutes for feedback. So before we start, can you tell me like, do you have hard stop after 1 hour or it's okay to go a little over?\nMythic Platypus: I have a hard stop after 1 hour.\nRed Maelstrom: You have okay, I will try to keep it as close to 1 hour as possible. Okay, cool. So this is the first question. You have a root of a binary tree and you have to return the in order traversal of its node.\nMythic Platypus: Okay. So in order traversal, that would be the order where the left nodes are returned. Then let's see. So if I have that's going to be hard to draw a tree, but I'm thinking of in order I'm thinking of going down the left subtree and then returning that left leaf, then returning like, its parent and then returning the right node. Is that correct?\nRed Maelstrom: What would be in order to this? Correct? Yeah.\nMythic Platypus: Okay. And then we have a binary tree, and that means that each node has at most two children. Okay. Yeah. Let's see. Do I need to choose my language?\nRed Maelstrom: Yeah.\nMythic Platypus: So given the root of a binary tree, return the in order traversal of its node values. So I need to write a function, and I'm given the root of the tree and like, in this example, given the roof, the tree before, and I need to basically return an order traversal. So I'm thinking that I want to take maybe take a recursive reproach. So if my tree if I'm giving none as a route, then I just basically return none. Yet if the root of this tree is valid, but it doesn't have any children, I'll just return the root value. Those are my two base cases or cases that I think of immediately. And I know that I want to return the left subtree or the left leaf node, node, parent node, and then the right node. So let me think.\nRed Maelstrom: How would you define a tree node?\nMythic Platypus: How would I define a what node?\nRed Maelstrom: Binary tree node.\nMythic Platypus: I don't think I understand the question.\nRed Maelstrom: Like, how would you represent a tree node? Like, will it be a class? Like, how does the tree node class looks like?\nMythic Platypus: Oh, that's not given. I assume it'd be some sort like, a node with value and I'm sorry, the value left and right.\nRed Maelstrom: Okay.\nMythic Platypus: Yes, left and right pointers.\nRed Maelstrom: Okay.\nMythic Platypus: I know that I want to get down here. So I started the root node, and then I checked to see if the root node has like, a left subtree or like, a left node. And if it does, then I would like, repeat the check if it has a left or right subtree. But if it doesn't, then I can return this value and then it would backtrack and it should visit this node again and return it. And then it should visit this node and return it. So how do I code that given the root? I'm given the root of a tree and I want to return the in order traversal of its nodes values. I have these two checks in the beginning. If root is none, then return none. And if that's not the case, if root left equals none and root right equals none, and I just return root value. Those are like my base cases. Now I need to think about how to think about the case where I have a left and right child. Let's see, think about it up here. If root has left subtree left child, then I need to basically call this function again like a recursive call. It would be like in order route. And now I'm hitting a bit of a difficulty because I know that it can return the value of the get to a leaf node. I know it will return the value, but I'm struggling to figure out how to get the parent node, I guess, printed out before that. Right? Sub tree node.\nRed Maelstrom: You don't need to print out. You need to return a list. So the output is expected as a list of this.\nMythic Platypus: I don't need to return them.\nRed Maelstrom: I just need to you don't need to print. You need to return a list. You need to create a list and return it.\nMythic Platypus: Okay, well now that changes things. I need a minute to think.\nRed Maelstrom: Sure.\nMythic Platypus: I can't do recursive because I need to add on to the list instead of adding or creating a new list each time. So I need to figure out the structure of how the structure of this code.\nRed Maelstrom: Can't you update a list that you got from left subtree? The list that you got from right subtree?\nMythic Platypus: I'm sorry, could you repeat that?\nRed Maelstrom: Can you just obtain the list? Let's say, for example, if you get sorry, list from left, I think there is an eco. I don't know why. So if there is a list from left subtree and if there is a list from right subtree, you can append them?\nMythic Platypus: Yes, I can do that.\nRed Maelstrom: Base case is already taken care of. You just need to worry about recursive it. Cursing. It like, let's say like so you call a left side and you get a left list, right?\nMythic Platypus: All right.\nRed Maelstrom: Right. How will you append them?\nMythic Platypus: I would just do left list plus right list.\nRed Maelstrom: You also need to append the value of this current node in between, right?\nMythic Platypus: Yes. Okay. If I look at the code that I have now, I have a result list which is empty, and I'm starting at the root node. If the root node is none, then I return none. Or I guess if it's not, I want to return an empty list instead. If it's just the root, then I just need to return the root value. I don't think that's completely right. Because if I'm calling on this like recursively. It's not adding to the list. It's returning a single A list with a single item in it. I need to edit result and then return result. There you go. Let's see.\nRed Maelstrom: So if you are creating result, then do you want to return the result?\nMythic Platypus: I don't want to return the result because that would cause the function to basically end. Okay, so now have this case out here. And then once we get to this line, it's going to call order in order and it's going to return or it's going to have this as the parameter. And this can either be because the next node really doesn't exist on this side, or it can actually be another node valid node.\nRed Maelstrom: You already check. Even if you go to the none, your base case will be taking care of it, right?\nMythic Platypus: Right. Correct. Here I'm thinking at the end of this, I do, I know I need to add the left list plus the current node plus the right list. So I need to do this. This I don't think that will work. Okay. Because I wanted just to add sorry. I wanted to make it a list value. I don't think that works in Python. So.\nRed Maelstrom: Do you really require the case? This condition at line number 29?\nMythic Platypus: What about the condition at 29?\nRed Maelstrom: Do you need it? Because like, even if you go to the non node you are taking care of. Right.\nMythic Platypus: I'm a little confused because if I pass a route like a non node in, then we return empty.\nRed Maelstrom: Right?\nMythic Platypus: But 929 is the case where the route is valid.\nRed Maelstrom: Right. Let's say you pass five to line number 29, right. And if you don't have this condition, you will end up calling none and none for left and right. And you will get two empty list and just append five in it. Right. So this.\nMythic Platypus: Basically does the same. It does the same thing. I see. Just a step to do the same thing. Okay. So if that is the case, then this is not necessary because it just repeats the same, right?\nRed Maelstrom: Yeah. Cool. Awesome. I think this should work. Let's move to the second question. What would be the complexity of your code?\nMythic Platypus: The complexity of this here?\nRed Maelstrom: Yeah.\nMythic Platypus: So it's traversing the tree and the binary tree and it's going to visit each node once. Would it be for the time complexity of log in? And then the space complexity would be.\nRed Maelstrom: Login. Why would be the login for the.\nMythic Platypus: Time.\nRed Maelstrom: What is N? There.\nMythic Platypus: Is the number of nodes.\nRed Maelstrom: How it would be logged in.\nMythic Platypus: Because it's a binary tree. So it's basically looking at half of the nodes each time, I believe.\nRed Maelstrom: But you would be visiting each node at least once, right?\nMythic Platypus: Right. Yes, that's true. I will be honest and say I'm not well versed in trees. This is probably one of the few tree questions I've actually practiced on. I know that binary trees that when you traverse them I guess that the time complexity is O of log in.\nRed Maelstrom: Yeah, actually I put the order of n because you would be visiting every node. Right.\nMythic Platypus: Okay. I see.\nRed Maelstrom: Understood. Cool. Let's move to the second question. Like I have posted the second question at the top.\nMythic Platypus: You are given a large integer represented as an integer array of digits where each digit is the 8th digit of the integer. The digits are ordered from most significant to least significant and left to right order. The large integer does not contain any leading zeros increment the large number the large integer by one and resulting return the resulting array of digits. Okay, so look at the first example. I have one, two, three and I just want to add one to it. The array represents the integer 123. Okay. Okay, so I'm just basically given an integer and I need to add one to it and return the resulting array of digits. Okay, so let's see. Okay. And I'm always going to increment the digit by one. I don't have to carry a digit over and there's a case where I do have to carry a digit over. Let's see if I'm looking at the first case one with one, two and three I can go over to the ones place, get the value from there and add one to it and then basically replace the three and have the new digit included in there. But if I look at this third example here, I just can't simply replace the I can't just replace that element because I would need to have two different elements in the output array. So my first thoughts it is that I can make it a bit easier. I can reverse the array and then I know once I reverse the array I'll have the ones place in the very front and so I can add one to the ones place. Then I have like the two cases I have to think about need to carry and don't need to carry. After I consider all of those cases then I can reverse the array and then return it. So if I need to carry, I can have that being I can indicate that with a variable if this variable is true, then I do the addition. I'm sorry. If I need to carry, then I'll indicate that with the variable like a true or false variable. And then if I need to carry, I know that the one's place digit is nine and that nine needs to turn to a zero. So I will replace the nine with a zero and then I would increment the next digits place. In the case of me starting with the ones place, I'd go on to the ten, the tens place and then I would just add one there. But also I still need to check if I need to carry because if I have a number like 1999 more than once and then if I don't need to carry and I just replace or just simply add one to the digit. Okay. Is this approach clear?\nRed Maelstrom: Yeah, I understand it how it will work on this case.\nMythic Platypus: So if this is the example I have, the first thing I would do is reverse it to this number. And then second step, you add one to the ones place. And so I need to carry in this case because I'm working with a nine. And so like I said, I would have a carry variable evaluate to true this nine would become zero and then I would iterate to the next spot right here. The carry variable would still be true. So I would change this to a zero as well. And then when I get to this next place after the evaluations are done and my carry variable, what do you call it? When my carry variable evaluates stuff off, all I'll need to do is simply add one to this place, it'd be nine and then I just return this reversed again.\nRed Maelstrom: Cool. I think. Yeah. What would be the time complexity of this?\nMythic Platypus: Of this? So reversing the array itself would be a time complexity of N and then this would be a loop that would be O of N as well. And then this version array again is O of N. But when I reverse the array those are like outside of this loop. So the overall time complexity of this looks like it's going to be O of yes. If you don't reverse your array, you can just iterate to the end of the list, add one and then you can continue with the same loop. But you would have to go backwards. Yes, I think it's possible to do it without reversing the array.\nRed Maelstrom: Okay.\nMythic Platypus: So which one should I code first without reversing? If I want to just add one to the ones place, I need to get to the very last digit. So I can do that with going to go backwards one. Okay. So starting at the end of the list, I'm just going to copy this down lower so I can see it. Okay. So I want to add one to the ones place. So I need to see whether or not I need to carry. And I do this by if the array at this position is equal to nine. If it is, I'm going to have a variable initialize it to false. If the array of this digit is equal to nine, then I know I need to carry. So my carry needs to be set to true. Let's see if that's true. Let's see. I need to update this digit to zero. Okay. If the array at this digit is equal to nine, I need to carry. After I set carry to true, the array at this particular digit turns into a zero and I need to increment the next digit by one only. If I don't have to carry. Okay, let's this is going to get messy, I guess, before it gets clean.\nRed Maelstrom: Do you need this? Like, you already turn back to it, right? If it is not going to get carried, then you will just break the forward loop.\nMythic Platypus: Okay. I'm doing I'm trying to do a lot of work in one loop. Okay, I see. Okay. I'm going backwards. If I need to carry, that means that the digit I'm at is equal to nine. And then I could just change this digit to zero else at this variable equals.\nRed Maelstrom: I think yeah.\nMythic Platypus: Okay.\nRed Maelstrom: Do you want to test it?\nMythic Platypus: Okay? Yes, I'll do that. I'll just return here at the end. Okay. So I'm working with one, two, and three. I'm going to have for I in range. Okay. So the length of this array is three. It's going to start at two until it gets up to negative one. You just wanted to actually print it out. Okay. That is not what we want. We only want to increment it by one. Okay. So where am I going wrong here? So I want to start at the end of the list, and if I need to carry, then I carry.\nRed Maelstrom: Do you need to break the loop and it will start where you increment it?\nMythic Platypus: Yes, I know I need to break the loop. I'm just trying to understand where because, like, in the case that I just only have to carry once, I think this is fine. And I can increment or I can just break. But I'm curious about, like, when I have two nines in my number.\nRed Maelstrom: Yes, sir.\nMythic Platypus: I think this could work for here. It works for this case because right now I'm only editing my carry value once, but I might need to fix it.\nRed Maelstrom: Do you mean something like this?\nMythic Platypus: Yes.\nRed Maelstrom: Do you want to try anything for this properly?\nMythic Platypus: Okay. I'm sorry.\nRed Maelstrom: I think it will fail for all nines if everything is nine.\nMythic Platypus: Okay, I see. Okay. I was worried that it wouldn't register all the nines I see now, but.\nRed Maelstrom: For all nines, I think it's fulfilled.\nMythic Platypus: Okay, well, that is another case I need to get finished, like whenever I need to add a digit. Okay, interesting. Okay, let's see. I know I need to add a digit whenever my carry variable is still true on the most significant digits.\nRed Maelstrom: Right.\nMythic Platypus: So let's see. Right now, I'm just replacing the digits. I need to have some sort of condition or write it some sort of condition that will tell me whether or not I need to add a digit and then I can just insert right. I feel like there's like, subcases with this one too. You have nine, nine, nine. You can also have something like 1000. No, that'd be fine. Okay, I see now. Okay.\nRed Maelstrom: You can even count if everything is nine. Right. You can have counter. Like if everything is nine months, depending.\nMythic Platypus: I would do this outside of the loop? No, because if I do it outside of the loop at the very end, then none of the nines would be there. There'd be all zeros.\nRed Maelstrom: Yeah. So you already have this condition here. You can just increment the count.\nMythic Platypus: Okay, I guess I'll do it at the beginning. So if of the array count of nine is equal to the length of the array, it should be. I'm thinking I should indicate that with a variable and then like, look at that variable at the very end. So at the beginning of the loop or right before the loop, I would count the number of nines. And if the number of nines is equal to the length of the array, I need to set something to true. So like, I guess add a digit that will be set to true. And then once I get at the end of this for loop, I can say if add digits true, then I can do the array right at the beginning. Position one. Okay, I run this.\nRed Maelstrom: Awesome.\nMythic Platypus: It works perfectly. Okay.\nRed Maelstrom: Does it work for the previous cases.\nMythic Platypus: The time complexity of this function? Let's see. So I have some if statements, which is constant. I have some initializations constant. I have this loop here. Okay. So the bottleneck of this function is this for loop here. And this for loop is only iterating an array backwards. So all the elements in the array, I would consider that to be N. So I think the time complexity of this would be O of N.\nRed Maelstrom: Cool. Yeah, that's correct. Do you want to drive another program or you have hard stop?\nMythic Platypus: I kind of have a hard stop. I don't think I'll be able to answer the next question in the next 15 minutes.\nRed Maelstrom: Okay.\nMythic Platypus: I just want to talk about feedback and whatnot what I can do better. I know you have an evaluation, write it down. But is there anything that we can talk about now?\nRed Maelstrom: Yeah, I like that. For the first problem, even though you were new to the binary space, you identified that it would be a recursive approach. So you communicated it correctly that it would be a recursive approach to solve the problem. Then you came up with base cases. Like when the tree is none, allude root has no children. Like those cases. Right, right. You came up with the appropriate structure for the node. You converted your base cases into code easily. I think there was redundant case, like only root personal was required. Base case. Right. And that should be sufficed. So the case was not required. Maybe with the practice you will understand this, like why what cases are redundant? So my solution would like to practice a bit more on the recursion and a binary. I have shared a link at the top for the binary tree as a resource.\nMythic Platypus: Okay.\nRed Maelstrom: So my session would like to go through the basics of it. I think you mentioned the time complexity would be logging, whereas like the time complexity was N, which was a big difference. But yeah, as you mentioned, you are new to binary trees. It is expected. But yeah, the second question, I really like the way you approach. You clarified that it will always be increment by one or will it differ by one or two or three, things like that. You clearly identified the case where you need to either carry or you don't need to carry. Right. You shared a step by step approach. I really understood what you are trying to think. But I think the carry was not used. This variable carry was never used. So that was again a redundant code. In your code, if you see carry is never used. It's initialized, but it's never used. The expectation would be like even at least if you are using it. But after the code, you are done with the code, you can identify what is your redundant code and remove it. This carry was never used.\nMythic Platypus: All right. This served as the carry variable basically.\nRed Maelstrom: Right?\nMythic Platypus: Okay.\nRed Maelstrom: Yeah. I think initially you missed breaking from the loop and end up incrementing everything. But you were able to debug it and figure it out what is the issue and debug it. So that's all good. I think you also handled the edge case of all being nine correctly. So yeah, I think in the second problem, you did really well based on this overall interview. It would have been higher call, let's say. For example, this would have been a phone screen. I would have asked, given a recommendation, to move to the next step and call forth on site. But yeah, my session would be like to practice a bit more on binary trees and recursion so that those glitches goes away.\nMythic Platypus: Okay, cool.\nRed Maelstrom: Do you have any questions for me?\nMythic Platypus: Let's see, I guess when you were on my side interviewing, what did you do to prepare specifically while you were in college? How did you prepare for interviews while handling school work at the same time?\nRed Maelstrom: Yeah, so I kept a target of like having solving at least two, three problems a day. Two was the target for me. I just not go into coding. I just don't try to get the solution coded. So I use the lead code. So basically I used to write down the approach in plain English language initially so that I get a practice of articulating my thoughts and then analyze the complexity of my solution and then start coding the problem. And I will try to come up with my own test cases so that solution gets accepted in a first go. My target was not to solve multiple problems with the good speed. My target was like to get solution accepted in a first quote. So I will try to force myself to think about test cases before submitting the code.\nMythic Platypus: Okay.\nRed Maelstrom: So that I get in the habit of identifying the issues in my code.\nMythic Platypus: Okay. And my next question is, since a lot of the interviews are virtual, how.\nRed Maelstrom: Do you.\nMythic Platypus: Try to visualize or show your interviewer what you're thinking? Because it's kind of hard to like I was thinking I didn't know how to draw a key or draw a tree in this coding environment. So is there any tips on how you can show your interview what you're thinking, even if it's virtual?\nRed Maelstrom: Yeah, so you can use the excalidraw so you can say that maybe I can share my screen. You can use excalidraw to draw things for the discussion point, and then you can stop sharing your screen once you share your thoughts.\nMythic Platypus: Okay, got you. Okay, I'll keep that in mind.\nRed Maelstrom: When are your interviews?\nMythic Platypus: I have one coming up in January.\nRed Maelstrom: Oh, my you still have time. Okay.\nMythic Platypus: Yeah.\nRed Maelstrom: Awesome.\nMythic Platypus: I'm still applying, but yeah, that was.\nRed Maelstrom: All the questions I understood. Cool. Awesome. Then I will give you your eight minutes back. All the best for your upcoming interviews. My suggestion would be to practice a bit more on binary trees and recursion, and maybe she is one more interview to make sure that you go through it.\nMythic Platypus: Okay. Yeah, of course. Thank you so much for your time today. This is really helpful.\nRed Maelstrom: Thank you. I think you need to write a feedback after this, so please do that.\nMythic Platypus: Okay. All right. Have a good rest of your day.\nRed Maelstrom: You too. Bye.