# Python Interview with a Meta engineer #### Watch someone solve the odd even linked list problem in an interview with a Meta engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays. Odd Even Linked List: Python Interview with a Meta Engineer - YouTube ### Interview Summary **Problem type** Odd Even Linked List **Interview question** 1) Given the head of a singly linked list, group all the nodes with odd indices together, followed by the nodes with even indices, and return the reordered list. The first node is considered odd, and the second node is even, and so on. 2) Given the `root` of a binary tree, determine if it is a valid binary search tree (BST). ``` 3 / \ 1 5 / \ 2 7 ``` ### Interview Feedback **Feedback about Crimson Turtle (the interviewee)** **Advance this person to the next round?** Yes **How were their technical skills?** 3/4 **How was their problem solving ability?** 3/4 **What about their communication ability?** 3/4 > Overall easily clears screening round. For onsite, unless you get benefit of doubt it could be a no-hire. #### Communication **Perf: Strong** - (+) created a testcase to discuss - (+) didn't jump to coding - (+) language is clear - (+) used comment space to explain the solution #### Problem solving skills **Overall: Solid** **q1** **Perf: Strong** - (+) figured out acceptable solution without any hints - (+) knows about linked lists - (+) shared time & space complexity himself proactively - (+) quick at finding the solution **q2** **Perf: Solid** - (+) knew about BST definition - (-) assuming it's integers, always worth asking if it's integers or float - (+) had to prod but was able to talk about time & space complexity correctly #### Coding skills **Overall: Solid** **q1** **Perf: Moderate/Solid** - (=) coding speed is avg - (+) edge cases taken care of - (+) readability is good -- good var names, comments in code, method name is appropriate - (+) was able to correct logical bug in his code after the prodding and fixed the code without needing hint for actual solution - (-) logical bug : assumed head.next is at same place still...which it isn't. tried minor nudges but didn't work. had to spoon-feed issue again. **q2** **Perf: Solid/Strong** - (+) took care of edge cases - (+) code readability is good generally - (+) code is correct - (=) avg coding speed #### Verification skills **Overall: Moderate** **q1** **Perf: Moderate** - (+) good line by line verification - (-) unable to catch his own mistakes and had to point it out two times...and had to exactly pinpoint the mistakes - (+) created test cases **q2** **Perf: Moderate** - (-) not a proper line by line verification --- antipattern, don't do this. had to prod you for this. and then you processed 5 before processing 2 or 7 which isn't line by line truly. act as an interpreter, don't use your brain during verification. - (+) good way of visualizing the states in comment. - (-/+) no new test cases created proactively, had to prod TC to do so. Created new test cases. - (=) no mistakes to correct ### Interview Transcript **Quantum Wolf:** All right, cool. Awesome. **Crimson Turtle:** Sure, sure, sure. Yeah, so basically like last year around, like, yeah, last year, maybe around like September, I did interviews and then it was like a closeness. So the recruiter actually reached out to me and then she's like, yeah, so like to interview. So I'm in the first interview coming up on the 24th of February. **Quantum Wolf:** Gotcha. Gotcha. **Crimson Turtle:** Yeah, yeah, yeah. **Quantum Wolf:** All right, I understood. Okay, cool. So, meta coding interviews, basically you're going to get 35 to 37 minutes. I'm going to ask you two questions. **Crimson Turtle:** And. **Quantum Wolf:** Essentially you're not allowed to run your code, you are allowed to do a dry run by creating your own test cases. Okay, that's about it. I will spend about 21 minutes after the interview giving you all kinds of feedback and because you're familiar with the platform, you know that the You can obviously listen back to it later on. I will submit every piece of feedback I'll give you in written format as well, so you don't need to necessarily write things down. But that's on you. All right, let's begin. Which language would you like to code in? **Crimson Turtle:** Python. **Quantum Wolf:** All right, that's good. Okay, then let me give you your first question. Are you familiar with LinkList? **Crimson Turtle:** Yes. **Quantum Wolf:** All right, cool. That's your first question. Have a read. Let me know if there's anything that's unclear. Happy to elaborate further. **Crimson Turtle:** Okay. So given the head of a singly linked list, we want nodes, odd indices first, all of them first, and then nodes, even indices after all of the odd indices, and then we are going to return reordered lists. So, we still want a linked list, right? At the end? **Quantum Wolf:** Yep. **Crimson Turtle:** Okay, so first node considered odd with, I guess, with a value of one. Second node is even. Relative order, even odd groups for main as an input. Got it, yeah. We have a linked list with nodes like 12345, and we want all of the odd ones first. So 1356, 2, and then 4. **Quantum Wolf:** Yep. **Crimson Turtle:** Cool. So since the first node is always odd, we can just return the same header. OK. Yeah, so how would we do this? So let's see. So one has to be connected to 3 and then 3 has to be connected to 5 and then 5 has to be connected to 2 and then 2 has to be connected to 4. **Quantum Wolf:** Yep. **Crimson Turtle:** Okay, so I think we can do this by first having a pointer for the even and the odd. For example, the odd will be here and the even will be here. Then we'll connect all the odds first. Odd.Next would be odd.Next.Next. **Quantum Wolf:** What would be the... Yes, sorry, go on. **Crimson Turtle:** Oh, sorry. Yeah, so the time complexity in this case would be O of n. since we just iterate each of the nodes once and the space in this case would be constant, so we're not using anything. **Quantum Wolf:** Okay, sounds good. I think that sounds good to me. Let's see the code for this. **Crimson Turtle:** Got it, got it. So define my function, so reorder. Which takes in the head. So first we're going to define our left pointers. So left is qual to head, and then we're going to have the right is qual to head.next. We also have the edge case where we just have a single node. So if head.next is none, then we can just return the head as we have finished. We have the head and we have the head.next. First wire left odds, Odd and then even. So why are the odds? What is the condition for wiring the odds? If odd.next exists and odd.next exists, odd.next is the next even element. If odd.next.next is the subsequent odd element. If this exists, While this exists, we want to continue, so both have to be true. Let's wire it, so odd.next is qual to odd.next.next, and then we move the odd.next, odd2, next is qual to odd.next.next, and then odd. **Quantum Wolf:** Let's see here. **Crimson Turtle:** O is equal to next dot next. That goes here. That's the 1 gets pointed to 3. And. Then odd moves up here. And then even.next.next also gets moved up. So even goes to here and we have two going to two going to four. We have 2.24 and then so the second one exists so this three gets pointed to five. Odd goes to five. And then even.next goes to null so we get none and then even goes to none. So at this point, we have this, so 135, and so we can say the current position of the odd, which is at the last, gets pointed to the first even, which is set. Yep, so head is at the one. So we want to point the final value of odd, to the first even, which is head on next, so which is two. **Quantum Wolf:** Okay, do you want to do any other test cases? **Crimson Turtle:** Yeah, so if we just have a single node, that's just a base case. So if we just have one head on next would be none and then we can just simply return this and we would be finished. **Quantum Wolf:** Anything else that comes to mind? **Crimson Turtle:** Yeah, so I'll just do, let's see. So right now we have an odd number of nodes, so another one would be even. So for example, if we have 1, 2, 3, 4, so we should be odd. Odd and even. So second one up from odd exists. So in this case, one goes to three and odd moves up and then even moves up. **Quantum Wolf:** How is your head.next not changing? **Crimson Turtle:** Oh yes, the headless next should be now RT3. Yeah, so it just seems that we need to save the head of the even ones, which is just, we can just say even head, is qual to head.next, and we can just save that node here. **Quantum Wolf:** Okay, I think let's move on to the second question. **Crimson Turtle:** Sure, sure. **Quantum Wolf:** All right, cool. Second question is around binary trees. Again, have a look. And just so that it's everybody easy, and let me just draw one of the binary trees for you. **Crimson Turtle:** Sure, sure. There you go. Okay. Yeah, so. For this problem, I think it's best to first define what a binary search tree is. So ST is so for every single node, it's left child should have a value that's strictly less and then and the right child should have a value that's strictly greater. So for five, the value should be smaller than five, but of course greater than three. And then for seven, it should be greater than five strictly. So essentially the problem asks us to validate if it's BST. So we need to ensure that this condition holds for every single node recursively. That's the problem. So essentially what we need to do is every time we go down a node, we need to define the valid space of numbers that's allowed according to the definition of BST. So for three, we allow the elements everything less than three. So we can say have the range going into the left child as negative infinity to node minus 1 going into this one. And if it's in that range, yes it is because the upper bound is 2, it's valid. So it returns true for the left child. We go to the right child. That's looking for elements 1, 3 plus 1, which is 4 all the way to infinity. And that again fits the condition. So 4 to infinity going down to the left child. Now it should be less than 5, so it should be 2 to 5, 2 to 4. And that's, again, that's valid. And then going into the 5, the lower bound now is 5, so it should be 6 and up. So this is also valid. So we can solve it in this fashion. **Quantum Wolf:** OK, what would be the answer for the given tree? **Crimson Turtle:** So the given tree would be given tree would be false because the lower bound here is 3 and then the upper bound is 5, so this node would make it fail. Otherwise, if it was like this, it would be fine. **Quantum Wolf:** OK, sounds good. Let's see the code for this. **Crimson Turtle:** Okay. Stack docs. So let's see. So this is the outer problem. We're going to define a helper function which takes in a node and it has a left and a right. We'll just say low and high. So if not node, then we can return true since we expect that a single node is a valid BST. And then if in the recursive case, so check if node value is in between low and high. **Quantum Wolf:** True. **Crimson Turtle:** Okay, so we have the answer for this node and then we can. So if this node for this node. If. So node is in range and. Also. We need the answer from the children. So helper.node.left but when we go into the node.left, the low is the same and then the high should be node.val minus 1. And then we have another helper function called to the right child. So node.right. And then for node.write, every value should be strictly greater. So the lower balance should be node.val plus 1. And then the upper balance should just be the same. **Quantum Wolf:** Yeah, let's see the code. **Crimson Turtle:** Okay. **Quantum Wolf:** Can we do Word Drive and some tests here? **Crimson Turtle:** Sure, sure, yeah, so I'm just gonna do the test case at the bottom. Okay. So our state variables are node to indicate the current node that we're traversing, and then we also have a state variable low and high. So I think in this case, I'll just list the state variables beside each of the nodes in the tree. So the three, which is the head, is being called on negative infinity, And then, so it's going to be, so the three node here is going to be in range, so the ends here will be true. And then we call the left. So the left is being called on the same negative end and the node.val minus 1, which is going to be 2. So again, this one is in range and then we're going to call the left child. So the left child is going to be called on, no dot left is being called on the same low and no dot dot minus one, which is going to be So -inf and node.val-1 is 0, so in this case 2 would be false. And then the right child would be the node.val+1 which is going to be 2 and then the high bound is going to be. **Quantum Wolf:** Got it. Do you want to try any other test cases? **Crimson Turtle:** Yeah, the only test cases to try will be if you only have a skewed binary tree. So if we have something like this. So, K-SOR for example, the answer is true, so something like this. And we skew it a little bit. So, for example, three. So left is qual to minus infinity, infinity, so and is qual to true. **Quantum Wolf:** Yeah, it's always do it like that. Yeah, just always try to be proactive. That's often in fact, although for coding leveling doesn't matter, but for all other interviews except for behavioral, any system design interviews, any other kinds of interviews, often a big difference between E4, E5 or l4s and l5s is actually to how proactive are they, how much are they leading the interview themselves versus requiring the interviewer to help them or to nudge them or to have a back and forth with them. **Crimson Turtle:** Right. **Quantum Wolf:** So the more you lead, the better you seem anyway as a candidate. So that'll always be better regardless of which interviewer it is except for behavioral. #### We know exactly what to do and say to get the company, title, and salary you want. Interview prep and job hunting are chaos and pain. We can help. Really.