Meta: Accounts Linked to Banned Accounts Through Shared Devices
Meta's integrity team looks for ban evasion: people who come back with fresh accounts on the same phones.
- Difficulty: Hard
- Topics: Subqueries, Joins
- Dialect: MySQL
- Problem: #772
Problem statement
Meta's integrity team looks for ban evasion: people who come back with fresh accounts on the same phones. Two accounts are directly linked when both logged in on at least one common device. Links chain: an account linked to an account linked to a banned account is in the same cluster, two hops away.
Return every account that is not banned but is connected, through any chain of links, to at least one banned account, with the columns account_id and hops — the fewest links from it to its nearest banned account (1 for an account sharing a device with a banned one). Return the rows in any order.
A practice scenario set at Meta: the tables and data are invented, and this is not a question from, or endorsed by, Meta.
Tables
Table: FbAccount
| Column | Type |
|---|---|
| account_id | int |
| is_banned | bool |
Primary key: account_id.
One row per account; is_banned is 1 for accounts disabled for policy violations.
Table: DeviceLogin
| Column | Type |
|---|---|
| account_id | int |
| device_id | varchar |
Primary key: account_id, device_id.
Each device an account has logged in on (one row per pair). Every account_id is in FbAccount.
Examples
Example 1
FbAccount
| account_id | is_banned |
|---|---|
| 1 | 1 |
| 2 | 0 |
| 3 | 0 |
| 4 | 0 |
| 5 | 0 |
| 6 | 1 |
| 7 | 0 |
| 8 | 0 |
DeviceLogin
| account_id | device_id |
|---|---|
| 1 | dev-a |
| 2 | dev-a |
| 2 | dev-b |
| 3 | dev-b |
| 4 | dev-c |
| 5 | dev-c |
| 6 | dev-d |
| 7 | dev-e |
| 3 | dev-f |
| 8 | dev-f |
| 8 | dev-g |
| 6 | dev-g |
Output
| account_id | hops |
|---|---|
| 2 | 1 |
| 3 | 2 |
| 8 | 1 |
How to solve Meta: Accounts Linked to Banned Accounts Through Shared Devices
First the logins become a graph: a self-join of DeviceLogin on device_id (excluding an account paired with itself) gives an edge for every pair of accounts that shared a device; DISTINCT collapses pairs that shared several devices into one edge.
Reachability over that graph needs recursion. The anchor puts every banned account at distance 0; each recursive step follows an edge and adds one hop. Because the graph has cycles — two accounts on one device link each other both ways — the recursion needs a stopping rule: a shortest path never has more links than there are accounts, so hops < COUNT(*) bounds it, and UNION (not UNION ALL) removes duplicate (account, hops) rows so the work stays small. Grouping the reached rows by account and taking MIN(hops) gives the distance to the nearest banned account; banned accounts themselves are filtered out, and accounts in clusters without a banned member are never reached.
The alternative searches in the other direction — from every clean account outward, keeping the shortest walk that ends on a banned account. It explores once per starting account rather than once overall, so a breadth-first search from the banned set is the cheaper choice on a large graph.
Reference solution (MySQL)
WITH RECURSIVE linked AS (
SELECT DISTINCT a.account_id AS src, b.account_id AS dst
FROM DeviceLogin a
JOIN DeviceLogin b ON b.device_id = a.device_id AND b.account_id <> a.account_id
), reach AS (
SELECT account_id, 0 AS hops FROM FbAccount WHERE is_banned = 1
UNION
SELECT l.dst, r.hops + 1
FROM reach r
JOIN linked l ON l.src = r.account_id
WHERE r.hops < (SELECT COUNT(*) FROM FbAccount)
)
SELECT r.account_id, MIN(r.hops) AS hops
FROM reach r
JOIN FbAccount f ON f.account_id = r.account_id
WHERE f.is_banned = 0
GROUP BY r.account_idAnother way
WITH RECURSIVE linked AS (
SELECT DISTINCT a.account_id AS src, b.account_id AS dst
FROM DeviceLogin a JOIN DeviceLogin b ON b.device_id = a.device_id AND b.account_id <> a.account_id
), walk AS (
SELECT account_id AS start_id, account_id AS at_id, 0 AS hops FROM FbAccount WHERE is_banned = 0
UNION
SELECT w.start_id, l.dst, w.hops + 1
FROM walk w JOIN linked l ON l.src = w.at_id
WHERE w.hops < (SELECT COUNT(*) FROM FbAccount)
)
SELECT w.start_id AS account_id, MIN(w.hops) AS hops
FROM walk w
JOIN FbAccount b ON b.account_id = w.at_id AND b.is_banned = 1
GROUP BY w.start_id← Meta: Instagram Reels Shopping Funnel, Steps in Order · Microsoft: Dev and Test VMs Still Billing Over the Weekend →