LinkedIn: First- and Second-Degree Network Size

Hard
745.

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. 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

ColumnType
member_idint
full_namevarchar

Primary key: member_id.

One row per member.

Table: MemberConnection

ColumnType
member_aint
member_bint

Primary key (together): member_a, member_b.

One row per connected pair, always with member_a < member_b; both are member ids.

Example

The rows must come back in the order shown.

Member

member_idfull_name
1Aisha Khan
2Dev Sharma
3Emma Nair
4Harsh Gupta
5Liam Rao
6Zara Iyer

MemberConnection

member_amember_b
12
13
23
34
45

Output

member_idfirst_degreesecond_degree
121
221
331
422
511
600
Read the hints, the editorial and the reference solution
-- Write your MySQL query below

Sign in to write, run and submit queries

A free account — no card, no trial clock. You come straight back here.

Run your query to see its result next to the expected one, example by example.

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

ColumnType
member_idint
full_namevarchar

Primary key: member_id.

One row per member.

Table: MemberConnection

ColumnType
member_aint
member_bint

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_idfull_name
1Aisha Khan
2Dev Sharma
3Emma Nair
4Harsh Gupta
5Liam Rao
6Zara Iyer

MemberConnection

member_amember_b
12
13
23
34
45

Output

member_idfirst_degreesecond_degree
121
221
331
422
511
600

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_id

Another 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 →