Mechanical Llama, a Facebook engineer, interviewed Kind Dragon in Python
1) Write functions to serialize and deserialize a tree. 2) Determine if two numbers in the list sum to a target number.
Feedback about Kind Dragon (the interviewee)
Advance this person to the next round?
How were their technical skills?
How was their problem solving ability?
What about their communication ability?
Great job with the interview, I was really impressed by your performance! Summarizing some high-level feedback: * Loved that you explicitly wrote out the constraints, inputs, outputs, approaches, and test cases. This kept the interview very well-organized. * On the second problem. this is also another helpful similar practice problem and solution: * https://leetcode.com/problems/continuous-subarray-sum/description/ * https://youtu.be/wsTcByj8QbI Very small suggestion for improvement: after you finish writing code, make sure to let your interviewer know you are done with implementation before moving on to writing test cases (i.e. looking for corner cases).
Feedback about Mechanical Llama (the interviewer)
Would you want to work with this person?
How excited would you be to work with them?
How good were the questions?
How helpful was your interviewer in guiding you to the solution(s)?
I can't believe this is your first interview. Because you did it really great!
Mechanical Llama: Hello. Kind Dragon: Hi. Mechanical Llama: Hi. Nice to meet you. Can you hear me alright? Kind Dragon: Yeah, I can hear you. Mechanical Llama: Yep. Cool. I'll just do a quick intro of myself. So yeah, I'm a senior engineer at a big tech company. And I've been doing interviews for a while now at my company. But I'm still kind of new to the
interviewing.ioplatform. So if you have any feedback from me about the interview at the end, as well, I'd love to hear back from you. Yeah, if we can get the quick intro of yourself as well before we start. Kind Dragon: Okay. I am a senior engineer, too. I am a person that has more than 10 years of experience. And now I be leading the Google on site interview. Yeah. Mechanical Llama: Cool. That sounds great. So yeah. I guess before I get started, I also just wanted to share some interview logistics. And normally when I do interviews at my company, they're 45 minutes. So thinking, we could also like try to aim to finish this in 45 minutes, right. And then we can spend the last 15 minutes going over any feedback or questions? Kind Dragon: Yeah, sounds great. Mechanical Llama: Cool. Okay. So I'm actually going to open the drawing window for this problem. Okay. Yeah, yeah. So basically, what we're going to try to do is serialize and... we're going to write two functions. So one is the binary. Kind Dragon: I'm sorry, I'm sorry. There is a lot of echo. So I cannot have to catch your voice. Mechanical Llama: So is it better now? Kind Dragon: Can you use the headset. Mechanical Llama: Yeah. So I actually am using a headset. I can try to see if that helps. Great. Yes. Is it better? Kind Dragon: Yeah. Now we it's better. Mechanical Llama: Okay. Cool. Yeah, I think it is hard to understand later, you can let me know. Yeah, sure. Okay. Okay, cool. Yeah, so basically, what we're trying to do is serialize and deserialize, a binary tree. So for input, we have something let's take a second to write out an example tree. So we just have any like arbitrary tree, right? It doesn't really matter what's in it. So this is our tree. And what I want you to do right is write a function that given this tree class, or this tree representation, right? It comes up with so we have like a method called store which takes in the node, right, and then return some representation, right of the tree. And then we have restore, which takes should be list of nodes. Which takes this list and then returns the tree. And I think sorry, this is incorrect. Let me just rewrite this in actual
Pythonsyntax. Yeah. Yeah. So something like that is right. So we have two functions, one that takes in the tree representation. Returns a list of actually they should be list of ints and then one that takes in the list representation of the tree and then returns a tree class. Kind Dragon: Okay, cool. Okay. I think I understood the question. Before, start, I have some question. Okay. What is number of nodes? Mechanical Llama: Yeah, so that's a good question. You can assume that they all fit in memory. So okay, yeah. Kind Dragon: Minimum is zero, right. Okay. Cool. Continue, we're going to know what is the range of node values? Mechanical Llama: Yeah, that's a good question. So you can assume that they're all integers, but there could be negative values as well. Kind Dragon: So and in actually it can be from negative two to the 31... Yeah. Okay, cool. So okay, so okay maybe look at the root. Yes. Depart I think that our is the just the tree. So you need to be... Oh, root, we need to convert it to the list and then maybe pass the visual referencing yes and then next is we need to reach to exactly cool. Okay to serialize I think we need to use the DFS. So maybe we're gonna have to traverse in order and then we put the value one by one and that the time we need or so needed to prove node value. So, unfortunately integer we are able to print those values. So it is okay. So after that, maybe we could able to convert it to the list at this time. This time, time complexity is
O(n). Okay. And space I think we are because we're gonna use the system stack of recursion. And then the worst case tree the skewed to the left side or right side, it will be because system stack will be the same as the depth of the tree. That make sense? Okay, now, think about this tour. This time maybe I think we also make the we also epic to restore with the clear path. It postorder so at this time time is linear and space is also linear. So make sense? Mechanical Llama: Yep, that makes sense. Kind Dragon: Okay, cool. So shall we make another approach or get into the code which one do you want? Mechanical Llama: Yeah, sounds good. Um, can you actually maybe draw for this tree what the list would have in it? Sorry. Could you maybe draw out like for this tree? What you're gonna have in it? I'm sorry. Can you draw for like for this example tree? What would the list having it? Kind Dragon: Okay, so what do you want to convert the existing tree? Right? Yeah, exactly. Okay, cool. Awesome. Sure. So first, we'll start here, and then you know is right. For the first order... So, it will be one and then one and then it has the left is node so first I am going to write some code to write this for this mean needs to be called and start to hear from first and then go to light and then loot and then going off and the right is here, and then we let M and four and then next to three. And then that's it. Mechanical Llama: This makes sense. Yep, that sounds good. Kind Dragon: So, store three maybe had some trick, this time we need to talk diversity the left Okay. Well, I think not that so. Okay. Let me finish into my approach and then let me find the bugs by testing. Do you to make some changes equal two. You made the base case and then two. So, first we need to make base case. Okay good. So, me first start here with BFS. So, we need to do and maybe now we are and how okay to node. Okay now is going to let them that is here this case pass case are going to let you return on the left to return null so all you need right and then output. Mechanical Llama: Can you explain why you made this check? Kind Dragon: Yeah the reason is we... I think okay wait a minute please. Node needed to too bad. So, okay. Let me write this case. Now left is null and then the right is now right now ultimate value is the three combined to the left that is five by. Finally, it is the so now first, so three here, and then point n and is none. So left is none, and then right is none. And then the combined left alone none but basically. So this is three and then now we're going to root and then next is the right side. So, it's the same as and then seven and the finance part doesn't make sense. Mechanical Llama: Okay, so that you just walked through the first test case right? 537? Kind Dragon: Yes, that's going to lead to or from this one. So for us this long. So, here we cannot do not use the root. So I think their first order is not good. Cause the we need to build a tree, we need to I think because that we needed to make the root first right. I think the we needed to change the node first, does that make sense? If not less than like two steps below her equation in this case, check. So now we can output then go to the left. And then the map is known how to elicit anything. So not just return. Okay. I don't think so. And then next to is the right side. Does it make sense? So now let's see if this one and index. index. So for the five, okay, bye peace good for. So indeed. And then by then first we have here five including decks three, left on the left and then go to that is to say that again, then now we are here, make another one, then now is the right side to side effects, and that's same with that all okay. Yep. Okay, thank you. Mechanical Llama: Yeah, I just want to ask you, why did you decide to switch from pre order to sorry, from in order to pre order? Kind Dragon: The reason is the server needs to restore. As we discussed, I would like to use the DFS and to build a DFS, I think we need to make the tree node the root node parsed first. To get root node the first we have no choice to use the pre order. Because they know fully what likely. Yeah, back for maybe we have two choice for the order. And in this case, I think you know, maybe we cannot use data. Because if we use in order, some of the data structure will be hard to compute. So we needed to use pre and post order. So at the time, I thought, Okay, let me choose first for that. Yeah, so this decision is not good. And I changed it to pre order. Mechanical Llama: Okay, so I'm going to say post order. Actually, I think that's what you're right. That's what you did before. Right. So I guess the question is, maybe why did you decide to switch from postorder to pre orders? Kind Dragon: I go and I make the root go first. Make this. I think that this one is that to the stag, I would like to make the clean code, easy to read. A little bit complex, you know? Yeah. Find the root node first. Yeah. Mechanical Llama: Yeah, exactly. Okay, that makes sense. Cool. Cool. Yeah, this looks great. So normally, this question does take 45 minutes, but I think you finished it faster than I normally people finishes. That's great. Kind Dragon: Do we have time for another question? Mechanical Llama: Yeah. So the next question is basically we have a list of integers, so I'll just write out. So we have a list of integers, and we have some target value. So let's say the target value here is maybe five. And then given these two inputs, we want to return true. If there's any continuous sequence that adds up to this target value. So in this case, four plus minus four plus five right adds up to five. So we return true. I can give you another example. Maybe a counter example. Yeah, so another example here, might be six right, so one plus five adds up to six, but they're not next to each other. So this would actually actually be false. And I don't think there's any other continuous sequence in here. That adds up to six, six. I could be wrong. I have to check but yeah, okay. Kind Dragon: Cool. Okay, thanks for the question. And then I have returned from the question to let's say, if a case is minus four, to use minus, right, in this case, can I return the true because the item is only one? Mechanical Llama: Yes. Oh, that's a good question. Yeah. So you can return true if there's even if it's only one. Kind Dragon: Length of the substring is that no matter right? Yeah. Okay, I have a question. What is the length? Mechanical Llama: Um, so you can assume they're just like any integer basically. Okay, cool. So then me Oh, you're asking about the length of the array so the length of the array can fit in memory. Kind Dragon: Okay, cool. Okay. Then zero, right. Okay, cool. So the range of items you don't so integer... Mechanical Llama: Sorry, can you repeat that? Kind Dragon: Okay, we didn't even know what these the main job got item. Item open nodes. Can I say this is a node. Mechanical Llama: Oh, yeah, so numbers can be any integer like negative or positive? Okay, cool. So yeah, this is 32 bit integers thank you for the example okay. Kind Dragon: I'm going to use the are you gonna click... Then if the sum up of all is the same as k, I return it true otherwise I will return false. But it is created because we're gonna use through PCs okay. Which one is good? I'm not sure maybe we can consider a map. Maybe we are so considered mature maybe a pointer. Coincidentally, it is not make sense and pass the it do maybes thing. Okay. Okay, I think that this one is not bad map. So shall we start with the the map? The hash table project first. Mechanical Llama: Yeah, that sounds good. Kind Dragon: Okay, cool. Awesome. So, my target time complexity will be linear but okay. Not yet because now I have no idea yet so... Okay, so first we want to start from here and then two is so maybe none is different does not have negative maybe we can use it to solve it but maybe are a little bit tricky part because we needed to take care of the negative, the saw be able to do that. Okay, let's use the current sum... two three and five. Okay cool. So in this type one four and then maybe we need to find two range... Okay, can you give me a hint? Mechanical Llama: No, no, I think you're on the right track actually with this map. So let's see how to think about this problem. So we're looking for the some eight here, right, which what are the numbers add up to eight? five and three, right. Is there anything else? I'm just checking? I don't think so. Right? Kind Dragon: Yeah, it's just five in three, eight and then this, right. Nine and negative one in five be persistent. You'd have to eight. Mechanical Llama: Three plus five is eight. So yeah, so actually, this was we have signed this one before we find both of them work. Yeah. Okay. Um, yeah. So. So actually, let's think about that. Don't know if I would call this a simple example. But it might help you see the solution. So let's say we had you know, two 1k equals, let's say seven, right. So that one is straightforward because of submission. Two plus one plus four is beginning of the array. We get to seven If we had k equals five right how would we get to five? Kind Dragon: That is that we can get to here yeah. Mechanical Llama: Exactly and then what do we need to do with like two in order to get to five? Kind Dragon: So I'm going to try to use curr sum here is looking for looking for the 2x 5x Mechanical Llama: So what is x in this case? Kind Dragon: X is... curr sum minus k. Yeah. Pretty much to do so. Wow. Okay. Okay. Should you type into the code? So first and we have differing views. No need to index change it for you put up with the example 1234 are we looking for one full file? This is two three, this is seven and then we looking for trees here. Yes. So you're gonna return true. Okay, let me make some... Okay, so now we're going to go one and three so is looking for pretty pretty is here. Oh okay sorry I think the time is up oh. Mechanical Llama: Yeah that's okay. Kind Dragon: Thank you let me check that this goes you know we have time limits so we added to take care of the corner case but it is not so one minus two ways. 11234 it's easy to find it. So in this case we cannot find it this one right okay let me again for you for five and 5 4 4 8 8. Okay, it is minus one is four is three. We must find that The return is, right. Mechanical Llama: So, eight minus five should get you to three, right? Kind Dragon: Yes, of course. So minus key three. Ah, yeah, definitely. Cool. Yeah, I think Yeah. Yeah. So I do. Mechanical Llama: What if k was equal to five? Kind Dragon: Okay, in this case, some... Yes. That is very important. Yeah, exactly. I think that was according to K here. That is what I was looking for. I couldn't. Mechanical Llama: Yeah, no, great. Yeah, I can go over the feedback I had quickly if that's helpful for you. Kind Dragon: Awesome. Mechanical Llama: Cool. Yeah. So overall, I was pretty impressed actually, with how you did like the first problem you solved really quickly. Normally, that takes up like the full 45 minutes, but you solve it pretty fast. And then the second problem as well, like, you solved it, you know, even though like you hadn't seen this before, right. And it's kind of a tricky problem. And I think the only thing that you missed was like, Okay, yeah. And, like feeding a hit, but that's okay. I think like, even with the honts, like you didn't need that much help for me. Like once I showed you an example. You figured it That sounds good. Yeah. Let me see what other feedback I had just high level. Oh, yeah, I one thing I really liked actually, is how you wrote out the like, constraints, the examples input output, like approach, like it just kept everything very organized. I really like that. And the test cases like so that was really good. Definitely keep doing that. Yeah, one thing I would suggest is that, I think here, when you finish store and restore, you kind of started diving into writing test cases. So it's good to write test cases, for sure. But maybe like, once you're done writing the code, just like kind of give your interviewer a heads up that, hey, I'm done right now. I'm going to test it. And then they might ask you to explain like, you know, like how the implementation works. I guess you already explained what you were doing right at the beginning, but... Kind Dragon: You may need to it is good to pass the compiler, right? Mechanical Llama: Not not necessarily what the compiler so I'm not sure which company you're interviewing, I think you think you're interviewing at
Python. Mechanical Llama: Right. Yeah. So I think the return type could have actually been way off still. Because we also return nine values, right? Kind Dragon: Yeah. So no, no, I saw a optional, right. Yeah. So I think that this one is, I'm not sure. Because getting this one is the acceptable, right. Even that is on us dailies team. Kind Dragon: I think the type checker might complain because. Oh, I see. Yeah. So I think the types have actually been fixed. But that was my fault. Because Yeah, okay, cool. Yeah, but yeah. I never use
Pythonfor the developing because I just use it for leetcode, I have no information about... Oh, okay. This is a little bit why I'm asking you. Mechanical Llama: Yeah, okay. Yeah. Okay. Yeah, so only minor thing there. Yeah. And then I again on this problem, too. I really liked how you wrote the test cases and corner cases. And just like the organization that was really good. Yeah. That's pretty much all the feedback I had actually. Kind Dragon: Okay, cool. Oh, I think that that is really great feedback. Okay, thanks. Okay. Let me give you my feedback. Okay, if it goes to you, yeah, you kept to me. Okay. So, okay. Before that, that English is my second language. My English is improving. So, if you're hard to understand something, please let me know. Okay, okay. Okay. So, overall, you really did a great job. So you're used to quite, how can I say the respect? Actually, the really tall view at the faang, they did not just copy and paste to try to drawing something writing something right. So it is really cool. When I do something, you try to keep with me some direct feedback. Such as, wow, you asked this question. Line seven. That is really great. Those kinds of things. I really easy to follow your, your How can I say your direction? That is also really great. So okay, yeah, thank you. And then so second is to use you checked my detailing. So that is really great to hear. Mechanical Llama: So I think I can repeat the last one. I didn't hear it. Kind Dragon: Okay, last that last piece. You You checked my code. Okay. So because that this kind of the thing is that very hard to a... very easy to mistake if you did not concentrate. Me. So they may you literally tried to concentrate me for interviewee. So those kinds of things are really great to me, because I need you to feeling that was this. This is ready to have me so that that feeling is really great to me. So appreciate it. So yeah. Mechanical Llama: Thank you so much. It was really nice to meet you. And I wish you all the best. If you don't mind, I'm sharing my YouTube channel. Oh, line 148. This is way too much. Kind Dragon: Okay. definitely take a look at it and subscribe. Mechanical Llama: If you have some time, and if you don't mind. I've tried to connect you. Kind Dragon: Oh, absolutely. I'll share my contact information. Mechanical Llama: Yeah, so I'm not sure that you are sort of preparing for an interview. So okay, may I ask you that? Are you preparing? Where are you in the interview processing now? Kind Dragon: So I'm actually not preparing for an interview right now. But I've kind of been considering it. So it's an I also have interviewed a lot of people at my company but not outside. So... When I saw this platform, basically I was thinking about just practicing my interview skills, even though I'm not like directly interviewing anywhere right now. Mechanical Llama: Oh, then may I ask you why you are trying to emphasize the interview? Kind Dragon: Why I'm interviewing other people? Yeah. So I think there's some, I think for every two interviews you do, right, you get one free interview. So I think it's, for me, it's a good way to get more mock interviews for myself. But I also learn a lot by interviewing other people, right? So, for example, I really liked how, you know, you wrote out your examples and the approaches, right. So sometimes, when I interview other people, I also get any ideas for how I should interview myself. Kind Dragon: Oh, awesome. Yeah. Okay. Mechanical Llama: I'm going to say if you haven't tried interviewing other people before, you definitely should, because I definitely learned a lot from interviewing people as well. Kind Dragon: Actually, I interview other people from around one and half years before to interview more than 400 people. During interview, one of the great thing is that I make the yearly could meet another Interviewee. Yes. Yeah. So many of them are already got Java from the Fang. So when I do the
Googler. report me, they gave me their report. And some of them are my interview friends. So the if you look at so if you want to try too long to study, and then I would like to recommend you please study with the awesome people. Because Yeah, you use it to find in
interviewing.io. So some of people is very extraordinary ability. So if you want to do the mock interview with them, you are better. So same level with them. So that is really cool. Mechanical Llama: Yeah, thank you for that. Yeah. Kind Dragon: So if you want to do a mock interview with me, please let me know. So after, if I'm not after got the job offer from