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

Python Interview with a Meta engineer

Watch someone solve the minimum depth of binary tree 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.

Interview Summary

Problem type

Minimum Depth of Binary Tree

Interview question

1) Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Note: A leaf is a node with no children. 2) Given the root of a binary tree, the depth of each node is the shortest distance to the root. Return the smallest subtree such that it contains all the deepest nodes in the original tree. A node is called the deepest if it has the largest depth possible among any node in the entire tree. The subtree of a node is a tree consisting of that node, plus the set of all descendants of that node.

Interview Feedback

Feedback about Diamond Pterodactyl (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

Strengths & what went well: - Able to psuedocode multiple approaches and determine optimal solutions - Understood OOP (Object Oriented Programming) principles in their language of choice (Python3) - Knows fundamental Binary Tree / Graph based algorithmic approaches / solutions (BFS / DFS) and when to use which one. Areas for improvement: - Practice more recursive approach based algorithms, recursion can make straightforward logic get messy. Define your base case in all recursive approach based problems / solutions. Advice for future interviews: - For Meta, be aware of the time you have left and make your intros concise to leave you more time for solving potentially 2 questions.

Feedback about Clandestine Snake (the interviewer)

Would you want to work with this person?

Yes

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)?

3/4

Great question and build up of questions. Good proctoring of interview to be similar to that of Meta. I kind of got lost with the hints to the problem. Not sure if that's because I was too constrained in thinking about LCA for two nodes.

Interview Transcript

Diamond Pterodactyl: I have a interview with Meta tomorrow. It's the initial phone screen. The format they mentioned was you basically solve two roughly leetcode mediums in 45 minutes. So I just kind of want to benchmark against that to see or even just get used to that type of format. I have about seven years of software engineering experience, mostly in back end infrastructure. So. Yeah. Is there anything else that you need to know?

Clandestine Snake: No, I think that's pretty good. I'm glad you mentioned the Meta things, so I'll try to give you something relevant. So why don't we do this? Let's do this. I'm gonna paste this question. I want to see if you have seen this before.

Diamond Pterodactyl: Okay.

Clandestine Snake: A little tougher, but that's fine. I'm gonna go ahead and comment this out and then here we go.

Diamond Pterodactyl: Given the root of this, I'm going to read out. I'm going to read it quietly. The depth of each node is the shortest distance return us return the smallest subtree such that it contains all the deepest nodes in the. Okay, let's call the deepest. If it has the. Okay. I have not seen this problem before, so I'm happy to solve it. And great.

Clandestine Snake: Before we solve this though, it's great that you didn't see this before. So I'm actually going to do this real quick because I'M going to follow meta's format. I'm going to give you another question.

Diamond Pterodactyl: While.

Clandestine Snake: We get to that. That's going to be the follow up.

Diamond Pterodactyl: So here you go. Okay. Given the minority, find its minimum depth. The depth is the from the root down to the nearest leaf node. A leaf node is no children. Okay, I'm ready to start talking and working through this problem. If this is the format, which I think it is. So to me this is a pretty. Feels like a pretty straightforward problem either when I'm thinking about trees, I can think about dfs. Dfs, we're looking for the minimum depth number of nodes along the shortest path from the root to the two little beaks node. So if I have a tree that is like this, sorry for the formatting, the minimum depth. Okay, so in this case the minimum depth would be two, right? Because there's three and two. And if I add this, if I add one more, this would be, this would be. The minimum depth would be three. Is that, is that understanding correct?

Clandestine Snake: Yep.

Diamond Pterodactyl: Cool. Finding the minimum depth. I guess one approach is to basically find. One approach is to find the depth art, traverse the entire tree keeping track of depth and you know, have a separate variable keeping track of minimum, minimum, minimum depth. So what that would look like is let's do five. So if I have this tree, I can just do bfs dfs. I look at the 3min def. If we initialize it to something really high or something and I start with the three, I look at the one, I look at the two and as I'm going down, I'm incrementing, I'm keeping track of the depth and when I see three, two is a leaf node, I will compare it to the current minimum depth and see if it's either none or smaller. In this case it's none. So it's going to be three. I go back and I go back to four and I see that this is four. Sorry. I see that the depth is still three, so nothing changes. I go to my right subtree and I go down here, I see the depth is two and I convert this to two. And then when I fully traverse a tree, I explored every depth at each leaf node and therefore I'm able to determine the, the minimum depth.

