Two Sigma·Data Scientist·Technical Phone Screen·Senior

Senior

Jun 2026

Summary

Two Sigma data scientist interview with a probability/combinatorics problem that looked like a graph question but was really just linearity of expectation dressed up in fancy clothing. Clean problem statement, no behavioral stuff from what I could tell.

Questions Asked (1)

In a complete graph on n vertices where every edge weight is drawn independently from the same continuous distribution, define a 'good pair' as two vertices that are each other's maximum-weight neighbor. Derive a closed-form expression for the expected number of good pairs.

Algorithms & Data StructuresProduct Analytics & Metrics

Author's notes

I spent the first few minutes thinking about this combinatorially in a way that was going nowhere.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use linearity of expectation by defining an indicator for each unordered pair of vertices being a good pair. For a fixed pair {u,v}, compute the probability that u is v's maximum-weight neighbor and v is u's maximum-weight neighbor, leveraging symmetry and the continuous distribution of edge weights. Then multiply by the number of pairs to get the expected number.

Pro tip: Emphasize that the specific continuous distribution doesn't matter—only that ties have probability zero and all edge weights are i.i.d. This shows you understand the robustness of the result and can simplify the problem.

1. Define indicator variables

For each unordered pair {u,v}, let I_{uv} be 1 if u and v are each other's maximum-weight neighbor, else 0. Then the total number of good pairs is the sum of I_{uv} over all pairs.

2. Apply linearity of expectation

The expected number of good pairs is the sum of E[I_{uv}] over all pairs. By symmetry, E[I_{uv}] is the same for every pair, so the expectation equals C(n,2) times the probability that a fixed pair is good.

3. Compute probability for a fixed pair

Fix vertices u and v. For u to be v's maximum-weight neighbor, the edge (u,v) must have weight greater than all other edges incident to v. Similarly, for v to be u's maximum-weight neighbor, (u,v) must be greater than all other edges incident to u. These conditions involve disjoint sets of edges (except the shared edge (u,v)), so they are independent given the weight of (u,v).

4. Calculate the probability

Condition on the weight w of edge (u,v). The probability that (u,v) is the maximum among the n-1 edges incident to v is 1/(n-1) (by symmetry, since all n-1 edges are i.i.d.). Similarly for u. Since the events are independent given w, the conditional probability is 1/(n-1)^2. This does not depend on w, so the unconditional probability is also 1/(n-1)^2.

5. Multiply by number of pairs

The expected number of good pairs is C(n,2) * 1/(n-1)^2 = [n(n-1)/2] / (n-1)^2 = n / (2(n-1)).

Key Points to Mention

Linearity of expectation allows summing probabilities without worrying about dependencies between different pairs.
Symmetry: all pairs are equivalent, so we only need to compute the probability for one pair.
The continuous distribution ensures no ties, so the maximum is unique almost surely.
For a fixed pair, the events 'u is v's max neighbor' and 'v is u's max neighbor' are independent because they depend on disjoint sets of edges (other than the shared edge, which is conditioned on).
The probability that a specific edge is the maximum among k i.i.d. continuous random variables is 1/k.
The final closed-form expression is n/(2(n-1)), which simplifies to approximately 1/2 for large n.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.