The Legendary Avenger: Hello.
Superimmune Chameleon: Hello.
The Legendary Avenger: Hey. Hope you're doing well. How's your day going?
Superimmune Chameleon: Pretty good. How's yours?
The Legendary Avenger: So far so good. Can't complain. End of work. But yeah. So just to get it started, maybe give me a quick run through of what you're prepping for as well as what you're looking to get out of this.
Superimmune Chameleon: Yeah. So my title right now is senior software engineer. But I've come up in the startup world, and I'm not sure how to say it, but it almost seems like I've had it easy in the interviewing. My interviewing has just been focused on sort of practical problems. And while I've kind of lazily been doing data structures and algorithms for a couple of years, I just haven't focused on it. And so this is sort of like, I'm hoping this can be like my calibration interview to see where I actually am and some of my weaknesses so that I can have a plan over the next year to just study. Basically, I'm not prepping for anything in particular.
The Legendary Avenger: Good. Not makes sense. And do you find that you have set of specific domain that you find that you're strong and any other that you find that you weak? Because I don't want to give you something that you value. If it's a probing interview, it will be good for you to actually struggle a bit. That way you kind of know where you're struggling and focus the practice on that. Right?
Superimmune Chameleon: Yeah. I mean, I don't have strong preferences. Like, if you were to give me something like a graph that required me to build an adjacency list, I wouldn't know how to do that right now. I don't have several, probably common algorithms memorized. I don't know how to just implement Kadan's algorithm. Basically, I find myself doing okay with lead code easys, and then with mediums, I would solve maybe like 30% of them or 40%.
The Legendary Avenger: Duly noted. Okay, that makes sense. So, for context, I'm not going to play nice. I'm going to actually ask what I consider a medium. That said, it's not a trick question, necessarily, because at least my goal here with this interview is to see the weaknesses. I don't think I'll be serving you well if I'm just giving you something and complimenting you all the way. That said, what you can do is, I'll give you the question. You'll solve it as though you're in an interview. Don't feel any pressure if you struggle with it, don't feel any pressure to get let's say an inefficient solution. We're okay with that. And the problem here has multiple solutions, multiple possible solutions. Some were efficient, some less so. So we'll just walk through them together. I want the first phase of it, you work on it on your own. The second phase of it, we can delve into it and think about possible optimizations, because at least when you're a senior, they'll be looking for that out of the box thought. And then we can just go from there, and then you can center the feedback around how your process looks like and at least how to prep. In this case, you're going to be targeting binary trees. So that's kind of the plan I have here. Does that make sense to you?
Superimmune Chameleon: Sure, that sounds great. Thank you.
The Legendary Avenger: Awesome. All right, so are you familiar with the lowest common ancestor problem?
Superimmune Chameleon: Lowest common ancestor. So basically this would be a situation where you give me two nodes and I need to find the ancestor that is nearest to the root node.
The Legendary Avenger: Excellent. Yes. And in this regard I live and give you the freedom of having a parent pointer. So in this regard, you can look up the definition there. But we're going to try and basically solve this problem here. So use any approach you want. Now that said, I'll give you the class definition for the node, and feel free to construct test examples. So part of the test here will be how you actually deal with, let's say, testing. I'll be looking for that, so feel free to actually modify this. Fortunately, it's Python, so we're fairly fast with this. And so we have ourselves Val, and you can initiate that as none, same case, cells left. You can actually pass this in as parameters to make life easier. You can say Val, left, right, parent. I just realized I'm very spoiled by copilot. Normally I'll not write any of this.
Superimmune Chameleon: No prOblem.
The Legendary Avenger: All right, so feel free to get started. I think you kind of get the sense of what I'm writing out here, and then we can build out some test examples over time.
Superimmune Chameleon: Yeah, okay, that sounds good. So yeah, maybe I can start by just sort of in the commented section, just sort of drawing out my understanding of a test example. And so if we have a node that is like, let's say that it's four, and then we've got a three over here. 71256. Um, so in this case, if you were to give me three and seven, the lowest common node would be the root node. But to make this example a little bit more interesting, let's do something like this. I'm not worried about the tree being balanced right now. I'm just trying to get an example. So let's say that there's like a seven here. So if I were to get the seven and the eight, the lowest ancestor would be 13.
The Legendary Avenger: That makes sense to me.
Superimmune Chameleon: Okay, great.
The Legendary Avenger: And what I've done here, just to even make the testing easier, I'm going to provide predefinitions for some of these nodes that if you want to construct the tree manually, that is also a possibility. The goal is to make life easier here. Right?
Superimmune Chameleon: Yeah, sure.
The Legendary Avenger: All right, keep going. I think this makes sense to me.
Superimmune Chameleon: Okay.
The Legendary Avenger: I don't know why transition to whiteboard?
Superimmune Chameleon: Yeah, sure. So I see you're constructing these nodes.
The Legendary Avenger: I wish I had these definitions earlier. My apologies. But hey, at least we get to walk through them.
Superimmune Chameleon: Yeah, sure.
The Legendary Avenger: There we go.
Superimmune Chameleon: All right. Yeah. For test one is node four. Yeah, that makes sense.
The Legendary Avenger: And then if you want to add nodes, you can say test one left is equals to. Maybe in this case, we wanted node three.
Superimmune Chameleon: Right, right. That makes sense.
The Legendary Avenger: That basically makes it easy to build the trace. Keep going. I'll give you the freedom to do that if you want. Start an algorithm.
Superimmune Chameleon: Sure. And then node three is just a reference. We can say left equals node one. Gosh, it really wants to autocomplete for me. Oh, do I not have a node one? I don't. Let me make R1 quick.
The Legendary Avenger: And if you want to also set the parents, you can do that too.
Superimmune Chameleon: Sure. Right it. And let's say parent is node four. Parent node four, excellent. And then let's say start with node 13. So node 13 was passed as the right of node one. So node 13 left should be node eight. Node 13 right is node nine, which I need nine. And I haven't set node 13 parent. So I could do that. Now. 13 parent equals node four. Um, and node eight. Dot. Parent equals node 13. And then let's do same for node nine. Parent equals node 13. And then. Almost done. We just need node nine. Write equals node seven. And node seven. Parent equals node nine. I think we have basically the tree constructed at this point. We'll see. Maybe there's a parent I forgot to add or something.
The Legendary Avenger: Totally good. Yeah. At the end. I think we can correct for that. I think it was good just to make sure you have this practice with manual testing. I feel like typically when I give people this, they usually don't know what the heck to do with it.
Superimmune Chameleon: But it is good.
The Legendary Avenger: In this case, you observed how to test, which is a good thing.
Superimmune Chameleon: Yeah, I see I made a mistake here. Node two parent was node four. Actually, node two parent was node three, and then it was node three parent, which I failed to do here. 1 second, almost done with this equals node four. Okay, so great. I think we're in great shape. So fantastic. Yeah. I think that we've constructed a test case that makes sense here. And so in this representation between lines 15 and 18, the sort of test example that I was hypothesizing about that we've constructed is in this particular tree, if I were to take the inputs eight and seven, so presumably the function signature, if I'll just spend a minute typing this out, would be something like Lowe's common ancestor, let's say LCA, and this would be node one, node two. And we can just say that these will be, rather than references to the node, would these be references to the node or just the values, integer values?
The Legendary Avenger: Let's say it will actually be references to the nodes themselves. So we'll have the nodes passed. That makes life easier too, right?
Superimmune Chameleon: Yeah, that sounds great. Yeah. So in this case, just to sort of define a high level kind of algorithm here, my thought is that I do something like set up. So this function, I think is most sensibly implemented recursively, at least for now. That's what I'm thinking. I may change my mind on that. But initially, either way, we would just sort of do some preliminary validation. And so I would say ensure that node one and node two are set. Otherwise the lowest common ancestor of a single node is the node itself. I believe that's true. Maybe we can go with that as a heuristic. Like if one node is not set, okay, else node that is set is LCA. Obviously, if null inputs, we are done. Given that we have control over it here, maybe that's a case that we can ignore. But yeah, once we do some preliminary validation, I think that trying to think of the best traversal strategy, but we have the references to the nodes themselves. And given that the nodes have parent pointers, I think there are some interesting cases to consider in this particular case that we're hypothesizing about where eight and seven are the nodes. Neither seven is not an ancestor of eight and eight is not an ancestor of seven. But this is theoretically possible, right? If the question were node nine and node seven, then the lowest common ancestor would be node nine itself. And so it wouldn't make sense to just take node nine and start traversing upward, necessarily.
The Legendary Avenger: So let me just ask you intuitively, as a human being, when you look at it, what's the silliest, stupidest way you can actually find that lowest common ancestor? Naively, we are not even worried about optimizations.
Superimmune Chameleon: Yeah, I guess I would start from the root node and basically depth first search the tree, keeping track of the nodes that I find along the way. And then if I identify that one of the nodes is either the left or the right of the current node that I have, then I would sort of pause there and continue to traverse down. Well, that's interesting. I would pause there and then essentially record that and then continue traverse down until I find the next node. Essentially.
The Legendary Avenger: Keep in mind, at first value, we don't know what the root is. The input we have is node one and node two. Will you fast find the root, or can you think of another approach? We have the nodes themselves. Is there a way we can just look back, so to say?
Superimmune Chameleon: Yeah, well, I mean, if we have the nodes themselves, then we can literally just traverse the parent pointers up until we find the node with no parent. And that would give us the root and so we could quickly identify the root. Yeah, go ahead. Yeah.
The Legendary Avenger: Now to your point, let's take eight and seven, or even nine and seven. So we have nine and we have a path to trace the root. What will that path look like? So I'm just going to type here. If you have to track the path for nine all the way to the root, how will that path look like?
Superimmune Chameleon: Yeah, we would go from nine to 1313 to four.
The Legendary Avenger: Nine to 1313 to four. All right, same case with. Let's just say we are going to do the same with seven. What does the path for seven look like?
Superimmune Chameleon: Seven to nine to 1313 to four.
The Legendary Avenger: All right, nine to 1313 to four. Is there something you're observing here that could be of help or use for us just by typing those two?
Superimmune Chameleon: Oh, yes. So the only difference between the two is the seven. I see. There is a point at which they match. Yeah, that's interesting.
The Legendary Avenger: That point where this match, where does it start?
Superimmune Chameleon: That would be the index, one of the seven list or the first index of nine.
The Legendary Avenger: Excellent. So we know the value is nine. Right. And what's the lowest common ancestor?
Superimmune Chameleon: Nine.
The Legendary Avenger: That's it. So the keynote that I want you to note there is, for some reason, the first value that is common amongst them. The fast value that is common between these two lists is actually the lowest common ancestor. Do you see that?
Superimmune Chameleon: Interesting. I see the first value that is common between the two lists. So this might be a valid strategy where we have the references to node one and node two. In both of them we find the root just by traversing the parents upward and we build a list. Essentially we keep track. And then after doing this process on both of the nodes, we basically diff the lists and find the first match and return that as the common, lowest common ancestor.
The Legendary Avenger: Excellent, that makes sense. Now feel free to code that and then from there we can actually talk a bit more. So I think I might have some suggestions. I would want to think through them with you, but I would want you to implement that. So by all means take over and let's keep going.
Superimmune Chameleon: Okay, so what I would do here is I'm going to define a helper function, and the helper function will just take in a node and we will just basically return the list of nodes that are on the way to the root. So let's just say list, or let's call it root list. And what we would do is set up a base case where if the node, I'm a little bit newer to python, but if not node parent, I think is what we would say, then we can return the root list. Sorry, that's actually not accurate. If we need to append to the root list and then it, and then return the node and then return the root list. Otherwise what we're going to do is invoke node parent with current root list and this should basically get us the list. And so what we would do is then call root list one. Let's call it ancestor list. That makes a lot more sense. Ancestor list one, an invocation of helper with node one here. And then we can take this and do the same thing for the second node. And now that we've got those two lists, we would just do a comparison between them to see the first point at which the references don't match. And so this is interesting, I'm not sure if I should traverse the lists backward back to front, because at some point that's interesting. This operation I'm finding tricky to think about for some reason.
The Legendary Avenger: How about I ask you this? Okay, the helper function we know will give us the list. So say we just do it for our fast node, we find all the ancestors for node one. Okay, what if I was to just traverse node two without even generating a list? So I see seven, I check, is seven in my ancestor list for nine. It is not, right?
Superimmune Chameleon: I see, very interesting, great.
The Legendary Avenger: And so that kind of says, because as soon as you see the lowest common ancestor, you know, it must be somewhere in the ancestor list for the previous one, and then at which point you can just return that.
Superimmune Chameleon: You see that, right? Yeah. So I actually only need the ancestor list of one of them. And then there's this kind of next operation, which is very similar to the Helper, but it's almost like a modified version of the Helper. I'm not sure if it makes sense for me to try to reuse it, but maybe that's interesting. Um, maybe we can say if there, if this is set, then I'm not, I'm not sure I like this strategy, actually. It may be just worth defining yet another recursive helper.
The Legendary Avenger: How about what if we do this, we just say node one. Let's say we're always going to check node one, call Node one list. Just say that. Right. Let's define it externally. And then in this regard, I know we're using root list rather than have it be passed here, we just do this. Node one.
Superimmune Chameleon: Oh, I see. We don't even need to pass it.
The Legendary Avenger: And at this point we probably don't even need to return anything. Right. So helper just fills the node. So in this case, you're checking if node one has a parent. If it is, or whatever node you have, you'll be checking if it has a parent. If it does, then you add to the list. Otherwise at that point you break. So you can remove the, what do you call it, actually? Otherwise you continue, basically.
Superimmune Chameleon: Should I just do just a naked return there for the base case?
The Legendary Avenger: Yeah. So here, if not node parent. So here I think this should be if node. Let's generalize this a bit more. So if node, we say if node, node one, append, we just add it. So if the node is valid, if it's not a none, that's when you add it, right?
Superimmune Chameleon: Yeah.
The Legendary Avenger: Then makes sense. Else return. And then put this recursive call here. So we are recursively calling this within this point.
Superimmune Chameleon: That makes a lot of sense. That's great.
The Legendary Avenger: And let me just show you this other approach, just to make sure we can also think about it. Another alternative will be to say while node one, while node one. In this regard, you can just say, you can say ancestor one equals to that. And you can just say while node one. Ancestor node one append. What is it? Node one. In this case it's actually node. Let me just say node one.
Superimmune Chameleon: Equals node one parent, I guess I see, yeah, that makes a lot of sense.
The Legendary Avenger: That's an alternative, right?
Superimmune Chameleon: Yeah, very good.
The Legendary Avenger: All right, now with that in mind, so we have an ancestor list one. So how do we use that, given the logic we had there?
Superimmune Chameleon: Well, your actual strategy that you've just illustrated right here, now that we've got node list one, and I guess we still have to invoke helper just on the node, but then we can expect that the node one list will be populated. And so after this occurs, we can just use the same kind of strategy that you just used on node two to traverse it. But instead, here, what we're doing is checking if, I guess we say node two in node one list. Maybe we would say not in. Right. The first one that isn't in. Oh, I see.
The Legendary Avenger: Are we checking when it's not in or when it is in? Like, when do we break out of the loop?
Superimmune Chameleon: Yeah, we would break out of the loop when it's not in, but it's not enough for it to be not in, I suppose. Right. It has to be the first one that is not in.
The Legendary Avenger: Is it not in or in, if you think about it, when are we breaking? So as soon as we see it, we found whatever we're looking for and then we break. Right. Going back to the example. So look at line 63. So this is our ancestor list one on line 63.
Superimmune Chameleon: Right.
The Legendary Avenger: So in this case, I know we have generated this whole list here. So we have seven at hand from seven check.
Superimmune Chameleon: I see. Makes a lot of sense. Yes. The minute that we see that our current node is in the list, that's when we break. I guess we return node two, and then otherwise we just use the same kind of traversal technique to say node two equals node two parent.
The Legendary Avenger: Excellent. And there's one thing I want to point out here, because the root is a guaranteed ancestor. Right. We have the root that will always guarantee us that at the very least, we'll always have the least common ancestor.
Superimmune Chameleon: Which is the root.
The Legendary Avenger: So yes, it's the highest ancestor, but it's always going to be there. So by virtue of that, we'll always have something in common between this list. So an example with our list here, if you are given one and seven, right?
Superimmune Chameleon: Yeah.
The Legendary Avenger: There's no lower ancestor really, except for four. So at the very least we know they will converge somewhere at four.
Superimmune Chameleon: Right.
The Legendary Avenger: You see that?
Superimmune Chameleon: Yes, that makes sense.
The Legendary Avenger: All right. And so question to you, what's the performance of this algorithm, both time and space complexity?
Superimmune Chameleon: Right. So in terms of time complexity, we have a couple of operations that are relevant. The first is the race to the root, and the second is the traversal of the second node to the root. Both of these. In worst case, assuming that, let's say that we had a situation where essentially what we have is just a long string of dot rights where everything is essentially almost like a long linked list, this would be O of N. Both of these operations, the traversal of root one to the root and traversal of root two, or, sorry, node two to the root, are O of N. And so I think the overall time complexity is O of N for this solution.
The Legendary Avenger: Perfect. And that is excellent. I really like that you thought of it in terms of worst case, not just average case. Now that said, if you were to generalize it, so whatever the case, even the worst case, how would you define that distance from the root to the farthest node? What's that distance to us in three terms? That is.
Superimmune Chameleon: Yeah, I guess it would be. Yeah. I'm not exactly sure how to define that. Let's see.
The Legendary Avenger: Maybe, let me rephrase.
Superimmune Chameleon: Sure.
The Legendary Avenger: If we have a bamboo tree or a bamboo shoot right here, just a single line itself, how bamboo looks. And it's, let's say 10 meters tall. Right. And we have another acacia tree with a lot of branches, but it's also 10 meters tall. What's the height of those two trees?
Superimmune Chameleon: Oh, I see. The height of those two trees is 10 meters for both. But it's expressed in terms of h, right? Yeah. So we Would say that the actual maximum length of N is H, where H is the height of the tree. The number of layers, I suppose.
The Legendary Avenger: Precisely, yes. And that's it. So at least we now define the complexity in the correct terms, because the reason why OVN might be confusing is if we generalize it even in the acacia tree case, then technically it's not OVN. Right. Because that's not a worst case. In the worst case, we get it. But if we want to generalize the worst case better, we'll have to refer to the height of the tree. So that's good.
Superimmune Chameleon: Okay.
The Legendary Avenger: Alternatively, you can even say maximum depth. Now, here's the thing. This is not the best approach we can take, especially on that height part, because that also defines our space complexity. You can imagine that least one. Right. So space complexity would also be of H in the last case. So the question to us here will be, can we do better? I'll let you try and think through that. Can you see any other approaches that will work better?
Superimmune Chameleon: Yeah. Well, right now, one observation to make, just in terms of the comparison strategy between these two lists, is that we are traversing up to nodes that we don't actually need. In order to discern a difference. And so the operations that we spend traversing 13 and four are not necessary. I'm not quite sure how yet, but it seems like it would be possible to know that you've reached a common ancestor earlier in the traversal by comparing maybe the two different pointers or something like that.
The Legendary Avenger: All right, now I'll give you a hint here, because it's one of those almost tricks, so to say, it will be good, kind of like a dense algorithm. It was good to mention that. Are you familiar with Floyd's algorithm for cycle detection?
Superimmune Chameleon: I don't think so.
The Legendary Avenger: It's typically also called the tortoise and hair algorithm. But here's the idea. Are you able to switch to the whiteboard? I can show you a trick here.
Superimmune Chameleon: Yeah, great.
The Legendary Avenger: Say we have this. I'm just going to define a bunch of nodes here. So let's just define our tree here at the moment. Right? And I'll add some more examples hEre. So this is the tree we have. So say this is our tree here. And then you can help me with the pointers here. Let's just connect these pointers. So this is our tree. It's going this way. It's a fairly simple tree at this time, in case let's connect this too. Now, if I was to go a bit crazy here and say we're going to assume this is our fast one here, where's the text? And so if this is Node one, let's just say node, node one, and this is Node two here. So say I was to find the common ancestor here. I know it's this and I don't want to save the whole space. So what if I'm just going to go crazy here, I know this is where the root is. What if I decide I'm going to connect this to, and I wish I could draw because I want to actually have the cycle. So I'm just going to connect these two. So as soon as you hit the root, I tell it, okay, the parent for the root is now going to be this node. So what's happening here is as I traverse up the nodes, you can see what would happen here is I can go up, go here, go in a circle, go up, keep going, go in a cycle again. So I'm stuck in this cycle here, and if I start from here, same case, I'll basically be going in a cycle at the same time, right?
Superimmune Chameleon: Yeah.
The Legendary Avenger: So imagine if I start from here and I decide I'm going to go with this one here, one step at a time with this one here, two steps at a time. What does a fast car and a slow car in a cycle do? Like what will happen?
Superimmune Chameleon: They overlap.
The Legendary Avenger: Precisely. Now, the key question to you here is when they overlap. And the key insight here, and this is actually the basis of Floyd's algorithm when, let's say I start from here. So the slow pointer starts from node one. This fast pointer starts from, let's say, two steps ahead. If they just start going, whatever point they meet in, the cycle will usually be equidistant to the convergent point by whatever length we have from the first node. It's trippy, but that actually works. So, typically, the idea behind Floyd's algorithm is you launch two fast and slow pointers, have them keep going until they meet with those two steps at a time for the first one, and then as soon as they meet, bring the slow pointer to the start again, and then have them go one step at a time. They'll meet at the convergence. Does that make sense?
Superimmune Chameleon: Wow. Yes. It's hard for me to understand why that works.
The Legendary Avenger: Yeah, I'll show you in a few. Give me 1 second.
Superimmune Chameleon: Okay.
The Legendary Avenger: I used to be tripped out, too, but I'll show you. There's a mathematical. So I'm only going to show you the mathematical approach. And then from there, we can essentially think of another alternative. In fact, here's a stupid thing, that's not even the most efficient approach, though. I just want to make sure. Let's see. Cycle detection. Floyd, improve. So I'll give you this link here. It's a stock exchange link, but we can discuss it together and then think about how that will work in our context. Oh, let's switch back to the notes, because I feel like that will be so on line 90. I pasted it in.
Superimmune Chameleon: Okay, great.
The Legendary Avenger: And so there's this explanation here. So I don't know if you can see it. So if you go into that link, you'll see there's a response that has been explained there, and you'll see distance traveled by the slow pointer. Before meeting, just look at the math and then tell me if it makes sense. If it doesn't, we can discuss it a bit more.
Superimmune Chameleon: The distance travel with my slope pointer is X plus Y, as pointer is X plus Y plus Y is essentially X plus two, Y plus C. Oh, I see.
The Legendary Avenger: Do you see that? I don't know if it's making sense to you how X becomes equals to Z make sense, or should we run through?
Superimmune Chameleon: It'd be helpful to understand, but basically, this boils down to two times the distance of the slow pointer is, of course, the distance of the fast pointer. Right. But in the context of a cycle, um, the time is constant for both when both pointers reach the meeting point. Yeah, that makes, that makes absolute sense.
The Legendary Avenger: Exactly. And so it's a trippy concept, but it's mathematically provable. And you can actually, in my case, what I did to understand it more, I wrote simulations, and it's good to just See it in action. Unfortunately, because it's such a common proof, there's also videos you can probably find on YouTube that actually show it going wrong. Not wrong, it going round. And I've seen some where they actually use, like, f one vehicles. And it's really nice to see it making sense. But the whole idea here is if you just kind of keep those steps in mind, it's literally just understanding there'll be overlap. And so long as my first pointer is moving at twice the speed of the second one, wherever they meet, the distance to the point of intersection will be equal to the distance from the start. And when you have that in mind, when you come back to our problem here, given how we've now created a cycle. Right, you see how we've now created a cycle, so we can literally ignore everything else. We can even take this. This is a linked list and it's a cycle. We can now do that. You see that, right?
Superimmune Chameleon: Yes. The idea here, though, is that if you were to start at node two and traverse to find the root, then you simply point the route to the starting point.
The Legendary Avenger: No, what will happen is with this. So if we create this cycle, both our slow and fast will start from, say, node one, and they can start from node two. But the whole idea is if you're going to start from node one, once you hit the root, you point to the other node. I see, yeah, they both start here and then they keep going up. The parent only that fast will be going two steps at a time, slow will be going one step at a time, and wherever they meet, because as soon as they get into the cycle, because there's no pointer from this convergence node to the node itself here. Once you're in the cycle, you're in the cycle. And so once they start moving, they'll meet somewhere. We don't know where that is, but wherever they meet, the distance from that node to this convergence point will be equal to the distance from this node to this convergence point. So I would expect that the first time they get into this cycle, they'll meet at node Two. And if you get a bigger tree, then that's something we can observe too. So they'll meet at whatever the distance is. And so what you'll want to do then is as soon as it gets there, just move the slow pointer back to node one, let's call it the starting point, and start going one step at a time. Right. Because at this point we still don't know where that convergence point is. So just move it back and have them both go one step at a time. So it's literally go X steps and then trust that they will meet at a certain point. Makes sense.
Superimmune Chameleon: Okay, I think I understand everything up until. So once they meet in the cycle, you know that they are equidistant from the convergence point, right?
The Legendary Avenger: Exactly.
Superimmune Chameleon: But then, yeah, go ahead.
The Legendary Avenger: The equidistant from the convergence point to the distance. From the convergence point to the starting point. So this is our X, right? So our X is right here. And so wherever they'll meet, in this case, I know it's node two because it's a fairly simple tree. Then leave the first pointer there. Or even you can just say, leave one of the pointers there, move one of the pointers to the start, and then have them start going step by step until they meet again. Because those steps that they each take.
Superimmune Chameleon: And in that Second traversal, where they are now going step by step when they do meet, you know that that is the LCA.
The Legendary Avenger: Precisely.
Superimmune Chameleon: Interesting.
The Legendary Avenger: It's a trippy move, but it's relying on the fact that we are creating a cycle between the root and the second node and then the other node. The first node is going to serve as our starting point, and it can be the opposite. If you want to create the cycle between the root and this one, only that node two will be our starting point. Okay, does this make sense?
Superimmune Chameleon: Yeah, I think so. I think the suggestion to make some simulations around this later and play around with this is great. I'm going to do that for sure.
The Legendary Avenger: Absolutely. Now here's the thing. That's not the most efficient solution. And when I saw the more efficient one, I beat myself up. And so, I'll admit it's kind of trickish, but it's elegant. And so I'Ll just paste it here for you and we can both front that. Somebody actually came up with this. So can we go back to the code?
Superimmune Chameleon: Yeah. All right.
The Legendary Avenger: So you ready? Somebody came up with this crap. Just go through it and then tell me if it makes any sense.
Superimmune Chameleon: Okay, so what we're saying is we get a node which is P and Q. And if the nodes are not the same, while the nodes are not the same. Um, okay, so. Oh, this is, this assignment is interesting. So we, we basically keep a reference to the, we keep, we keep a couple of pointers to the original nodes, but then we have these sort of traversal pointers that we give ourselves. And while they are not the same, we set P one to the parent, if there is a parent. Otherwise we set it. Interesting. We set it to the other node. And this one, same thing. Wow.
The Legendary Avenger: I'll do this. You can go back to the code and let's think about how that looks like in the context of paths. Right?
Superimmune Chameleon: Yeah.
The Legendary Avenger: So what we are saying here is we are just doing a traversal. So I'll just draw it. And I wish I could switch the color here. So we're going to say for P one, let's see what is a nice color to use. I'm just going to go some random number here. Oh, sorry, I did not know that FfF was white. So here, GGG, I guess how that works. I don't know any colors, really. Okay, so the idea here is with node one, we are going to go up this path, up this path, and then go up this path, and then that's our path for node one. Right?
Superimmune Chameleon: Yeah.
The Legendary Avenger: Now with node two. No, that's the other question. And this is, I kind of wanted a different color, maybe five. I'm just going to try a different number with node two. It's going to be up the path, up the path, and then as soon as we hit the root node, it swaps, right?
Superimmune Chameleon: Yes, I see. Because as soon as it hits the root node, that's when there is no parent and it sets it to the other node. Okay, exactly.
The Legendary Avenger: And so the whole idea here is there'll be this part where they both have in common all the way up to when they start. But now if you were to call these distances out, let me type this out here. Let's See if you were to type the distances out. And this is a good explanation I saw somewhere. Are you able to go back to the text?
Superimmune Chameleon: Yeah.
The Legendary Avenger: Just this explanation here because I think it can be helpful. And while this is specific to this type of problem, it also is a good solution because especially when you start working with linked lists, there's this problem called linked list convergence. So just knowing this is a possibility is usually a good technique to have. But if we were to define the path. So if you think of P's path or P one's path. So P one is a pointer to node one, P two's path is the pointer to node two, and then C's are the Commons. So whatever common parents they have, common ancestors they have. If you're going all round, we know we'll explore them. So for P One, we know we are going from parent one to parent two to parent three, until somewhere we hit a C one. So if they, let's say, had the same distance from the common ancestor, this is fairly straightforward. We know that they are going to meet at C one. So case one here, line 61 and 62, this is fairly straightforward.
Superimmune Chameleon: Yes.
The Legendary Avenger: Now, it becomes tricky when they're different distances. So what's happening here is this one might start from Q one, which is maybe one level from the common ancestor. But now what I really liked was we have the paths defined. So if we have the PC as the P common path, and then C is the common ancestor, and then the QC is the QC common path, it means that our P will travel PC to C to QC and our Q will travel QC to C to PC. So in essence, they're traveling the same path to a degree. And so if you were to actually evaluate one step at a time here, then we know that they will eventually converge at C, because these distances are equivalent. So as soon as it hits that cycle, we know that whatever balance is, there will be the distance to C. So if we are doing one step at a time, they will eventually converge at C. Makes sense.
Superimmune Chameleon: Yes, this makes sense. It's interesting.
The Legendary Avenger: So it's called the linked list convergence test. It's probably the most efficient you can get with linked list convergence, but the complexity for it is the same as Floyd's algorithm. They're both of one space, because you only need to track the pointers.
Superimmune Chameleon: Right.
The Legendary Avenger: Time becomes of H, because as soon as you hit the root, you just go back to the nodes, so it still saves you in terms of time complexity. So this is probably the best you'll do with both algorithms. But I wanted. Now you get why I like this problem, because now we've looked at like four techniques in one interview session.
Superimmune Chameleon: Yeah. So it's great.
The Legendary Avenger: Absolutely. But I think this is a good time because we have about nine minutes left. So I know we've talked a lot here, but back to the interview mode. I know we've kind of had a bit of idea sharing, too, but I want you to just look at everything here and tell me, if you were to gauge yourself, what do you think you did well, and what do you think you could improve on.
Superimmune Chameleon: Well, I suppose that I did all right, establishing some test cases and sort of making sure that I understood the nature of the question and what we were essentially trying to solve for. I think in a very rudimentary, naive solution. I was stumbling on some basic things that I think are just a matter of practice in terms of like how do I quickly set up a helper to get me to the root node, or just basic traversal things, which I will work on. But it was probably the implementation of the ideas that was trickiest for me. Yeah, I guess that's my assessment.
The Legendary Avenger: Makes sense. And for the most part, my feedback is in alignment with you. It's quite apparent that, yes, this is maybe the first time you're delving into this kind of practice. And I get it. Typically when you're ft, it's really hard to justify spending time on stupid puzzles like this. Now that said, you do need the practice. I feel like it will help you long term to, you can see this, it's a combination of three techniques you could use and they can all help. And in fact, if you even knew about being such, there is a way we can probably also leverage it to speed up even the algorithm so that it's somehow log H. But point to it is the practice will help you identify common techniques. And when you're doing practice, don't focus on problems, you want to focus on techniques. Binary search this case, you've seen Floyd's algorithm. Those techniques come in handy because then you usually slot problems into buckets of techniques and then automatically solve them. So on your side, I'll add you to look into a collection of techniques. And not to worry, I'll give you a list of resources that break them down. So with graph problems, there's usually a number of techniques you can use. By technique, I mean the likes of DFS, just having a sense of template code, I can throw at a problem, backtracking the likes of that. So if you practice the general technique, get that breath, then you can start delving deep question by question and upping your comfort with the complexities in this case. Now, the other piece of feedback I'll give you is more. So with respect to interview style, you want to take lead, especially at senior and above. For junior and mid level, you're given a lot more leeway. Typically the interview will be happy to give guidance on when to do things now. Complexity analysis as an example, I should not, at least at senior, remind you to do that. You should automatically take charge and do it now. Well, in this case I gave you the hint on test cases, at least for interview note, like in this case I wasn't really going to penalize it because I gave the example. But when you're in interviews, take charge immediately, build your own tree. And this was good. It was good that you immediately picked up the intuition on the how to. Now, in the interview, either you use this approach, you can use adjacency list, it's really up to you. But define how you expect your input to look like, because I think in this case you actually did a good job because you even specified what the input should look like. You said it will be node, et cetera. But in the interview, what you want to do is immediately take charge, build the examples, define your scope, define your domain models, and then start with the problem. Does this make sense?
Superimmune Chameleon: Yes, definitely. That's great advice. Thank you.
The Legendary Avenger: Yes. And then the final piece of advice here will be make sure you refine those common terminologies, especially if it's trees. We know things like height, depth and all that. That way you can even express the complexities in terms of those terms. Not only do they help you be more accurate, but you want to showcase, you want to at least boast a bit about that knowledge, show that you have it while doing the analysis. So that way the interviewer doesn't have any reason to knock you down or even doubt that you might know some of these concepts, because clearly you have the intuition for height. So you might as well refer to height when doing that analysis.
Superimmune Chameleon: Yes, definitely.
The Legendary Avenger: All right. And I forgot this one. I really like recursion, but it felt out of place here. I don't know how you feel like looking at the loops here. Do you think maybe the recursive approach was a bit overkill?
Superimmune Chameleon: Yes, definitely. Like I said, I just don't have that many problems under my belt. And when you did the comment here of the iterative traversal, it was just so much simpler. It made a lot more sense to do it this way. So, yeah, it's a good point for sure.
The Legendary Avenger: Yes, and this again, I noted it in the feedback, and I'll paste the notes for you, not listing the form there alongside the resources. But yeah, always go for simplicity. So loops instead of recursions whenever you can, because trust me, they can trip you up, especially when you start working with recursions that require return values. Yeah, I usually avoid that. In this case, I was noting an example. You see how we used an external object to populate it instead of passing it as a parameter. Not only is that more efficient, but it's simpler to read. But even then, a loop was probably even simpler than even going that route. So, overall, these are things that you'll pick up with practice. So it's more or less what you need is practice getting those core terminologies right and just getting problems under your belt, because at the moment, you're on the right track. I can tell you already have strong fundamentals, so it's just about practicing and getting them refined. Does this make sense?
Superimmune Chameleon: Yeah. Thanks so much. I just wanted to give you the feedback that your teaching style is really excellent. I could have really enjoyed just even another hour of this, so I really enjoyed this session, and thank you very much.
The Legendary Avenger: Absolutely. I'm one of the dedicated coaches that you see. They try to advertise hard here, so we do make sure we have a refined curriculum, and I really enjoyed showing people this new technique, so I'm glad you enjoyed it, and hopefully you learned something from it.
Superimmune Chameleon: Definitely. Yeah. Thank you so much.
The Legendary Avenger: Absolutely. Thank you, man. And, yeah, have a good day.
Superimmune Chameleon: Yeah, you too. Thank you. Bye.