Clandestine Snake: So that approach that you just mentioned, which one is that? Is that BFS or dfs?

Diamond Pterodactyl: Oh, when I walked through it, I was using dfs. So I start, go down, go down. And then. So a DFS approach would be. So one of the things I was thinking about while I was walking through this. Is. Is there something we can do that? Is there something special about the minimum versus maximum? Like, if we can traverse the tree such that we find the minimum first, then the first minimum, the first leaf node we find could be the answer and we won't have to traverse the tree. Whereas maximum, you know, you. For example, if I see five here and I know that the left side is not a leaf leaf node, but the right side is, then I kind of know that, like, I don't have to keep going because the further I go down, the answer is definitely going to be longer. So that makes me more inclined to do a BFS approach. Bfs? Traverse. Traverse each level. If there is a leaf node, we know that it is the minimum depth because we define the depth as the shortest path from the root down to the nearest leaf node. So nearest leaf node can be explored via bfs. Yeah, so I feel like the worst case here is still equivalent to the dfs, but on average case, I, you know, especially for, you know, pretty lopsided unbalanced trees, I can expect this to be more performant than the DFS approach. Do you have any questions so far?

Clandestine Snake: No, I think that those are. Two approaches are both solid, but I do think DFS might be slightly better in some cases.

Diamond Pterodactyl: That's how I feel on the average case. Especially when the trees are not well balanced, basically. Yeah. Cool. Is it okay if I code this up or is there any other questions you may have?

Clandestine Snake: Please, please. Yeah.

Diamond Pterodactyl: Okay, I'm going to start with writing the node or should I write the spoiler play? I know with meta they mentioned they don't let you run the code. So do you think I should write the boilerplate or should I just skip it?

Clandestine Snake: You should write it. Let's adhere to OOP practices, right?

Diamond Pterodactyl: Adhere to what?

Clandestine Snake: Practice Object Oriented Programming. Right.

Diamond Pterodactyl: Oh, yeah. Okay. And so with bfs, I usually do it by. I usually do it by creating it. I usually traverse it by using a queue. So I'm going to create a dec. I hear that's how you pronounce it, even though it stands for double entity queue. And I should also probably check for the case in which root is not exists, in which case I will probably return zero or some predefined thing. So while Q going to iterate and pop off, the node is equal to Q pop left. And if the node is a leaf node, so if not left, end node, not node, right is a leaf node, in which case we can return our depth, which we haven't instantiated and then otherwise we will queue our. Sorry, I made a mistake here. I need to traverse level by level. So I'm going to write A for loop here which traverses through each level. So this will be the first level. And then so and if not, then if no left append no left. And then if Q node right, Q append no right. And then for each time we increase the depth by one. I feel like there's a risk I have a off by one error here with the depth. So I'm just gonna. And I don't think this will end. I don't think this while loop will end without reaching some kind of leaf node. So I'm just gonna raise an exception just in case. Except. Sorry. Assumption file. Cool. Let's see here. Okay, I'm going to run through this with the example that we talked about by hand. Super ugly. This is what it looks like. And this is the write down. So my queue starts off with the 3 and my depth is equal to 1. So for n in length Q, I pop this off and this condition line 46 is not true. So I don't return depth. I see I have a left and right node, one and five. So once I finish that, my depth will become two. And now I pop off the one. The one here is not a leaf node. It has two children. So I add two. I add two and four to my cube because they both exist. And then I go to my second index in this array, which is the five. I see five has no children. And I return depth, which is two and two matches what I expect here, which I'm happy about. And we can talk about potentially edge cases, but is there any questions you have so far?

Clandestine Snake: Nope. I think you solved it and you definitely walked through it. This is the perfect format. So this is what meta will do. They're not going to let you run.

Diamond Pterodactyl: The code.

Clandestine Snake: At least since I remember. But you talked about everything. You gave two different approaches. You went with more optimal one. I would only say what is the time and space complexity of the BFS approach?

Diamond Pterodactyl: The BFS approach on average performs better because for trees that can be imbalanced, it will basically return early. It'll find the first leaf node. But the worst case is still you have to traverse through every node. And this would happen in the case of a perfectly balanced. Perfectly balanced tree. So which is the same as the dfs. So which is O of N with N the number of nodes.

Clandestine Snake: Right. What about the space complexity?

Diamond Pterodactyl: Space complexity is also O of N because we're keeping track of the queue here. So the Q could basically in Q, you know, every. If it's a fully formed tree, this could be up to, you know, some constant of or some portion of the total number of nodes.

