Lowest Common Ancestor All in One

While written exams often feature dynamic programming and backtracking problems that are somewhat challenging, interviews tend to focus on classic problems that are not very difficult and are quite practical.

This article introduces a classic algorithm problem using Git: the Lowest Common Ancestor (LCA).

We frequently use the git pull command, which by default uses the merge method to bring changes from a remote repository to your local one. If you add the -r parameter with git pull -r, it uses the rebase method to incorporate remote changes locally.

The most intuitive difference between these two methods is that a branch merged with merge will display many "forks," whereas a branch merged with rebase appears as a straight line. However, in both methods, if conflicts exist, Git will detect them and prompt you to resolve them manually.

So, the question arises: How does Git detect conflicts between two branches?

Take the rebase command as an example. Consider the scenario illustrated below, where you execute git rebase master while on the dev branch, and then dev is positioned on top of the master branch:

In this process, Git operates as follows:

First, it identifies the Lowest Common Ancestor (LCA) of the two branches. Then, starting from the master branch node, it replays the modifications from LCA to dev. If these modifications conflict with the commit from LCA to master, you will be prompted to manually resolve the conflicts. The final result is that the dev branch is fully integrated on top of the master.

So, how does Git find the Lowest Common Ancestor of two different branches? This is a classic algorithm problem, and I will explain it step by step.