Distinct Value Pairs With a Target Sum in a Sorted Doubly Linked List
Company: Arista Networks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A doubly linked list holds integers sorted in non-decreasing order. Find every pair of nodes whose values add up to a given `target`. As a follow-up, the list may contain duplicate values, and each distinct pair of values must be reported only once.
The list is passed as the values of its nodes from head to tail.
### Function Signature
```python
def pairs_with_sum(values: list[int], target: int) -> list[list[int]]:
```
### Rules
- A pair uses two different nodes. A pair of equal values `[v, v]` therefore needs at least two nodes holding `v`.
- Report each distinct pair of values once, however many node pairs produce it: for `values = [1, 1, 3]` and `target = 4` the answer is `[[1, 3]]`, not two copies of it.
- Write each pair as `[a, b]` with `a <= b`, and sort the pairs by `a` in ascending order. Because `b = target - a`, this order is unique.
- Return an empty list when no pair exists.
### Constraints
- `0 <= len(values) <= 10^5`
- `-10^9 <= values[i] <= 10^9`, and `values[i] <= values[i + 1]` for every valid `i`
- `-2 * 10^9 <= target <= 2 * 10^9`. The target and the sum of two values can fall outside the 32-bit signed range (`-2^31` to `2^31 - 1`), so use 64-bit arithmetic.
### Examples
**Example 1**
```text
Input: values = [1, 2, 4, 5, 6, 8, 9], target = 7
Output: [[1, 6], [2, 5]]
```
`1 + 6` and `2 + 5` reach the target. There is no `3` to pair with `4`.
**Example 2**
```text
Input: values = [1, 1, 2, 3, 3, 3, 4], target = 4
Output: [[1, 3]]
```
Six node pairs (two `1` nodes times three `3` nodes) add up to `4`, but they form one distinct pair of values. `2 + 2` would need two nodes holding `2`, and there is only one.
**Example 3**
```text
Input: values = [-1, 2, 2, 5, 6], target = 4
Output: [[-1, 5], [2, 2]]
```
`-1 + 5 = 4`, and the two nodes holding `2` form the pair `[2, 2]`.
Overview: Find every pair of nodes in a sorted doubly linked list whose values add up to a target, then handle duplicate values so that each distinct pair of values is reported once. The problem tests working with sorted linked structures, pairs of equal values and a canonical output order.
Read the full Arista Networks Software Engineer interview experience this question came from
A doubly linked list holds integers sorted in non-decreasing order. Find every pair of nodes whose values add up to a given `target`. The list may contain duplicate values, and each distinct pair of values must be reported only once.
The list is passed as `values`, the values of its nodes from head to tail. Implement `pairs_with_sum(values, target)` and return the list of pairs.
### Rules
- A pair uses two different nodes. A pair of equal values `[v, v]` therefore needs at least two nodes holding `v`.
- Report each distinct pair of values once, however many node pairs produce it: for `values = [1, 1, 3]` and `target = 4` the answer is `[[1, 3]]`, not two copies of it.
- Write each pair as `[a, b]` with `a <= b`, and sort the pairs by `a` in ascending order. Because `b = target - a`, this order is unique.
- Return an empty list when no pair exists.
### Constraints
- `0 <= len(values) <= 10^5`
- `-10^9 <= values[i] <= 10^9`, and `values[i] <= values[i + 1]` for every valid `i`
- `-2 * 10^9 <= target <= 2 * 10^9`
- Use 64-bit arithmetic for the target and for the sum of two values: Java receives `target` as a `long` and C++ as a `long long`.
### Example 1
```text
Input: values = [1, 1, 2, 3, 3, 3, 4], target = 4
Output: [[1, 3]]
```
Six node pairs (two `1` nodes times three `3` nodes) add up to `4`, but they form one distinct pair of values. `2 + 2` would need two nodes holding `2`, and there is only one.
### Example 2
```text
Input: values = [-1, 2, 2, 5, 6], target = 4
Output: [[-1, 5], [2, 2]]
```
`-1 + 5 = 4`, and the two nodes holding `2` form the pair `[2, 2]`.
Constraints
- 0 <= len(values) <= 10^5
- -10^9 <= values[i] <= 10^9
- values[i] <= values[i + 1] for every valid i (non-decreasing order; duplicates allowed)
- -2 * 10^9 <= target <= 2 * 10^9
- Use 64-bit arithmetic for the target and for the sum of two values (Java long, C++ long long for target)
Examples
Input: ([], 0)
Expected Output: []
Explanation: Empty list: there are no nodes, so no pair exists.
Input: ([5], 10)
Expected Output: []
Explanation: One node: 5 + 5 = 10 would need two nodes holding 5.
Hints
- Each distinct answer pair is fixed by its smaller value a, because b = target - a. How can the sorted order help you consider each distinct value only once?
- A pair [v, v] is valid only when at least two different nodes hold v, so the count of v matters, not just its presence.
- Lists with fewer than two nodes, or with no two values reaching the target, return an empty list.