How would you find the kth smallest sum over all pairs of two sample lists without materializing every pair?

## The problem, and why the obvious route fails A request crosses two hops. You have `n` measured front-hop latencies and `m` measured back-hop latencies, and an end-to-end observation is any front sample plus any back sample. You want the kth smallest end-to-end value across all `n x m` combinations. Building the combinations is `O(n x m)` work and memory before you even sort them — at a few hundred thousand samples per hop that is tens of billions of values, which settles the matter. So do not build them. Search the **values** the answer could take, and use a counting predicate to steer the search. ## The predicate Define `count(x)` as the number of pairs whose sum is at most `x`. It is non-decreasing in `x` by construction: raising the threshold can only admit more pairs, never fewer. That gives the value range the split structure binary search needs — every `x` below the answer has `count(x) < k`, every `x` at or above it has `count(x) >= k` — and the target is the **first** `x` on the at-least-k side. The search range is `[min(A) + min(B), max(A) + max(B)]`. Its width is a property of the measured latencies, not of how many samples there are, so the halving count is the log of that value span. ## Counting without building Sort both lists once, ascending. Then count with two pointers moving in opposite directions: ``` // A and B are sorted ascending countAtMost(A, B, x): count = 0 j = length(B) - 1 for i in 0..length(A)-1: while j >= 0 and A[i] + B[j] > x: j = j - 1 if j < 0: break count = count + (j + 1) return count ``` The invariant is that `j` is the largest index with `A[i] + B[j] <= x`, so every one of `B[0..j]` pairs with `A[i]` under the threshold and contributes `j + 1` at once. Because `A` is ascending, the valid `j` never moves back right as `i` advances, so `j` only ever decreases across the whole run — total work `O(n + m)`, not `O(n x m)`. Once `j` falls below zero, no larger `A[i]` can qualify either, so the loop stops. ## Why the converged value is a real sum This is the step candidates most often distrust: the search walks arbitrary integers in the range, so how can the value it lands on be an actual pair sum? Let `x*` be the smallest `x` with `count(x*) >= k`. Then `count(x* - 1) < k <= count(x*)`, so `count` strictly increased between `x* - 1` and `x*`. But `count` only increases at a value that some pair actually attains — it is a step function whose jumps sit exactly on attainable sums. So at least one pair sums to precisely `x*`, and `x*` is the kth smallest sum. No post-processing, no snapping to the nearest real value. This argument needs integer-valued data. With genuinely real-valued measurements, scale to integers first — latencies in microseconds rather than fractional milliseconds — or accept an epsilon-precision answer, because there is no longer a well-defined `x* - 1`. ## The duplicate trap Use `count(x) >= k`, never `count(x) == k`. Many pairs can share a sum, so `count` can leap from below `k` to well above it in a single step and no `x` ever satisfies equality — a search written around `==` never terminates or returns garbage. Duplicates are the norm here, not an edge case: latency measurements cluster hard. ## Cost Sorting both lists is `O(n log n + m log m)`, done once. Each halving costs one `O(n + m)` sweep, and there are about `log2(R)` halvings where `R` is the value span. Total: `O(n log n + m log m + (n + m) log R)`, with `O(1)` extra space beyond the sort. Set that against `O(n m log(n m))` for materialize-and-sort and the gap is not a constant factor, it is a change of category. ## Recognizing the family The generalizable shape is: a huge implicit collection you can **count** cheaply against a threshold but cannot afford to **enumerate**. Order statistics over pairwise combinations, over a multiplication grid, or over any derived quantity with a monotone counting rule all fit. The interview signal is the sentence "I never build the collection; I only ever ask how many of its members fall at or below a threshold." ## What to watch in an interview State the predicate and its monotonicity before any code. Say why the answer is attainable rather than hoping nobody asks. Name the duplicate handling explicitly. And charge the sort honestly — a candidate who reports the cost as `O((n + m) log R)` and forgets the one-time sort has not actually accounted for the algorithm.