Clandestine Snake: Awesome. Okay, well, here's the follow up question. Question 2.

Diamond Pterodactyl: The definition node is for attention to the depth of each node. Okay. That's just what we know so far. The deepest. So instead of the minimum, it's deepest, so it's maximum. The root node is called the deepest if it has the largest a subtree. The subtree of a node of a subtree of a node is a tree consisting of that node plus all descendants and end of. Okay, there's a lot to keep track of, so I find it most helpful to just work through some examples. So just going to copy what we have before we built something familiar with that. So the input input is a root, the output is the node, the smallest subtree. So it's the node of the. It's a node of the tree that contains all deepest nodes. Okay, so let's look at this example here. The deepest nodes here are 2 and 4. We can figure that out if we just did one of the DFS BFS approach by keeping track of the depth, unlike the. I'm just thinking out loud here. If I know for minimum trees, minimum depth, we have the optimization traversing in depth sorted order. And I'm wondering if maximum depth has a similar thing. That's just something I'm going to, I'm going to table for now because I'd rather get the correct solution first. So at least for the example we have 2 and 4 being the deepest nodes. So once we have the deepest nodes, it contains all the deepest nodes in the original tree. So deepest nodes is maximum length or maximum depth of nodes and all the depth of all depth of nodes are the same. So in this case, this deepest node in this tree at 2, 4, what we would want to return is the one because the one contains both of them. If we find, if we expand this tree such that the four has a right child, then this example would become six and then what would the answer here be? It would be. Would it be six? Is that how I'm understanding? Because it's the only. It's the only. It's the deepest node.

Clandestine Snake: Well, all the deepest nodes would be. I think in this case it might be four and six, right?

Diamond Pterodactyl: Oh, six is a right child of four, so. Right.

Clandestine Snake: And because six is the deepest node and it's not, it needs to have a parent.

Diamond Pterodactyl: Right?

Clandestine Snake: Because we're looking for the tree.

Diamond Pterodactyl: Oh, right. We're not. We're not considering. We're not considering six to be a parent of itself. Right. At least not a subtree of itself. Basically. Yeah. So. Okay, okay, okay. That makes sense too.

Clandestine Snake: Wait, you wouldn't return four, you would return four and six. Right. Because trying to return the smallest subtree.

Diamond Pterodactyl: Return the smallest subtree. I assume the output is a pointer to the node of the subtree. So it would be the four.

Clandestine Snake: Technically, yes. Let's assume you're right. It could be a pointer. I just gotten so used to returning in an array format, but it could be a pointer. Totally fine. Yeah.

Diamond Pterodactyl: Okay. Okay. Yeah, let's do that. The array thing, I'm not as used to. Yeah, let's just do that. We can maybe workshop this later if we decide.

Clandestine Snake: Don't worry about it. We've defined the expected output. This is fine.

Diamond Pterodactyl: Yeah.

Clandestine Snake: As long as you. I think we're fine.

Diamond Pterodactyl: Okay, that's fair. So I think I understood the problem. Let's just do one more. If the seven here of the right and eight is the right, then the subtree would be. We would return three. Is that correct? This would be eight.

Clandestine Snake: Technically, this is where things get a bit hairy. Right? So we wouldn't return just three. We'd have to return 3, 1, 4, 6 and 3, 5, 7, 8. And we wouldn't return the two as part of that. Right. So as another follow up to this, instead of just returning the root, try to print out the. Pick your choice. I'd say print out the inorder, traverse like array of the root of the smallest subtree. Well, even then, that would include the two.

Diamond Pterodactyl: Sorry, you mentioned two. Oh, there's two here. Yeah.

Clandestine Snake: I'm trying to make this bearable because we have limited time, but the trick is you'd have to return. Actually, no, it's fine. Just return the root. Yeah, it's fine.

Diamond Pterodactyl: Okay. Yeah. It feels a little bit trickier to return the path. Okay. I'll think about this afterwards too. But I feel most. Yeah, let's do that. Okay. So to me, I think I understand the problem clearly. There might be other stuff I missing, but let's just talk about approaches. So to me, at least when I walk through the example, it seems like there's two parts. The first part is find the deepest notes and then for the deepest notes, find the. What they call it the lowest common ancestor or lowest common parent. Parent. Ancestor is probably the right word. So to find the deepest node, we traverse the tree. This is kind of from part one DFS the tree, keep track of deepest nodes nodes via a list and. Yeah. And then for deepest nodes for each node, this might be a bit trickier. So if I have six and eight, how do I keep track? How do I find the common parent? I guess I could just traverse for each since they're the same depth. Since they are same depth, traverse each one one parent up at a time and if the parents are all equal, return that parent. I know in the first part we didn't add a. We have left and right but not parent. Is that, is it okay to add a parent or should I try to work the exact same class that we did in part one?

