Katkat
Back

Fewest Severity Inversions When Interleaving Two Patch Queues

AmazonSoftware Engineer · Online Assessment
HardSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Merge two severity-labeled patch queues into one install order that keeps each queue's internal order, and return the minimum number of severity inversions over every valid merge. Tests DP over two sequences and efficient counting with letters as priorities.

Two fleets are each running their own queue of pending firmware patches, written as a string of lowercase letters. The letter is the patch's severity: 'a' is the most critical, 'z' the most trivial. You must merge queue_a (length m) and queue_b (length n) into a single install order of length m + n that uses every patch from both queues exactly once and preserves each queue's own relative order — the merged order is an interleaving of queue_a and queue_b.

A severity inversion is a pair of positions in the merged order where a less severe patch is installed before a more severe one. For example, in the merged order "zab", the 'z' (trivial) is installed before both 'a' and 'b' (both more severe), giving 2 inversions. Return the minimum number of inversions achievable over every valid merge.

Function Signature

def min_merge_conflicts(queue_a: str, queue_b: str) -> int:

Rules

  • The merged order must use every character of both inputs exactly once, each in its original relative order within its own queue.
  • An inversion is a pair of indices x < y in the merged order with merged[x] > merged[y] alphabetically. Equal letters never form an inversion.
  • Inversions between two patches that both came from the same input queue count too, even though no merge can change their relative order — they are unavoidable and present in every valid merge.
  • Return only the minimum count, not the merged order itself.

Constraints

  • 1 <= m <= 1000 and 1 <= n <= 1000.
  • Both strings contain only lowercase English letters.
  • The answer fits comfortably in a 32-bit signed integer.

Examples

Example 1

Input:  queue_a = "fd", queue_b = "e"
Output: 2

The three possible merges are "efd" (2 inversions), "fed" (3 inversions) and "fde" (2 inversions).

Example 2

Input:  queue_a = "hg", queue_b = "pc"
Output: 4

The merge "hgpc" achieves 4 inversions (h-g, h-c, g-c, p-c), and no valid merge does better.

Example 3

Input:  queue_a = "k", queue_b = "k"
Output: 0

The only merge is "kk", and equal letters never count as an inversion.

Hints

Hint 1

Split the total into two parts: inversions entirely within queue_a or entirely within queue_b (fixed, computable up front), and inversions between a character of queue_a and a character of queue_b (the only part you control).

Hint 2

A valid interleaving is exactly a monotone way of deciding, for every pair of one character from each queue, which one comes first — think of it as a path through an (m+1) x (n+1) grid.

Hint 3

Define dp[i][j] as the minimum cross-queue inversions after placing the first i characters of queue_a and the first j of queue_b. What does appending queue_a[i] or queue_b[j] next cost you?

Hint 4

You don't need to rescan the placed characters for every transition — precompute, for each prefix, how many letters greater than a given letter it contains.

Follow-up questions

  • How would you reconstruct one merged order that actually achieves the minimum, not just the count?
  • How would the approach change if letters had arbitrary integer priorities instead of being restricted to 26 lowercase letters?
  • Could you solve this in better than O(m*n) time, and if so under what assumptions on the alphabet or the inputs?
  • How would you extend this to merging three or more queues at once?