LinkedIn: Mutual Connections Behind Pending Invitations
The invitation inbox shows how many mutual connections the sender shares with you, and the growth team wants to know how that number spreads across…
- Difficulty: Hard
- Topics: Joins, Aggregation, Subqueries
- Dialect: MySQL
- Problem: #741
Problem statement
The invitation inbox shows how many mutual connections the sender shares with you, and the growth team wants to know how that number spreads across invitations still waiting for an answer.
For every invitation with status pending, return invitation_id, sender_id, recipient_id and mutual_connections: the number of members who are connected to both the sender and the recipient (0 if none). Connections are stored once per pair with the smaller id in member_a. Order the rows by mutual_connections descending, then invitation_id ascending.
A practice scenario set at LinkedIn: the tables and data are invented, and this is not a question from, or endorsed by, LinkedIn.
Tables
Table: MemberConnection
| Column | Type |
|---|---|
| member_a | int |
| member_b | int |
Primary key: member_a, member_b.
One row per connected pair, always with member_a < member_b.
Table: Invitation
| Column | Type |
|---|---|
| invitation_id | int |
| sender_id | int |
| recipient_id | int |
| status | enum(pending, accepted, ignored) |
Primary key: invitation_id.
One row per connection invitation; sender and recipient always differ.
Examples
Example 1
MemberConnection
| member_a | member_b |
|---|---|
| 1 | 3 |
| 1 | 4 |
| 2 | 3 |
| 2 | 4 |
| 3 | 5 |
| 4 | 6 |
| 5 | 6 |
Invitation
| invitation_id | sender_id | recipient_id | status |
|---|---|---|---|
| 10 | 1 | 2 | pending |
| 11 | 5 | 4 | pending |
| 12 | 1 | 6 | pending |
| 13 | 3 | 4 | accepted |
| 14 | 6 | 2 | pending |
| 15 | 5 | 2 | pending |
Output
| invitation_id | sender_id | recipient_id | mutual_connections |
|---|---|---|---|
| 10 | 1 | 2 | 2 |
| 11 | 5 | 4 | 1 |
| 12 | 1 | 6 | 1 |
| 14 | 6 | 2 | 1 |
| 15 | 5 | 2 | 1 |
How to solve LinkedIn: Mutual Connections Behind Pending Invitations
Stored once per pair, connections are awkward to query: "my connections" means the pairs where I am member_a plus the pairs where I am member_b. The CTE e normalises this into a directed edge list with every connection twice, once from each end, so e.m = X lists all of X's connections in one condition.
Then a mutual connection is a member f reached from both people. The first LEFT JOIN lists the sender's connections s.f; the second looks for a recipient edge to the same member (r.m = recipient AND r.f = s.f). Each match is one mutual connection, so COUNT(r.f) counts them, and the NULLs left by unmatched rows — or by a sender with no connections at all — count as 0. Both joins are LEFT so that invitations with nothing in common still produce a row. The primary key guarantees no duplicate edges, so no mutual connection is counted twice.
The alternatives count per invitation with correlated subqueries — one with EXISTS over the edge list, one with IN over the recipient's neighbours built inline. The join version computes one intermediate row per sender connection; with indexes on both columns of MemberConnection all three are lookups per invitation.
Reference solution (MySQL)
WITH e AS (
SELECT member_a AS m, member_b AS f FROM MemberConnection
UNION ALL
SELECT member_b, member_a FROM MemberConnection
)
SELECT i.invitation_id, i.sender_id, i.recipient_id, COUNT(r.f) AS mutual_connections
FROM Invitation i
LEFT JOIN e s ON s.m = i.sender_id
LEFT JOIN e r ON r.m = i.recipient_id AND r.f = s.f
WHERE i.status = 'pending'
GROUP BY i.invitation_id, i.sender_id, i.recipient_id
ORDER BY mutual_connections DESC, i.invitation_idAnother way
WITH e AS (SELECT member_a AS m, member_b AS f FROM MemberConnection UNION ALL SELECT member_b, member_a FROM MemberConnection)
SELECT i.invitation_id, i.sender_id, i.recipient_id,
(SELECT COUNT(*) FROM e x WHERE x.m = i.sender_id AND EXISTS (SELECT 1 FROM e y WHERE y.m = i.recipient_id AND y.f = x.f)) AS mutual_connections
FROM Invitation i
WHERE i.status = 'pending'
ORDER BY mutual_connections DESC, i.invitation_idAnother way
SELECT i.invitation_id, i.sender_id, i.recipient_id,
(SELECT COUNT(*) FROM (SELECT member_a AS m, member_b AS f FROM MemberConnection UNION SELECT member_b, member_a FROM MemberConnection) x
WHERE x.m = i.sender_id AND x.f IN (SELECT member_b FROM MemberConnection WHERE member_a = i.recipient_id
UNION SELECT member_a FROM MemberConnection WHERE member_b = i.recipient_id)) AS mutual_connections
FROM Invitation i
WHERE i.status = 'pending'
ORDER BY mutual_connections DESC, i.invitation_id← LinkedIn: Members With Exactly the Same Skill Set · LinkedIn: Followers Across Each Company's Affiliated Pages →