Name: Microsoft Coding Interview Question and Answer: Lowest Common Ancestor
Uploaded: 2020-03-28T16:25:33.000Z
Duration: 7 min 5 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

To-infinitive

in this video, I'm going to discuss a Microsoft interview question and answer on This problem is called the lowest common ancestor problem.

The imperative

We have a tree, as you can see on the left on were given two elements four and five and we're trying to find the common out sister That's the lowest in level in this case.

The answer would be three because we have two common ancestors for these two elements one on three and obviously three is so lower.

The lowest common ancestor of three and 53 and five would be three again.

So l see a could be one of the given moments on the L C.

Off for two warrant too would be one and then l c a.

The same element would be this Ellman itself.

If you want to try solving this problem yourself, Pulis a video right here and see if you can come up with a solution on.

There's a number of solutions to this problem, but the one I find the simplest is the following.

Let's say we're trying to find the L C A.

That lowest common ancestor off four and five.

What I would do first is I would find the past from the root to one of the elements for Let's say I do that by going to the left and then left again on right there I find the element.

So the past to that lemon would be 14134 on.

So I go to the right, left again and I find the paths.

So that's 13 65 on By examining these two paths 134 on 1365 We see that these two paths are the same up on 23 convert or divers after that.

So in these two paths, we can see these two elements are the same.

So we return the last element in this common pass as the L C.

Now, the key to implement in this solution is dysfunction past X.

It takes the route on the element that we're looking for X or five in this case on it returns a stack off this past or he returns this past as a stack.

I'm just gonna write it as a list for now and then something for this one for so the past is once before.

And given these two paths were able to look at each Ellman at a time.

Andi, see which ones are the same until we find different elements.

We stopped right here on we can this return discernment as the L C A.

Now, if you want to try implementing this ocean yourself policy video right here on, come back to you later.

When you're done, Here's my implementation to our solution and in particular, the past two x function.

Let's say, as an example, we're trying to find the past from mood too.

Five, this woman on behalf of recursive solution here if the element or the route that we're looking at right now is no then we just returned.

If we're looking at the element that we were just looking for, If boo dot value is equal to this one, then we create a stack ways, this element alone and then we return that on.

Let's say we're looking at December now on if the left past or if the left child contends a pass to X, then that means left past is going to be not now.

And so we return left past after adding their current element that we're looking at this one to the left past.

And then we returned that and we do the same thing with the right pass.

If the right child contends the past two eggs or five in this case, then we add the current value to the right pass and then we return that if neither Children contained a pass to the element that we're looking for, if we're looking at this home and say, then we just returned no now, using the code that we just implemented, let's just implement our main function.

L see A that takes root on the two elements on Let's call them J and K and in particular will be looking at this example off the L C.

Now, the first thing we do is we find the paths to Dan Kate or 45 which would be these two.

And then we initialized Elsey aide to return as snow or anything else.

And while Pastor J and Pass A K are non empty, we pop these two stacks or these two paths on call them J pop and K pop and popping just means we take the first settlement.

And if these two elements J pop on Cape Up are the same element, then we update Elsey aide to return to that element.

So Elsie had to return, becomes one and then three because thes two elements are still the same.

And then we stop right here when these two elements J pop and Cape Up are not equal on break.

We return L c A to return in this case three as the L C A.