Meta: Accounts Linked to Banned Accounts Through Shared Devices

Hard
772.

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

ColumnType
account_idint
is_bannedbool

Primary key: account_id.

One row per account; is_banned is 1 for accounts disabled for policy violations.

Table: DeviceLogin

ColumnType
account_idint
device_idvarchar

Primary key (together): account_id, device_id.

Each device an account has logged in on (one row per pair). Every account_id is in FbAccount.

Example

The rows may come back in any order; the columns must be the ones shown, in that order.

FbAccount

account_idis_banned
11
20
30
40
50
61
70
80

DeviceLogin

account_iddevice_id
1dev-a
2dev-a
2dev-b
3dev-b
4dev-c
5dev-c
6dev-d
7dev-e
3dev-f
8dev-f
2 more rows

Output

account_idhops
21
32
81
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.

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

ColumnType
account_idint
is_bannedbool

Primary key: account_id.

One row per account; is_banned is 1 for accounts disabled for policy violations.

Table: DeviceLogin

ColumnType
account_idint
device_idvarchar

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_idis_banned
11
20
30
40
50
61
70
80

DeviceLogin

account_iddevice_id
1dev-a
2dev-a
2dev-b
3dev-b
4dev-c
5dev-c
6dev-d
7dev-e
3dev-f
8dev-f
8dev-g
6dev-g

Output

account_idhops
21
32
81

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_id

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