Clandestine Snake: Let's assume that we're not going to be able to have parent, just going to have value left and right on each node, just like we've defined.

Diamond Pterodactyl: Got it. Okay, that's, that's, that's work. Let's try to work with that. So if I can't traverse up that also that means I'd have to, I'd have to find each element on the way down. So that doesn't sound super efficient because the naive approaches for each element, let's see. I guess I would have to do the recursion. Find recurse left and recurs right. And then this recursion function. Recursion function, starting at root function, takes in a node node and returns if all nodes are in subtree. So if not all nodes, some nodes are in substrat. So we can do some casework here. So if left subtree, if the recursion is true and right is false, then we know that the subtree, the answer subtree is on the left side. Because if the right subtree doesn't have any nodes, that means doesn't have any of the deepest nodes. Then we know all the nodes are in the left subtree and therefore we're like the current node is not the answer, it's the left is in the left subtree and vice versa. Symmetrically. If this were reversed, if this right subtree was false, was true and the left subtree was false, then we would have the symmetrical answer. If left subtree equals true and right subtree is equal to true, then we know that we are the answer, the subtree with the deepest nodes. Does that make sense?

Clandestine Snake: Yeah, I think I understand your approach.

Diamond Pterodactyl: Okay. I'm trying to decide if I want to. I'm trying to decide if I want to. I have a good sense that this will lead to a correct solution and I could either walk through it manually to try to get to it or do you feel like we should try to optimize it before we try to try to.

Clandestine Snake: Definitely do not optimize before coming to a solution. Don't prematurely optimize.

Diamond Pterodactyl: Okay. In that case, let's walk through this approach, at least with the English approach, and see if we reach our solution here. So let's start with step one. Find the deepest nodes. So we can do that with dfs. We'll keep track of a list. Deepest nodes deepest or. Next step is equal to 0 or 1. And then deepest nodes is a trick. So then we start with three. Three here is. Sorry, zero. Actually three here is. It's not a leaf node, but we can keep track of the depth equals 0. Next depth equal to 0 or 1 or whatever we can do DFS, it doesn't. Shouldn't matter too much. So 1, let's do pre order 1 and then 2. 2 is a leaf node. Now we're at 3. This max depth is 0. So we do this to 3 and then we set this to 2. Now we go down to the 4. 4 is not a leaf node. 6 is a leaf node. So 6 becomes 6. Is 4 greater than 3 the current depth? Yes, it is. We updated as 4. Since we updated the depth, let's restart the list to B6. Then we go up, blah, blah, blah, 3, 5, 7, 8. 8. Here is depth 4. The max depth is 4. It's equal to the max depth. So we can append the 8.

Clandestine Snake: What if you didn't have the 8 there, you just had the 7?

Diamond Pterodactyl: If you had a 7 here, the depth would reach 3. Sorry, the depth is 3. The max depth is still 4. And since the depth is not greater than the max depth or not greater or equal to the max depth, we don't do anything. So the deepest node would be six.

Clandestine Snake: Okay, but technically trying to think in this case, I guess it shouldn't matter. Yeah, you're right. Because the root would be returned as three in that case. Right? Or actually, no, it would be four. Six. Yeah, yeah, you're right.

Diamond Pterodactyl: That's fine.

Clandestine Snake: I apologize. Just wanted to confirm that edge case.

