How should I practice Merge Sort Report with a Noisy Comparator?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Mercor onsite interview problems in FastPrep.

Is Merge Sort Report with a Noisy Comparator associated with Mercor?

FastPrep tags this as a Mercor onsite interview coding practice problem when the problem catalog has that company and stage context.

Merge Sort Report with a Noisy Comparator

Mercor● MediumFULLTIMEONSITE INTERVIEW

Learn

Problem statement

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.