FastPrepMerge Sort Report with a Noisy Comparator
Problems/Merge Sort Report with a Noisy Comparator

Merge Sort Report with a Noisy Comparator

Mercor logoMercor● MediumFULLTIMEONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The interview report asks for sorting through a comparator that is correct about 90 percent of the time and costs one cent per call, then reporting accuracy and cost. The practice adapter supplies the realized wrong pairs, fixes bottom-up merge sort as the algorithm, and defines pairwise accuracy in basis points so every run is deterministic.

You must sort distinct integer-valued objects in descending order by using a comparison service. The service is usually correct but is wrong for a stable set of unordered value pairs. Calling it again on the same pair returns the same result.

For deterministic practice, wrongPairs lists the unordered pairs for which the service reverses the true numeric comparison. Every other pair is compared correctly.

Run the specified bottom-up merge sort. Start with runs of width one, double the width after every pass, and merge adjacent runs from left to right. During a merge, call the service once whenever both runs still have a front value; place the value reported as greater first. Append a remaining suffix without another service call.

Return a string array containing the produced values as decimal strings, followed by accuracyBasisPoints=<value> and costCents=<value>.

Accuracy is the fraction of all unordered value pairs that appear in the correct descending relative order, multiplied by 10,000 and rounded to the nearest integer with halves rounded up. A list with fewer than two values has accuracy 10,000. Each comparison-service call costs one cent.

Function

noisyMergeSortReport(values: int[], wrongPairs: int[][]) → String[]

Examples

Example 1

values = [4,1,3,2]wrongPairs = []return = ["4","3","2","1","accuracyBasisPoints=10000","costCents=5"]

All five comparisons are correct, so merge sort produces the true descending order and all six unordered pairs are ordered correctly.

Example 2

values = [4,1,3,2]wrongPairs = [[4,3]]return = ["3","4","2","1","accuracyBasisPoints=8333","costCents=5"]

The comparison between 4 and 3 is reversed. The produced order has one inverted pair out of six, so its rounded accuracy is 8,333 basis points.

Example 3

values = [7]wrongPairs = []return = ["7","accuracyBasisPoints=10000","costCents=0"]

A one-value list requires no comparison and is fully accurate by definition.

Constraints

  • 1 <= values.length <= 2000.
  • Every value is distinct and lies between -1000000000 and 1000000000.
  • Each row of wrongPairs contains two distinct values from values.
  • No unordered pair appears more than once in wrongPairs.

More Mercor problems

  • Expected Fake-Name CollisionsPHONE SCREEN · Seen Oct 2026
  • Length of a Document Reached Through a Random TokenPHONE SCREEN · Seen Oct 2026
  • Precision of Stacked PII Detector FlagsPHONE SCREEN · Seen Oct 2026
All Mercor interview questionsSee Mercor hiring insights
Saved
class Solution {
    public String[] noisyMergeSortReport(int[] values, int[][] wrongPairs) {
        // Write your solution here.
    }
}
Checking account…