Merge overlapping corrections

Q: Merge overlapping corrections

This question evaluates a candidate's ability to manage and manipulate overlapping intervals with multi-criteria tie-breaking, preserve original metadata across splits, and design efficient data structures and algorithms for producing non-overlapping correction spans.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Q: What difficulty level is this interview question?

This is a none difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Grammarly.

Q: What role is this question designed for?

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

Question

Implement correctionMerge(corrections).

You are given a list of text-correction spans. Each correction applies to an inclusive interval [start, end] and has the following fields:

start: int — inclusive start index
end: int — inclusive end index
priority: int — higher value means higher priority
change: enum — the modification to apply, such as DELETE , DEDUP , UPDATE , UPPERCASE , or LOWERCASE

Return a list of corrections such that no two output corrections overlap.

When two corrections overlap, resolve the overlap using these rules for every covered position:

The correction with the higher priority wins.
If priorities are equal, the correction with the smaller original span length (end - start) wins.
If both are still equal, preserve the earlier correction in the input order.

If a correction loses only part of its interval, split it into the remaining non-overlapping pieces.

Important detail: if an interval is split, every fragment must keep the metadata of the original correction for future comparisons, including its original priority, input order, and original span length. In other words, after splitting (1,10,1,UPPERCASE) into (1,2,...) and (7,10,...), later tie-breaking must still treat both fragments as coming from the original span (1,10), not from shorter spans (1,2) or (7,10).

Example:

input: (1,10,1,UPPERCASE) , (3,6,1,LOWERCASE)
output: (1,2,1,UPPERCASE) , (3,6,1,LOWERCASE) , (7,10,1,UPPERCASE)

Assume the number of corrections can be large, so iterating over every character position is not allowed. Return the minimal sorted list of non-overlapping output segments.

Merge overlapping corrections

Quick Overview

Comments (0)