Six Degrees

A hard SQL interview practice problem on DataDriven. Write the query and run it against a real database, with instant feedback.

Domain

SQL

Difficulty

hard

Seniority

L5

Asked in

Meta

Problem

In chat_msgs, every reply ties its sender to the person in reply_to, and the tie runs both ways, though nobody is ever tied to themselves. How many different people is each person tied to, and what percentage of everyone who has ever sent or received a message does that make, rounded to two decimals?

Every reply ties two names together. Find whose web reaches the furthest.

Tables

chat_msgs

Columns: msg_id INTEGER, channel TEXT, sender_id INTEGER, content TEXT, msg_type TEXT, sent_at TEXT, edited INTEGER, reply_to INTEGER

Expected output

Worked solution and explanation

What this problem really is

This is a graph degree problem wearing a chat log's clothes. Each reply is one undirected edge between two user IDs, and the connection score is just a node's degree divided by the number of nodes in the graph. The trap sits in one column: reply_to looks like it should point back at a message, but here it carries the other person's user id directly. Read it as a message pointer and join chat_msgs to itself on msg_id, and on this data nothing matches, because reply_to values like 5 never line up with msg_id values in the millions, so the result comes back empty and every user vanishes.

Building the edge list

Step 1: Turn replies into undirected edges

Keep only replies that point at someone other than the sender. reply_to <> sender_id does both jobs at once: a comparison against a NULL reply_to is never true, so plain messages drop out along with the self-replies. Emit each kept row twice, sender_id to reply_to and back, and stack the two with UNION ALL. A pair who replied to each other, or kept replying, now shows up more than once, and that is fine: the next step is where it collapses.

Step 2: Measure the whole graph

The denominator is every person who ever sent or received a message, not just the senders. Union the senders with the reply targets and count the rows. Here the reply_to IS NOT NULL guard is load-bearing: most messages are not replies, and without it the union carries one NULL row that COUNT(*) happily counts as an extra person, quietly shrinking every score.

Step 3: Degree over platform size

Group the edge list by user_id and take COUNT(DISTINCT connected_to) as each person's degree. A plain COUNT(*) here counts replies, not people: two people who traded replies would each be credited twice. The platform total is a single scalar, so a CROSS JOIN broadcasts it to every person cheaply; multiply by 100.0 and round to two places. The question asks for a score per person, not a leaderboard, so no row order is owed.

The solution

WITH edges AS (
    SELECT sender_id AS user_id, reply_to AS connected_to
    FROM chat_msgs
    WHERE reply_to <> sender_id
    UNION ALL
    SELECT reply_to AS user_id, sender_id AS connected_to
    FROM chat_msgs
    WHERE reply_to <> sender_id
),
degrees AS (
    SELECT user_id, COUNT(DISTINCT connected_to) AS unique_connections
    FROM edges
    GROUP BY user_id
),
participants AS (
    SELECT sender_id AS person_id FROM chat_msgs
    UNION
    SELECT reply_to AS person_id FROM chat_msgs WHERE reply_to IS NOT NULL
),
platform AS (
    SELECT COUNT(*) AS total_users
    FROM participants
)
SELECT
    d.user_id,
    d.unique_connections,
    ROUND(d.unique_connections * 100.0 / p.total_users, 2) AS connection_score
FROM degrees d
CROSS JOIN platform p;

Self-join on `msg_id` (wrong here)

JOIN chat_msgs child ON child.reply_to = parent.msg_id assumes reply_to is a message foreign key. On this data reply_to holds a user id, never a msg_id, so the join matches zero rows and the answer is empty.

Pair sender with `reply_to` (correct)

Treat reply_to as the connected user's id and pair it with sender_id directly. Both orderings give an undirected edge, and counting distinct partners per user gives the degree.

Common follow-up questions

• How would you surface only the ten most connected people? (Now order matters: sort by the score, decide which tied person survives the cut, then apply a `LIMIT`.)
• What changes if you only want connections formed in the last 30 days? (Push a `sent_at` window into the edges CTE before the UNION so both directions inherit it.)
• How would you score mutual connections, where both people replied to each other? (Intersect the two directions instead of unioning them, so an edge survives only if it appears both ways.)
• What if the table held billions of messages? (Precompute and incrementally maintain an edge or degree table rather than rebuilding the graph per query.)