Merge Conflicts [Microsoft Python Interview Question]

Imagine you are working on a code version-control system website, similar to GitHub.

You are given a list of , and each element within the list represents a range of lines which that were changed in a specific pull request.

Your job is to write a function called which returns or , depending on if there is or is not any merge conflict. In this case, a merge conflict means two different pull requests are trying to change the same exact lines.

For example, if you were given the input .

We'd output because there is a merge conflict: two different pull requests trying to change lines between 25 and 40.

Here's another example: say you had the input .

You'd return because there is no merge conflict – none of these pull requests are trying to change the same lines.

The brute-force solution is to compare every pull request in the list, and see if they conflict with each other (i.e. if the lines change in the pull request overlap).

Here's started code for that, to generate the two different pull requests we'll compare:

Now comes the crux of the problem – how do we tell if two pull requests edited overlapping parts of the same file?

Well, let's first think about all the cases that could occur when comparing two PRs:

first_pr Starts First

Let's say 's starting line changes comes first. This represents the first 3 cases in the earlier photo (where is represented as A and is B).

We know overlaps the first IF the starts while the isn't over yet!

Expressed in code, we know there's an overlap if .

Putting this together:

Now, what about the other case – when the 's line changes come earlier than ?

second_pr Starts First

Let's say 's starting line changes comes first. This represents the 3 cases below, where is B:

We'll follow similar logic to detect an overlap.

We know overlaps IF the starts while the isn't over yet!

Expressed in code, we know there's an overlap if .

Here's a snippet we can use:

Putting these two cases together, yields us this final output:

The time complexity is $O(n^{2})$ because we are looking at all pairs of $n$ line change ranges.

Can you think of a faster solution? Hint: it requires sorting the input by the line starts!