How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Minimize Branch Merge Conflicts | Amazon Coding Question

Q: Minimize Branch Merge Conflicts

This question evaluates understanding of combinatorial optimization, set operations, and order-dependent state management, requiring reasoning about how commit file modifications accumulate across branch merges.

Minimize Branch Merge Conflicts

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Take-home Project

You are given several feature branches that must all be merged into the main branch. Each branch contains a sequence of commits, and each commit modifies one or more file paths. Implement `minMergeConflicts(branches) -> int`. - `branches[i][j]` is the list of file paths modified by the `j`-th commit in branch `i`. - You may choose any order in which to merge the branches. - The first merged branch has zero conflicts. - When merging a branch after some other branches have already been merged, a commit in the current branch is counted as a conflicting commit if it modifies at least one file path that has already been modified by any previously merged branch. - A commit counts at most once, even if it touches multiple already-modified files. - After a branch is merged, all files modified by all of its commits are considered modified for future merges. Return the minimum possible total number of conflicting commits after merging all branches. Example: `branches = [[['a'], ['b']], [['b'], ['c']], [['a', 'c']]]` One optimal order is branch `0`, then branch `1`, then branch `2`: - Merge branch `0`: `0` conflicts. - Merge branch `1`: commit `['b']` conflicts, commit `['c']` does not, so `1` conflict. - Merge branch `2`: commit `['a', 'c']` conflicts, so `1` conflict. The minimum total conflict count is `2`. Assume the number of branches is small enough for subset dynamic programming, for example `n <= 15`.

Quick Answer: This question evaluates understanding of combinatorial optimization, set operations, and order-dependent state management, requiring reasoning about how commit file modifications accumulate across branch merges.

Constraints

1 <= number of branches n <= 15 (small enough for subset/bitmask DP).
Each branch has at least one commit; a commit modifies zero or more file paths.
File paths are arbitrary strings; the same path may appear across different branches and commits.
Duplicate paths within a commit or branch are treated as a single file (idempotent).
The answer is the minimum total conflicting-commit count over all merge orders.

Examples

Input: ([[['a'], ['b']], [['b'], ['c']], [['a', 'c']]],)

Expected Output: 2

Explanation: Worked example. Order 0->1->2: branch 0 is 0 conflicts; branch 1's ['b'] conflicts (1); branch 2's ['a','c'] conflicts (1). Total 2, the minimum over all orderings.

Input: ([],)

Expected Output: 0

Explanation: No branches to merge, so zero conflicts.

Input: ([[['x'], ['y'], ['z']]],)

Expected Output: 0

Explanation: A single branch is always the first merged, which has zero conflicts regardless of its commits.

Input: ([[['a']], [['b']], [['c']]],)

Expected Output: 0

Explanation: Three branches touching disjoint files. No commit ever hits an already-modified file, so any order yields 0.

Input: ([[['a']], [['a']], [['a']]],)

Expected Output: 2

Explanation: All three branches touch 'a'. First branch 0 conflicts; each subsequent branch's single commit hits the modified 'a' (1 each). Order cannot avoid the 2 conflicts.

Input: ([[['a'], ['a']], [['a'], ['a']]],)

Expected Output: 2

Explanation: Both branches touch only 'a' but have two commits each. Whichever branch is merged second has both of its commits conflict on 'a' (a commit touching ['a','a'] still counts as touching 'a' once), giving 2.

Input: ([[['shared']], [['shared'], ['x'], ['y']], [['shared']]],)

Expected Output: 2

Explanation: Merge the wide branch first (0 conflicts), then the two single-commit 'shared' branches each conflict once: 0 + 1 + 1 = 2. Merging it last would cost 1 (its 'shared' commit) but leave the two 'shared' branches contributing 1, so 2 is the minimum either way here.

Input: ([[[]], [[]]],)

Expected Output: 0

Explanation: Two branches whose only commit modifies no files. An empty commit can never intersect the modified set, so total conflicts is 0.

Hints

Only the SET of already-merged branches matters for future cost, not the order they were merged in — the union of their modified files is order-independent. This collapses n! orderings into 2^n subsets.
Encode each distinct file path as a bit. Then each commit and each branch is an integer bitmask, and 'does this commit touch an already-modified file?' is a single bitwise AND that is non-zero.
Let dp[S] = min conflicts to have merged exactly the branches in subset S. Transition: for each branch b not in S, dp[S | (1<<b)] = min(..., dp[S] + (commits of b whose mask intersects files(S))). Answer is dp[(1<<n)-1].
Greedy (always merge the branch adding the fewest new conflicts) fails: merging a branch enlarges the modified-file set and raises FUTURE costs. The DP weighs both effects.

Quick Overview

This question evaluates understanding of combinatorial optimization, set operations, and order-dependent state management, requiring reasoning about how commit file modifications accumulate across branch merges.