Diamond Pterodactyl: Oh, no, no worries, no worries. Happy to answer any questions. I'm kind of flying by to see my pants as well. So we'll see if it's actually a good solution. And this would be a very interesting case too, because when I wrote this approach in the first place, I had assumed there'd be more than one deepest node. And I haven't really thought through the case in which there would be two. So let's write a little note here to edge case. Note edge case 1 deepest node. Okay, let's see and let's stick with the, the original one with six and eight and let's look at the, the second part for the devious nodes, find the lowest common ancestor. So for this I'm actually going to do it with the tree structure. So we're going to do the question mark, question mark question. So basically I'm going to try to, I'm going to try to mimic traverse a tree with the calls here. So let's see. So with the calls I'm going to do a pre order call stack. Let's see if that doesn't does that works. So recur. Starting on root node, find deepest node in the subtree. The answer is on find the lowest common ancestor. Recurse left side of root. Some of some. The function is some of the deepest nodes are in the subtree. So if I'm at the two here, I see that it's not the subtree. So this would be a. No, let's do false. And I go down here and this would be. We're not sure. Then we go down further. Is this a deepest node? This is yes. So this would be a true. That means this would be a true. And that means this would be a true. And that means then we go to the right subtree. This is a. I don't know. This is. I don't know. This is A true. Because 8 is the deepest node. That makes this a true. Because one of the subtrees is 0 and this is true. And since both of these are true, we know that three is the is the answer. So we noted somewhere answer is equal to 3 and this will return true as well. So that's kind of how I think about this. Let's work through the edge case of only one deepest node because that's a pretty interesting case. Here we assume that there's, you know, more than one. I'm thinking, the thing I'm thinking is, is one a generalizable edge case or is it strictly an edge case? Is it indicative of a pattern of edge cases or is it just specifically one? And if it were three, then that would be edge case one deepest node. I think it's an edge case.

Clandestine Snake: It's not like a path or anything. I mean.

Diamond Pterodactyl: Yeah, if it's just one, then I'm just thinking that if it's one then I can just try to find its parent and just return that and use a separate logic it doesn't seem.

Clandestine Snake: Because what's. Remember, what's. The ultimate thing this problem is trying to solve is trying to find the lowest common ancestor of all the deepest nodes. If your only deepest node is the six, the only common ancestor of the six is the four. Right?

Diamond Pterodactyl: Right. Yeah. Yeah. I'm trying to rectify it with the approach here, which assumes that some of the nodes are. Because the condition for setting an answer to be true to setting an answer is if there are nodes on one side and those on the other side. But if. If that decision, if that decision boundary, if that decision condition doesn't apply for one, then it's not gonna. It's gonna. It's gonna fail. Does that make sense? So maybe I can account for it by saying that if. If there's only one, if there's a left, or. If there's a left but not a right, or there's a right, not a left, then you're are the. You are the answer. So, okay, I think.

Clandestine Snake: I think the issue is with. Well, I won't. Do you need a hint? I can try to give you a hint.

Diamond Pterodactyl: Yeah, sure. I feel like I'm. Yeah.

Clandestine Snake: So the issue, I think, is in the case where you have, let's say, the 6 and the 8. Right. Those two are both of the same max depth. Right. I think, yeah. There has to be definitive max depth. And then you disregard anything else that isn't of that max depth value in terms of the deepest nodes, if that makes sense. And then that way you can focus on the lca.

Diamond Pterodactyl: Yeah, that's definitely very helpful. I'm just trying to think of the implication of the. So basically you're saying we know the depth of the deepest nodes, it's going to be four. So if we see a node that is three, then we can ignore it. But how is that going to help me? I guess to me the confusion is like, how is that going to help me find the. So, like, in the edge case of one deepest node, then you're saying, like, just find the. Find the. Find the node with depth minus one. Basically.

Clandestine Snake: Basically. Like if you had a parent property, you would basically return its parent.

Diamond Pterodactyl: Right.

Clandestine Snake: But since we don't kind of craft your algorithm in a way around it, which you're trying to do with recursion.

Diamond Pterodactyl: Yeah, yeah, exactly. That makes sense. Is equal to deepest node. Yeah, Maybe I'm getting ahead of myself here because I'm trying to think of the case where there are three deepest nodes.

Clandestine Snake: There could be infinite number of deepest nodes depending on how tall the tree's height is. Right. I mean, technically you can have a complete binary tree of height, like, you know, 100. And then at level 100, you have all the leaf nodes.

Diamond Pterodactyl: Right.

Clandestine Snake: And they're.

Diamond Pterodactyl: Yeah, yeah, yeah. I'm. I'm deciding whether my recursion is sufficiently. Like, I've covered. I can cover one deepest node with my approach. I don't know if I can cover three. I haven't really worked. Worked it out because when I wrote this approach, I was in my head, I was only thinking about really two deepest notes, which is not, you know, not. Not the smartest thing to do. So, yeah, I'm just thinking if I should try to find a different approach or should I try to work with this. Work this recursion approach and try to make it work for three plus deepest notes, like more than. More than two. Because I know for two it would work. So, yeah, I think it. Yeah, I think it makes sense, but I'm not. Yeah, Maybe we can walk through the example here. Let's do nine. Say nine is the right subtree of the right child of four. So we'll do.

