LinkedIn: First- and Second-Degree Network Size
A member's reach on the network is their first-degree connections plus the people one introduction away.
- Difficulty: Hard
- Topics: Joins, Subqueries, Aggregation
- Dialect: MySQL
- Problem: #745
Problem statement
A member's reach on the network is their first-degree connections plus the people one introduction away. The network-insights team wants both numbers for everyone.
For every member, return member_id, first_degree (their number of connections) and second_degree: the number of different members who are connected to at least one of their connections but are neither the member themselves nor already a first-degree connection. Connections are stored once per pair with the smaller id in member_a. Members with no connections show 0 and 0. Order the rows by member_id.
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: Member
| Column | Type |
|---|---|
| member_id | int |
| full_name | varchar |
Primary key: member_id.
One row per member.
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; both are member ids.
Examples
Example 1
Member
| member_id | full_name |
|---|---|
| 1 | Aisha Khan |
| 2 | Dev Sharma |
| 3 | Emma Nair |
| 4 | Harsh Gupta |
| 5 | Liam Rao |
| 6 | Zara Iyer |
MemberConnection
| member_a | member_b |
|---|---|
| 1 | 2 |
| 1 | 3 |
| 2 | 3 |
| 3 | 4 |
| 4 | 5 |
Output
| member_id | first_degree | second_degree |
|---|---|---|
| 1 | 2 | 1 |
| 2 | 2 | 1 |
| 3 | 3 | 1 |
| 4 | 2 | 2 |
| 5 | 1 | 1 |
| 6 | 0 | 0 |
How to solve LinkedIn: First- and Second-Degree Network Size
Graph questions in SQL start by making the edges easy to follow: the CTE e lists every connection in both directions, so e.m = X gives all of X's neighbours. A walk of two steps is then a self join of e — from the member x.m to a neighbour x.f, and from that neighbour to its own neighbours y.f.
Those two-step endpoints include noise that must be removed. Every walk can come straight back (y.f = x.m), so the member reaches themselves through each of their connections. A first-degree connection can also be reached in two steps through a shared friend, as members 1 and 2 are through 3 in the example — the NOT EXISTS against e drops them. And one person is often reachable through several connections, so the ring needs DISTINCT. What remains is the second-degree network; correlated counts per member give 0 for anyone with no rows.
The alternative LEFT JOINs both hops from Member, so isolated members survive, and does the filtering inside COUNT(DISTINCT CASE …). The cost grows with the sum over members of their neighbours' degrees — modest on sparse graphs, which professional networks are, but the reason real systems precompute this.
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
), second_ring AS (
SELECT DISTINCT x.m, y.f AS other
FROM e x
JOIN e y ON y.m = x.f
WHERE y.f <> x.m
AND NOT EXISTS (SELECT 1 FROM e z WHERE z.m = x.m AND z.f = y.f)
)
SELECT mb.member_id,
(SELECT COUNT(*) FROM e WHERE e.m = mb.member_id) AS first_degree,
(SELECT COUNT(*) FROM second_ring s WHERE s.m = mb.member_id) AS second_degree
FROM Member mb
ORDER BY mb.member_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 mb.member_id,
COUNT(DISTINCT x.f) AS first_degree,
COUNT(DISTINCT CASE WHEN y.f <> mb.member_id
AND NOT EXISTS (SELECT 1 FROM e z WHERE z.m = mb.member_id AND z.f = y.f)
THEN y.f END) AS second_degree
FROM Member mb
LEFT JOIN e x ON x.m = mb.member_id
LEFT JOIN e y ON y.m = x.f
GROUP BY mb.member_id
ORDER BY mb.member_id← LinkedIn: Merge Overlapping Premium Periods Into Spans · LinkedIn: Top Endorsed Skill per Industry and Its Lead →