Lowest Common Ancestor All in One
Info
English content is still improving...
You will not only learn the algorithm tricks, also resolve these LeetCode problems:
Prerequisites
Before reading this article, you should learn:
While written exams often feature challenging problems like dynamic programming and backtracking, interviews tend to focus on more classic and practical questions with moderate difficulty.
This article introduces a classic algorithm problem using Git: the Lowest Common Ancestor (LCA).
We frequently use the git pull
command, which by default merges remote changes into our local repository using the merge
method. If we use git pull -r
, it employs the rebase
method to integrate remote changes.
The most apparent difference between these methods is that merge
results in a branch with many "forks," whereas rebase
produces a linear branch. Regardless of the method, if conflicts exist, Git detects them and prompts you to resolve them manually.
So, how does Git determine if two branches have conflicts?
Taking the rebase
command as an example, consider the scenario below where I am on the dev
branch and execute git rebase master
. The dev
branch will then be attached on top of the master
branch:
Here's what Git does:
First, it finds the Lowest Common Ancestor (LCA) of the two branches. Then, starting from the master
node, it replays the commits from LCA
to dev
. If these changes conflict with the commits from LCA
to master
, Git prompts you to resolve the conflicts manually. The final result is that the dev
branch is fully integrated onto the master
branch.
So, how does Git find the LCA of two different branches? This is a classic algorithm problem, and I will explain it step by step from the basics.