0

Closest latency pairs by minimum absolute difference

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Closest latency pairs by minimum absolute difference

Companies: Tesla

Difficulty: Easy

Problem statement

A monitoring service records latency readings (whole milliseconds) and wants to flag readings that are suspiciously close to one another.

Implement min_abs_diff_pairs(latencies: list[int]) -> list[list[int]].

  • Let d be the smallest value of |a - b| over all pairs of readings taken from two different positions in the array.
  • Return every pair of values [a, b] with a <= b and b - a == d.
  • Sort the result in ascending order by a, then by b.
  • Readings can repeat. In that case d is 0. List each repeated value once as [v, v], not once for each pair of positions.
  • Return [] if there are fewer than two readings.

Constraints: 0 <= len(latencies) <= 10^5; -10^9 <= latencies[i] <= 10^9.

Example 1

Input:  [40, 12, 31, 18, 33]
Output: [[31, 33]]

The smallest gap is 2, and only 31 and 33 are that close.

Example 2

Input:  [9, 9, 3, 3, 3, 20]
Output: [[3, 3], [9, 9]]

Repeated readings make the smallest gap 0, so each repeated value is listed once.

Start with a simple approach, then improve it. Be ready to discuss repeated values and streaming input.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

Key idea: after sorting, the closest pair is always adjacent. If a <= b <= c, then c - a = (c - b) + (b - a), so it is at least as large as either adjacent gap. Any non-adjacent pair is therefore never strictly closer than some adjacent pair, and the minimum gap can only come from neighbours in sorted order.

Brute force (say it, then move on). Check every pair (i, j), track the smallest |x[i] - x[j]|, and collect the pairs that hit it. That is O(n²) time. It is correct, but at 10⁵ readings it is about 5·10⁹ comparisons.

Optimal: sort, then do one pass.

  1. Sort the values.
  2. Walk the adjacent gaps v[i+1] - v[i]. Keep the best gap seen so far and the list of pairs that reach it.
    • If the gap is smaller, it becomes the new best and the list restarts with this pair.
    • If the gap is equal, append the pair.
  3. The pairs come out in ascending order already, because we visit them left to right.

Duplicates. Real latency data repeats values, so the minimum gap can be 0. We return distinct value pairs: [v, v] appears once if v occurs two or more times, not once per index pair. Handle this in a single pass by skipping equal neighbours after the first [v, v]. (If the interviewer wants index pairs, see Follow-ups.)

Invariants during the scan:

  • best is the smallest adjacent gap in v[0..i].
  • pairs holds exactly the distinct adjacent value pairs in that prefix whose gap equals best, in ascending order.

A one-pass version needs no second loop. A two-pass version (first find the minimum gap, then collect the pairs) is equally fine in an interview and is a bit harder to get wrong.

Code

from collections import Counter
from typing import List, Tuple


def min_abs_diff_pairs(latencies: List[int]) -> List[List[int]]:
    """Return all distinct value pairs [a, b] (a <= b) whose difference
    equals the minimum absolute difference over all pairs.

    Pairs are sorted ascending. Fewer than two values gives [].
    """
    if len(latencies) < 2:
        return []

    values = sorted(latencies)
    best = float("inf")
    pairs: List[List[int]] = []

    for i in range(1, len(values)):
        lo, hi = values[i - 1], values[i]
        gap = hi - lo
        if gap < best:
            best = gap
            pairs = [[lo, hi]]
        elif gap == best:
            # With gap 0, a run like 5,5,5 would add [5,5] twice.
            if pairs[-1] != [lo, hi]:
                pairs.append([lo, hi])

    return pairs


def min_abs_diff(latencies: List[int]) -> int:
    """Just the minimum gap; useful when the caller only needs the number."""
    values = sorted(latencies)
    return min(b - a for a, b in zip(values, values[1:]))


