Find latency pairs with minimal difference
Company: Tesla
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an array of integers representing network latencies, return all increasing pairs [a, b] such that b − a equals the minimal absolute difference between any two elements in the array. Return the pairs sorted by a then b. State the time and space complexity of your approach.
Quick Answer: This question evaluates array manipulation, pairwise comparison, and algorithmic efficiency by requiring identification of minimal absolute differences and construction of ordered latency pairs.
Given an array of distinct integers representing network latencies, return all pairs [a, b] such that a < b and b - a is equal to the minimum absolute difference between any two elements in the array. The returned list of pairs must be sorted first by a, then by b. If the array has fewer than 2 elements, return an empty list.
Constraints
- 0 <= len(latencies) <= 100000
- -1000000000 <= latencies[i] <= 1000000000
- All values in latencies are distinct
Examples
Input: ([4, 2, 1, 3],)
Expected Output: [[1, 2], [2, 3], [3, 4]]
Explanation: After sorting to [1, 2, 3, 4], every adjacent pair has difference 1, which is the minimum.
Input: ([1, 3, 6, 10, 15],)
Expected Output: [[1, 3]]
Explanation: The adjacent differences are 2, 3, 4, and 5, so the minimum is 2 from the pair [1, 3].
Hints
- Try sorting the array first. After sorting, the minimum absolute difference can only occur between neighboring elements.
- As you scan adjacent elements in sorted order, keep track of the smallest difference seen so far and rebuild the answer whenever you find a smaller one.