Top-k with Noisy Comparator | Dataford Interview Questions

Given n numbers and a black-box comparison function cmp(a,b) that returns the wrong answer 10% of the time (deterministically, for the same arguments), find the top k elements; discuss the approach verbally.

Asked in the Onsite coding (45 min) stage. Verbal only, no code required per OP reply; exact top-k cannot be guaranteed.

For executable evaluation, cmp is represented as an n x n matrix, where cmp[i][j] is the comparison result for nums[i] and nums[j]: positive means nums[i] ranks higher, negative means lower, and zero means equal. Return the selected elements in descending estimated rank order.

Constraints

0 <= k <= n
1 <= n <= 100
nums contains numeric values
cmp is an n x n matrix containing only -1, 0, or 1
cmp[i][j] represents the deterministic result for nums[i] versus nums[j]
Exact top-k recovery is not guaranteed

Function Signature

def top_k_noisy(nums, k, cmp):

Your question is Top-k with Noisy Comparator. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Asked in the Onsite coding (45 min) stage. Verbal only, no code required per OP reply; exact top-k cannot be guaranteed.

Constraints

0 <= k <= n
1 <= n <= 100
nums contains numeric values
cmp is an n x n matrix containing only -1, 0, or 1
cmp[i][j] represents the deterministic result for nums[i] versus nums[j]
Exact top-k recovery is not guaranteed

Function Signature

def top_k_noisy(nums, k, cmp):

Your question is Top-k with Noisy Comparator. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.