Clandestine Snake: And by the way, we have 10 minutes.

Diamond Pterodactyl: Okay, that's. Thanks for the note. Cool. So what would this look like? This would be this. This. This true. This would be a true. This would be. Yeah, I don't think this approach works because if I go to the right subtree, the 6 would be a true, and then it would. It would. Their approach would say this is a true, and this is the answer. Because if my condition is that the answer is if the left and right subtrees recursion calls are both true, then you are the answer. And that doesn't seem right to me. We could keep track of a count of max nodescene and we can increment as we traverse through it, but that seems prone to be buggy as well. So let me give you a little bit.

Clandestine Snake: Why don't you calculate the max depth before even like tracking the leaf nodes? So you know what I mean? Get the max depth in a separate function and then use that max step as you're trying to find the subtree. And then that find subtree would have your recursive logic, if that makes sense.

Diamond Pterodactyl: Can you repeat that? I kind of. You said, I know. Max step. Find the maxdef.

Clandestine Snake: Yeah, that should be your first step, and that should be a function in and of itself. And then secondly, you want to have a separate function that actually finds a subtree and then pass in your max depth as a parameter. Of that function, if that makes sense. And you could also track the current depth, so that way you never go past the max depth. If you ever reach the maximum depth at the current depth in your recursion, you just return the current node, if that makes sense.

Diamond Pterodactyl: Return the current node. Maybe you can help me understand with the example here, because I know how to track the max depth. Right. It would be four at the bottom here. How could four help me reach an answer where I end up at 3, which is not anywhere near the bottom? Is kind of what I'm asking myself.

Clandestine Snake: Is it will pop off the recursion, off the call stack, right? And then eventually it's going to check the left and the right. And if both left and right are true, then you return that current node, the root right. If left exists, then you only return left. If right exists, you only turn right. And this kind of goes for the recursion because you had, the idea was kind of there like you had the logic essentially, but I think you just needed to short circuit with the max depth.

Diamond Pterodactyl: Oh, short circuit.

Clandestine Snake: And just track the current depth. I don't know if this helped you or not. I mean, hopefully the same helped.

Diamond Pterodactyl: Track the current depth. Short circuit the max depth. I'm trying to understand because you can't go deeper than a max depth. So how you can't go deeper than max depth. So if you're tracking a depth, like what would this search, what would this short circuit condition be? Because you can't. Sorry, can you repeat that? I can hear you.

Clandestine Snake: Depth equals max depth. That's your base case, I guess. Then you would return the root that you passed into the recursive function. That's your base case.

Diamond Pterodactyl: Yeah, that makes sense. It would be the same as saying if it's a leaf node, right? I guess not, because.

Clandestine Snake: Exactly. So with the leaf node, you wouldn't return the root, you'd have to return, I guess like none is Python.

Diamond Pterodactyl: Yeah.

Clandestine Snake: Value in recursion.

Diamond Pterodactyl: Right.

Clandestine Snake: And again, I guess it is a leaf you're passing. The pointer would be none. Anyway, never mind.

Diamond Pterodactyl: Okay, so what would that look like? So if I'm, I'm just walking through the example, if I'm at the depth, this would be a nine, this would be a nine, this would be a six, this would be a six. Or is this kind of what you're saying here? And what would this thing, if you have a left and right, then would this be a 6 or a 9 or 6? 9.

Clandestine Snake: It would be its root, right? Because each level or each thing you're doing has recursive call. So it would be its root.

Diamond Pterodactyl: Got it. So this would be two.

Clandestine Snake: Definitely not a chain of 69.

Diamond Pterodactyl: Yeah. Okay. And if this were a four, then this would return none or none. And then would this still return one? I guess it would still return one. This five here. This would be seven and then eight.

Clandestine Snake: So why would Z4 be a none?

Diamond Pterodactyl: Oh, sorry. I was. Sorry, I was not. I was not thinking about that. I was actually trying to think of. I jumped ahead of myself thinking about the edge case of if I was trying to create an edge case in which. Not edge case. I was trying to create a situation in which a leaf node is not deepest. So I can work throughout the logic of how would that affect the decision of what to return here?

Clandestine Snake: Sure, sure.

Diamond Pterodactyl: Yeah.

