# Six Degrees > Every reply ties two names together. Find whose web reaches the furthest. Canonical URL: 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? ## Tables ### chat_msgs - msg_id INTEGER - channel TEXT - sender_id INTEGER - content TEXT - msg_type TEXT - sent_at TEXT - edited INTEGER - reply_to INTEGER Sample rows (10 of 200): | msg_id | channel | sender_id | content | msg_type | sent_at | edited | reply_to | | --- | --- | --- | --- | --- | --- | --- | --- | | 147 | #engineering | 197 | Anyone seeing increased latency? | file | 2026-02-02 01:07:00 | 0 | NULL | | 194 | #incidents | 294 | PR #412 ready for review | reaction | 2026-03-03 02:14:00 | 0 | NULL | | 241 | #random | 391 | Dashboard is down | thread_reply | 2026-04-04 03:21:00 | 0 | NULL | | 288 | #deployments | 488 | Fixed the flaky test | system | 2026-05-05 04:28:00 | 0 | NULL | | 335 | #data-team | 585 | Merged the migration | Text | 2026-06-06 05:35:00 | 0 | NULL | | 382 | #general | 682 | NULL | FILE | 2026-07-07 06:42:00 | 0 | NULL | | 429 | #engineering | 779 | LGTM | text | 2026-08-08 07:49:00 | 0 | NULL | | 476 | #incidents | 876 | 👍 | file | 2026-09-09 08:56:00 | 0 | 5 | | 523 | #random | 973 | | reaction | 2026-01-10 09:03:00 | 0 | NULL | | 570 | #deployments | 1070 | Can someone check the pipeline? | thread_reply | 2026-02-11 10:10:00 | 0 | NULL | ## Expected output First 5 of 48 rows: | user_id | unique_connections | connection_score | | --- | --- | --- | | 5 | 1 | 1.35 | | 11 | 1 | 1.35 | | 14 | 1 | 1.35 | | 17 | 1 | 1.35 | | 23 | 1 | 1.35 | ## 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. > **Edges first, counting second** > > Build one undirected edge list first, then everything else is counting. Emit (`sender_id`, `reply_to`) and (`reply_to`, `sender_id`) for every real reply and stack them with `UNION ALL`: that turns a messaging table into a graph. Repeat chatter stays in the list on purpose, and `COUNT(DISTINCT connected_to)` is what turns it into a count of people rather than a count of replies. --- ### 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 **Edge list, per-person degree, platform size** ```sql 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. > **A self-reply is not a tie** > > Letting a user who replies to their own message inflate the count. A row where `reply_to` equals `sender_id` is a self-loop, not a connection. The `reply_to <> sender_id` filter drops it before edges are built; skip it and a chatty self-replier shows a connection to themselves. > **Half the graph lives in `reply_to`** > > Whether you carry both directions. If A replies to B, B is just as connected to A. Candidates who emit only (`sender_id`, `reply_to`) silently drop or undercount everyone on the receiving end of a reply, and the bug stays invisible until someone checks a known pair. > **One scan, one scalar** > > Only replies survive the filter: `reply_to` is NULL on 152 of the seed's 200 rows, and on a 50M-row production table the same filter discards every non-reply before both directions are stacked. `UNION ALL` skips a dedupe pass that the per-person `COUNT(DISTINCT)` already does, and the platform size is one scalar computed once and broadcast through the CROSS JOIN, so there is no self-join blowup. --- ## 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.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/six_degrees) - [SQL Interview Questions](https://datadriven.io/sql-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.