How should I practice Top K With a Deterministically Noisy Comparator (MLE)?

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

Is Top K With a Deterministically Noisy Comparator (MLE) associated with Mercor?

FastPrep tags this as a Mercor coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Array

Top K With a Deterministically Noisy Comparator (MLE)

Learn this problem

● HardMercorFULLTIMEONSITE INTERVIEW

Problem statement

Source note: 🍉 This practice version is an 85-90% match to the reported Mercor MLE full-time onsite prompt when judged by core task and follow-up coverage. It keeps the main setup of n numbers, a noisy cmp(a, b), and finding the top k; it keeps the 10% deterministic error behavior; it explicitly says that repeating the same comparison does not reduce the error; and it preserves the 45-minute coding-interview framing plus both follow-ups: minimizing comparator calls and minimizing wall-clock time when each call takes about 5 seconds. 🍊 The parts FastPrep had to clarify are the probabilistic model and output contract. The original source did not fully specify whether the 10% corruption is per unordered pair or per ordered pair, so this version assumes independent corruption per unordered pair to make the discussion well-defined. The high-confidence top-k versus exact-impossible framing is also a FastPrep clarification inferred from the prompt. If you are scoring by word-for-word reconstruction, this is closer to 75-80%; if you are scoring by core interview path and follow-up intent, it is 85-90%.

You are given n numbers and a comparator function cmp(a, b). The comparator is intended to compare two numbers, but it is unreliable.

The comparator has a 10% chance of returning the wrong result. The error is deterministic for the same arguments: if cmp(x, y) is wrong once, calling cmp(x, y) again returns the same wrong result.

Given an array of numbers and an integer k, design and implement a function that returns the top k largest numbers.

List<Integer> topK(int[] nums, int k)

Because the comparator can be wrong, your answer should explicitly state what guarantee you are targeting: exact correctness if possible, or a high-confidence result under a probabilistic error model.

FastPrep executable note: The original interview discussion focuses on comparator strategy, not output ordering. To make the workspace checker deterministic, return the selected top-k values in descending numeric order.

Comparator Contract

cmp(a, b) < 0  means a is smaller than b
cmp(a, b) > 0  means a is larger than b
cmp(a, b) = 0  means a and b are equal

Repeating the same comparison does not reduce the error probability, because the mistake is deterministic for the same pair.

Important Assumption To Clarify

Unless the interviewer states otherwise, assume each unordered pair of values has an independent corrupted comparison result with probability 10%. Once a pair is corrupted, all future calls on that same pair return the same corrupted result.

If the comparator can be adversarially wrong, or if no probabilistic model is available, exact top-k correctness cannot be guaranteed in general.

Clarifications / Corner Cases

k = 0: return an empty list.
n = 0: return an empty list.
k >= n: return all numbers.
Duplicate values may appear.
The original prompt did not require sorted output unless the interviewer asks for sorted top-k; this FastPrep version returns descending order for deterministic checking.
Calling cmp on the same pair multiple times is not useful for reducing error.
The comparator may appear inconsistent because different pairwise results may be corrupted.
If the error model is adversarial, exact correctness cannot be guaranteed in general.
If errors are random per pair, the algorithm can aim for high-confidence top-k.
The algorithm should avoid unnecessary comparator calls.
Comparator calls may be very slow.

Follow-up A - Minimize Comparator Calls

How would you minimize the number of calls to cmp(a, b)? Discuss the tradeoff between doing fewer comparisons and collecting enough independent evidence to handle a noisy comparator.

Follow-up B - Slow Comparator Calls

Assume each call to cmp(a, b) takes about 5 seconds. How would you minimize actual wall-clock runtime?

Which comparisons can be run in parallel?
How would you batch independent comparator calls?
How would you cache pairwise results to avoid duplicate calls?
How would you reduce long sequential dependency chains?
How would your design change if you can use async workers or distributed execution?

Function

topK(nums: int[], k: int) → int[]

Examples

Example 1

nums = [10, 8, 3, 20, 15]k = 2return = [20, 15]

True top 2: [20, 15].

A standard comparator-based top-k algorithm may return the true top 2, but a wrong comparison near the top-k boundary can cause an incorrect result.

Example 2

nums = [5, 1, 4, 3, 2]k = 3return = [5, 4, 3]

True top 3: [5, 4, 3].

If cmp(4, 3) is wrong, calling cmp(4, 3) repeatedly will still return the wrong answer. A robust approach must rely on information from other comparisons, not repeated calls to the same pair.

Example 3

nums = [100, 99, 98, 1, 0]k = 3return = [100, 99, 98]

True top 3: [100, 99, 98].

The most important uncertainty is often around the boundary between rank k and rank k + 1. A single corrupted comparison involving boundary candidates may change the returned set.

Constraints

0 <= nums.length <= 100,000
0 <= k <= nums.length
cmp(a, b) is deterministic for the same ordered arguments.
The cost of cmp may dominate all other computation.