Clandestine Snake: Then four would be none. That's right. Or rather forward if there's no leaf. Yes. It would turn none. And then you'd compare the recursive call from 2 and 4. It'd be true and false. Right. Left would be true. Right would be false because left is true. You would return the left subtree which would then pop back up to the one with a truthy value.

Diamond Pterodactyl: Right.

Clandestine Snake: And then potentially all the way back up to three.

Diamond Pterodactyl: Okay, that makes sense. Okay, for the sake of time, I could either try to code this or.

Clandestine Snake: Like. Sorry, I'll give you an extra five minutes if you'd like, but that's the most do. Just simply so we don't.

Diamond Pterodactyl: Okay, that's. Wait. Sorry.

Clandestine Snake: Don't worry, you have an extra. You have until 7.

Diamond Pterodactyl: 55.

Clandestine Snake: I'll give you extra time. I just have to at the end for questions just like they would.

Diamond Pterodactyl: Yeah, yeah. Let's do XDev is going to be rude. We talked about definitely def is equal to 0. Max depth s equal to none. Deepest node and then for stack is equal to root while stack equal to stack. Pop. I'm just writing the boilerplate node back. Dot append node right, node left.

Clandestine Snake: In the future, you've already written the plate up above, remember? Copy that just for reference.

Diamond Pterodactyl: Oh yeah, good. No, that's just BFS though. I don't know if that's the same, but I guess it doesn't super matter. Yeah. Depth. I need to keep track of the depth. F is one. This is one. I want this to be F plus one. F plus one. Oops. And this would be node depth. Depth is greater than max depth. Max depth is equal to depth. And then deepest nodes equal to node. And then lf depth is equal to max Depth append node else don't do anything. What's this? Not happy. Cannot be assigned to object. I'm going to ignore that for now. And then for lowest common ancestor root node, the base case we said is depth. If the root node the depth max depth is equal to max depth and return node, we want to return the current node and we want to Recurse the left left isol ca node left depth plus 1 max depth. Right is equal to LCA depth plus 1 max depth. We want to check here. If left and right return node. If. Lf. Actually we can just return. Lf return. If one is the other, it should be L or right. Otherwise return none and then if not node return none and then our thing.

Clandestine Snake: Sure about that?

Diamond Pterodactyl: Left or right? Is that what you're saying?

Clandestine Snake: I don't think that's. Let me see, what's the other function you're creating? I'm curious.

Diamond Pterodactyl: Oh, this is the overall function where I call lca. This is the max LCA of deepest nodes. And then max nodes is equal to maximum or max. Not max depth. Return max nodes or deepest nodes. I want deepest nodes equals to max depth root and LCA root. I guess I want to return the depth. So maybe I return the depth here and then max depth one max. I didn't want to overshadow. That's why I wrote def M def.

Clandestine Snake: Well, what if your root is null? Would the depth be one?

Diamond Pterodactyl: No, it'd be zero, but I can check for that. Perfect. Okay. Yeah. Well, I know we're at time, so I don't want to spend more time, but this is the high level picture of, of what I would write.

Clandestine Snake: So I'm going to share with you one thing and we can kind of jump into the review aspect of things.

Diamond Pterodactyl: Okay.

Clandestine Snake: This is not going to be in Python, but it's very similar. I mean, tomato, tomato. So this is what I was referring to. Like you, I think you did solve it. I'd have to run it to see. Just because this part on line 156, 157 is a bit iffy for me.

Diamond Pterodactyl: Right now.

Clandestine Snake: Because once you have your max depth, right, and that's your base case, what you want to do with your curse, basically just pass in your root left or the current node left. The current depth plus one because you're going down and the max depth and same thing with the right side, right. And basically the value you have from that, like from the overall end recursion, right. It would check to see if left and right are. Sorry if they're not falsely right. Basically, if the deepest leave is in the left and also the right, right.

Diamond Pterodactyl: Right, return the root.

Clandestine Snake: Otherwise it's not an else. If it checks. If, if the left, then you return the left. If the right, then you turn the right. And that's kind of the logic you want to do here. The or would not necessarily result in the right answer, if that makes sense. Because if you have a left or right, you're returning node first and foremost. You're not returning the calculation of the recursion or the value from the recursion, which is left and right. You'd want to return either left or right. You'd only return node if it's left and right. If that makes sense.

Diamond Pterodactyl: Yeah, that makes sense. Yeah. I'll have to walk this through later because what we wrote in the. And we walked through the example, I was returning on line 109110 in the case if the four was a no, I was returning one instead of two. I was simply. I was just following that logic without thinking too much about it. And so. So you're saying, yeah, I'll have to walk that through again. But like in terms of translating what we, what we talked about to code, that was kind of how. How I translated it. So for sure.

