Expected Number of Good Pairs in a Randomly Weighted Complete Graph
Company: Two Sigma
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Expected Number of Good Pairs in a Randomly Weighted Complete Graph
You are given a complete graph on `n` vertices — every pair of distinct vertices is connected by exactly one edge, so there are `n * (n - 1) / 2` edges in total. Each edge is independently assigned a weight drawn from the same continuous probability distribution. Because the distribution is continuous, all edge weights are distinct with probability 1.
For a vertex `a`, define its **favorite neighbor** as the vertex connected to `a` by the maximum-weight edge among all `n - 1` edges incident to `a` (with probability 1 this vertex is unique).
An unordered pair of vertices `(a, b)` is called a **good pair** if `b` is the favorite neighbor of `a` **and** `a` is the favorite neighbor of `b` — that is, the edge between `a` and `b` has the maximum weight among all edges incident to `a`, and also the maximum weight among all edges incident to `b`.
Given the integer `n`, return the expected number of good pairs in the graph.
## Input
- A single integer `n` — the number of vertices in the complete graph.
## Output
- A single floating-point number: the expected number of good pairs. Answers within an absolute or relative error of `1e-6` of the correct value are accepted.
## Constraints
- `2 <= n <= 10^9`
- The answer is the same for every continuous distribution, as long as all edge weights are drawn i.i.d. from it — your result must not depend on the particular distribution.
- Your solution must run in `O(1)` (or at most `O(log n)`) time. Monte Carlo simulation is neither precise enough nor fast enough at this scale.
## Examples
**Example 1**
```
Input: n = 2
Output: 1.0
```
Explanation: The graph has a single edge. Each vertex's only neighbor — and therefore its favorite neighbor — is the other vertex, so the unique pair is always a good pair.
**Example 2**
```
Input: n = 4
Output: 1.2
```
Quick Answer: This question evaluates probabilistic reasoning, combinatorics, and order-statistics intuition by asking for the expected count of mutual maximum-edge neighbors (good pairs) in an edge-weighted complete graph with i.i.d. continuous weights.
You are given a complete graph on `n` vertices — every pair of distinct vertices is connected by exactly one edge, so there are `n * (n - 1) / 2` edges in total. Each edge is independently assigned a weight drawn from the same continuous probability distribution. Because the distribution is continuous, all edge weights are distinct with probability 1.
For a vertex `a`, define its **favorite neighbor** as the vertex connected to `a` by the maximum-weight edge among all `n - 1` edges incident to `a` (with probability 1 this vertex is unique).
An unordered pair of vertices `(a, b)` is called a **good pair** if `b` is the favorite neighbor of `a` **and** `a` is the favorite neighbor of `b` — that is, the edge between `a` and `b` has the maximum weight among all edges incident to `a`, and also the maximum weight among all edges incident to `b`.
Given the integer `n`, return the expected number of good pairs in the graph.
## Input
- A single integer `n` — the number of vertices in the complete graph.
## Output
- A single floating-point number: the expected number of good pairs. Answers within an absolute or relative error of `1e-6` of the correct value are accepted.
## Constraints
- `2 <= n <= 10^9`
- The answer is the same for every continuous distribution, as long as all edge weights are drawn i.i.d. from it — your result must not depend on the particular distribution.
- Your solution must run in `O(1)` (or at most `O(log n)`) time. Monte Carlo simulation is neither precise enough nor fast enough at this scale.
## Examples
**Example 1**
```
Input: n = 2
Output: 1.0
```
Explanation: The graph has a single edge. Each vertex's only neighbor — and therefore its favorite neighbor — is the other vertex, so the unique pair is always a good pair.
**Example 2**
```
Input: n = 4
Output: 1.2
```
Constraints
- 2 <= n <= 10^9
- The answer is distribution-independent (any i.i.d. continuous edge-weight distribution).
- Must run in O(1) (or O(log n)) time; simulation is too slow/imprecise.
- Answers within absolute or relative error 1e-6 are accepted.
Examples
Input: (2,)
Expected Output: 1.0
Explanation: Single edge; the one pair is always good. E = 2*1/(2*(2*2-3)) = 2/2 = 1.0.
Input: (3,)
Expected Output: 1.0
Explanation: C(3,2)=3 pairs, 2n-3=3, so E = 3/3 = 1.0.
Hints
- Use linearity of expectation: the expected number of good pairs is the number of pairs times the probability that a single fixed pair is good. By symmetry every pair has the same probability.
- Fix one edge (a, b). It is a good pair exactly when its weight is the largest among all edges incident to a AND all edges incident to b. Count how many distinct edges are in that union: (n-1) at a plus (n-1) at b minus the shared edge (a,b) = 2n-3.
- Because the weights are i.i.d. and continuous, each of those 2n-3 edges is equally likely to be the maximum, so the probability that (a,b) is the max is 1/(2n-3). Multiply by C(n,2) to get E = n*(n-1) / (2*(2n-3)).