Closest Pair Between Two Arrays | Dataford Interview Questions

C-edge's transaction monitoring pipeline receives two unsorted arrays of integer values from separate processing stages. Given arrays a and b, find one value from each array whose absolute difference is as small as possible.

Return the pair as [x, y], where x comes from a and y comes from b. If multiple pairs have the same minimum difference, return the lexicographically smallest pair: choose the smaller x, then the smaller y.

Formal Specification

Implement closest_pair(a, b).

Input: two non-empty lists of integers, a and b.
Output: a two-element list [x, y] such that x belongs to a, y belongs to b, and abs(x - y) is minimal.
Do not modify the input arrays.

Constraints

1 <= len(a), len(b) <= 10^5
-10^9 <= a[i], b[j] <= 10^9
Duplicate values may occur
Both arrays are non-empty

Function Signature

def closest_pair(a, b):

Your question is Closest Pair Between Two Arrays. 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