Problem · Dynamic Programming
Minimum Merge Conflicts
See Amazon hiring insightsProblem statement
Developers want to merge two source-control branches into one unified branch while preserving the relative order of commits from each branch.
Each branch is represented by a lowercase string. Each character represents a commit priority, where a lower alphabetical character has higher priority.
A conflict occurs when, in the merged branch, a lower-priority commit appears before a higher-priority commit. In other words, for positions i < j in the merged string, there is a conflict when merged[i] > merged[j].
The problem statement continues
ProExamples
Example 1
primary = "zc"secondary = "d"return = 2Valid merges include:
zcdwith2merge conflicts (zbeing lower priority is placed before higher priority commitscandd).- Similarly,
zdcwith3merge conflicts. - Similarly,
dzcwith2merge conflicts.
The minimum number of merge conflicts possible is 2.
3 original screenshots from the interview report
ProFastPrep Pro
Reported in 1 Amazon interview this weekUnlock the full problem
- Full problem statement and constraints
- 2 more worked examples, explained
- Guided hints and editorial
- Run your code on real test cases
$9/month
Pro subscription, billed yearly — or $19 month-to-month. Cancel anytime.
Free plan — 2 of 2 free unlocks used this week