Clandestine Snake: So I will essentially start giving you feedback now because I think it's worthwhile.

Diamond Pterodactyl: You're.

Clandestine Snake: You're basically there. Meta is very strict, unfortunately. I mean, very, very strict.

Diamond Pterodactyl: Yeah.

Clandestine Snake: So in this case, technically, I wouldn't like advance you. Usually what happens is if you solve one out of two, it's. They kind of like, especially if you're almost there with the second problem, they might consider moving you forward. It's more of like a, you know, depending on like your work history, your experience, all that kind of stuff. But if you don't solve at least one out of two, it's definitely no, in this case, you did solve one out of two. I don't know your context, your resume, your experience and all that, and the kind of position you're applying to. But generally speaking, assuming just like a general viewpoint, since you didn't solve the second one correctly, I wouldn't move you forward. Although if it's a technical screen. Right. If it's not like an actual on site round, if it's just a technical screen, I would potentially move you forward. So I want to make sure you have that context. Technical screen round you pass. But on site round, you definitely wouldn't like. This wouldn't be a positive interview for an on site Round interview, if that makes sense.

Diamond Pterodactyl: Yeah, no, understood.

Clandestine Snake: But yeah, I mean, your logic is there. I like the approach you're taking because that's something they really value. Your pseudo code, walking through your edge cases, doing a dry run, trying to find what's wrong with your logic or what's right. Identifying time and space complexity, potential optimizations, asking whether or not if you have time or should consider pre optimizing something. Right. Or if you can just kind of go into it with the original approach that you've already identified. This is all great stuff. What else can I offer you? Be very cognizant with the time. Unfortunately, with Meta, this is. I hate this, I hate how they do this, makes no sense. But yeah, they are gonna be very, very like strict at the time. So when it comes to intros, when it comes to all that stuff, just, you know, like have your thing kind of memorized in a sense to just quickly talk about your stuff and not spend too much time on it. Don't try to make too much small talk with them. And I think with Meta, what they actually try to do is they do try to offer hints and everything. At least my experience when I interview with Meta, they are very much so. It's like, you know, they're engaged and they're trying to solve the problem with you. It's not just like, hey, here's the problem, they're just going to keep quiet and see you struggle or see you succeed or something. Right? So ask questions, know, communicate, talk, talk, talk. Don't just think things through your mind. Do what you did here today, right? And I think hopefully you should be fine. I mean, this is one of those like weird questions where it's worded weirdly. Right. On purpose. So I mean, just be ready for that too. But I mean, you identified an LCA approach, which is essentially what this problem is. So yeah, I think you'll be fine. You'll be fine.

Diamond Pterodactyl: Okay, I appreciate it's a technical screen. Quick question. Usually they say two questions. Are the two questions usually related the same way you, you like laid it out where they.

Clandestine Snake: No, unfortunately for me, I remember when I interviewed Meta, this was only about a year and a half ago, actually. No, I'm sorry. Yeah, it was a year and a half ago. I apologize. So what happened was they gave me a, they literally gave me a binary search tree question, like do a level order traversal and print out the array of that traversal, I guess. And then the second question was a algebra type math question, I guess because they're trying to jump on the AI bandwagon and they just asked me a random math question that I just couldn't remember. I didn't know how to solve it at all, so. And that was a technical screen round, but for whatever reason, I didn't pass just simply because I guess the algebra thing was in there. So they can literally throw a math question at you or they can do something like I did, where I've had that happen to me as well, where they, you know, built upon a question like similar pattern, similar data structures. So unfortunately the answer is. It depends.

Diamond Pterodactyl: Okay, that's, that's fine. I appreciate the data point. Yeah.

Clandestine Snake: Any other questions? Maybe I can offer more insight.

Diamond Pterodactyl: No, I think it's, I mean, I, you know, just. It's a good feedback loop when you don't finish the question. So I definitely have know the feedback I'm looking for. Yeah.

Clandestine Snake: Awesome. Well, I do wish you luck. Keep practicing. I think you're there at least for technical screen. I think you'll be fine, but just really keep grinding for the on site.

Diamond Pterodactyl: Cool. Awesome. Thank you. I appreciate that.

Clandestine Snake: Have a great one.

Diamond Pterodactyl: All right, good night. Bye. Bye.