def min_abs_diff_index_pair_count(latencies: List[int]) -> Tuple[int, int]:
    """Follow-up: (min gap, number of index pairs (i < j) reaching it)."""
    values = sorted(latencies)
    best = min(b - a for a, b in zip(values, values[1:]))
    counts = Counter(values)
    if best > 0:
        # Values at distance best are distinct, so pair count is count(v) * count(v + best).
        return best, sum(c * counts.get(v + best, 0) for v, c in counts.items())
    # best == 0: every group of equal values of size c gives c choose 2 pairs.
    return 0, sum(c * (c - 1) // 2 for c in counts.values())


if __name__ == "__main__":
    assert min_abs_diff_pairs([40, 12, 31, 18, 33]) == [[31, 33]]
    assert min_abs_diff_pairs([7, 1, 4, 10]) == [[1, 4], [4, 7], [7, 10]]
    assert min_abs_diff_pairs([5]) == []
    assert min_abs_diff_pairs([]) == []
    assert min_abs_diff_pairs([9, 9, 3, 3, 3, 20]) == [[3, 3], [9, 9]]
    assert min_abs_diff_pairs([-6, -2, 2, -4]) == [[-6, -4], [-4, -2]]
    assert min_abs_diff_pairs([100, 1]) == [[1, 100]]
    assert min_abs_diff([7, 1, 4, 10]) == 3
    assert min_abs_diff_index_pair_count([3, 3, 3, 9, 9]) == (0, 4)
    assert min_abs_diff_index_pair_count([1, 2, 2, 3]) == (0, 1)
    assert min_abs_diff_index_pair_count([1, 3, 3, 5]) == (0, 1)
    assert min_abs_diff_index_pair_count([1, 2, 4, 5]) == (1, 2)
    print("all tests pass")

Complexity

  • min_abs_diff_pairs: O(n log n) time for the sort, plus O(n) for the scan. O(n) extra space for the sorted copy and the output (the output can hold up to n − 1 pairs, for example an arithmetic sequence).
  • If you may sort in place, the extra space drops to O(1) beyond the output (Python's Timsort may still use O(n) scratch space).
  • If values lie in a small known range (latencies in whole milliseconds under, say, 10⁶), counting sort makes the whole thing O(n + range).
  • min_abs_diff_index_pair_count: O(n log n) time, O(n) space for the counter.

Test cases

  • [40, 12, 31, 18, 33] → [[31, 33]] (single closest pair, input unsorted)
  • [7, 1, 4, 10] → [[1, 4], [4, 7], [7, 10]] (every adjacent gap ties)
  • [100, 1] → [[1, 100]] (two values form the only pair)
  • [5] → []; [] → [] (fewer than two values)
  • [9, 9, 3, 3, 3, 20] → [[3, 3], [9, 9]] (minimum gap 0; each repeated value listed once)
  • [-6, -2, 2, -4] → [[-6, -4], [-4, -2]] (negative values)
  • Large: 10⁵ random values in [0, 10⁹] finishes well under a second; compare against the O(n²) brute force on small random arrays.

Follow-ups

  1. Return index pairs, or count them. With duplicates the answer changes. For gap 0, a value occurring c times gives c·(c−1)/2 index pairs. For a gap d > 0, the count is count(v) · count(v + d) summed over values v. Listing the actual index pairs means sorting (value, index) tuples and expanding the groups. That can be O(n²) output, so ask whether a count is enough.
  2. Streaming readings. Latencies arrive one at a time and you report the current minimum gap after each one. Keep the values in a sorted structure (sortedcontainers.SortedList, or a balanced BST). On insert, only the gaps to the new neighbours change, so each insert costs O(log n). Deletions (a sliding time window) are harder, because the old minimum may disappear. Keep a multiset of the adjacent gaps as well: delete the gaps on either side of the removed value and add the gap between its old neighbours.
  3. Pairs within a threshold t, not just the minimum. Sort, then use two pointers or a binary search for each left element to list or count all pairs with b − a <= t. Counting is O(n log n). Listing is output-sensitive.
  4. Closest pair across two arrays (for example, two data centres). Sort both and merge with two pointers, comparing a[i] with b[j] and advancing the smaller one. This runs in O(n log n + m log m).
  5. k smallest gaps or the k-th smallest pair distance (LeetCode 719). Binary search on the distance d, and count the pairs <= d with two pointers in O(n) per check. This runs in O(n log n + n log W).

Interviewer expectations

Mid-level (L4)

  • States the brute force and its cost, then moves to sort-and-scan quickly.
  • Explains why only adjacent elements need checking.
  • Writes clean, bug-free code that handles fewer than two elements and returns pairs in sorted order.

Senior (L5)

  • Asks right away about duplicates, negative values and the output format (values or indices), and decides how duplicates are handled.
  • Gives the one-pass version or a clean two-pass version and tests both tie and zero-gap cases.
  • Discusses counting sort for bounded latency values and the O(n) worst-case output size.

Staff (L6+)

  • Turns the problem toward real monitoring: streaming inserts with a sorted structure, sliding-window deletion with a gap multiset, and the memory limits at high event rates.
  • Separates counting from listing (output-sensitive bounds) and knows the binary-search-on-answer pattern for k-th distance.
  • Mentions practical concerns: float latencies and tolerance-based equality, and why approximate methods such as bucketing by resolution can replace exact sorting.

Sign in to comment, vote or remix.