Friend Pairs with High Same-Day Song Overlap

Hard

A music intelligence platform tracks listening behavior and social links to identify friendship pairs with strongly aligned daily listening patterns. Table: Listens user_id: listener identifier song_id: song identifier day: calendar date of the listen event this table may contain duplicate rows Table: Friendship user1_id: first user in a friendship pair user2_id: second user in a friendship pair (user1_id, user2_id) is unique user1_id < user2_id in every row Task: Report friend pairs that meet all of the following: The pair exists in Friendship. On at least one same day, both users listened to at least 3 common distinct songs. Duplicate listen rows must not inflate shared-song counts. Output requirements: Return exactly two columns: user1_id and user2_id. Return each qualifying pair once. Preserve pair orientation as in Friendship (user1_id < user2_id). Result can be returned in any order. Supported submission environments: SQL (SQLite 3.27.2) Pandas (Python)

Example 1

Input

Listens:
| user_id | song_id | day        |
|---------|---------|------------|
| 1       | 10      | 2021-03-15 |
| 1       | 11      | 2021-03-15 |
| 1       | 12      | 2021-03-15 |
| 2       | 10      | 2021-03-15 |
| 2       | 11      | 2021-03-15 |
| 2       | 12      | 2021-03-15 |
| 4       | 10      | 2021-03-15 |
| 4       | 11      | 2021-03-15 |
| 4       | 13      | 2021-03-15 |
| 5       | 10      | 2021-03-16 |
| 5       | 11      | 2021-03-16 |
| 5       | 12      | 2021-03-16 |

Friendship:
| user1_id | user2_id |
|----------|----------|
| 1        | 2        |
| 2        | 4        |
| 2        | 5        |

Output

[
  {"user1_id":1,"user2_id":2}
]

Explanation

Only users 1 and 2 are friends with at least three common distinct songs on the same day.

Example 2

Input

Listens:
| user_id | song_id | day        |
|---------|---------|------------|
| 1       | 7       | 2024-04-01 |
| 1       | 7       | 2024-04-01 |
| 1       | 8       | 2024-04-01 |
| 2       | 7       | 2024-04-01 |
| 2       | 8       | 2024-04-01 |
| 2       | 9       | 2024-04-01 |
| 1       | 20      | 2024-04-02 |
| 1       | 21      | 2024-04-02 |
| 1       | 22      | 2024-04-02 |
| 3       | 20      | 2024-04-02 |
| 3       | 21      | 2024-04-02 |
| 3       | 22      | 2024-04-02 |

Friendship:
| user1_id | user2_id |
|----------|----------|
| 1        | 2        |
| 1        | 3        |

Output

[
  {"user1_id":1,"user2_id":3}
]

Explanation

Pair (1,2) has only two shared distinct songs on 2024-04-01 despite duplicate rows. Pair (1,3) qualifies on 2024-04-02.

Example 3

Input

Listens:
| user_id | song_id | day        |
|---------|---------|------------|
| 1       | 31      | 2024-06-10 |
| 1       | 32      | 2024-06-10 |
| 1       | 33      | 2024-06-10 |
| 2       | 31      | 2024-06-10 |
| 2       | 32      | 2024-06-10 |
| 2       | 33      | 2024-06-10 |
| 2       | 40      | 2024-06-11 |
| 2       | 41      | 2024-06-11 |
| 2       | 42      | 2024-06-11 |
| 4       | 40      | 2024-06-12 |
| 4       | 41      | 2024-06-12 |
| 4       | 42      | 2024-06-12 |
| 4       | 50      | 2024-06-13 |
| 4       | 51      | 2024-06-13 |
| 4       | 52      | 2024-06-13 |
| 5       | 50      | 2024-06-13 |
| 5       | 51      | 2024-06-13 |
| 5       | 52      | 2024-06-13 |

Friendship:
| user1_id | user2_id |
|----------|----------|
| 1        | 2        |
| 2        | 4        |
| 4        | 5        |

Output

[
  {"user1_id":1,"user2_id":2},
  {"user1_id":4,"user2_id":5}
]

Explanation

(1,2) and (4,5) each qualify on at least one same day. Pair (2,4) shares songs across different days, so it does not qualify.

Constraints

0 <= number of rows in Listens <= 300000
0 <= number of rows in Friendship <= 200000
1 <= user_id, user1_id, user2_id <= 1000000000
1 <= song_id <= 1000000000
Listens may contain duplicate rows
(user1_id, user2_id) is unique in Friendship
Friendship rows always satisfy user1_id < user2_id
day is a valid date or datetime-like string
A qualifying pair needs >= 3 common distinct songs on the same day
Return exactly two columns: user1_id, user2_id
Each qualifying pair should appear at most once
SQL submissions must follow SQLite 3.27.2 behavior
Pandas submissions must return a DataFrame with columns [user1_id, user2_id]

Listens: | user_id | song_id | day | |---------|---------|------------| | 1 | 10 | 2021-03-15 | | 1 | 11 | 2021-03-15 | | 1 | 12 | 2021-03-15 | | 2 | 10 | 2021-03-15 | | 2 | 11 | 2021-03-15 | | 2 | 12 | 2021-03-15 | | 4 | 10 | 2021-03-15 | | 4 | 11 | 2021-03-15 | | 4 | 13 | 2021-03-15 | | 5 | 10 | 2021-03-16 | | 5 | 11 | 2021-03-16 | | 5 | 12 | 2021-03-16 | Friendship: | user1_id | user2_id | |----------|----------| | 1 | 2 | | 2 | 4 | | 2 | 5 |

Listens: | user_id | song_id | day | |---------|---------|------------| | 1 | 7 | 2024-04-01 | | 1 | 7 | 2024-04-01 | | 1 | 8 | 2024-04-01 | | 2 | 7 | 2024-04-01 | | 2 | 8 | 2024-04-01 | | 2 | 9 | 2024-04-01 | | 1 | 20 | 2024-04-02 | | 1 | 21 | 2024-04-02 | | 1 | 22 | 2024-04-02 | | 3 | 20 | 2024-04-02 | | 3 | 21 | 2024-04-02 | | 3 | 22 | 2024-04-02 | Friendship: | user1_id | user2_id | |----------|----------| | 1 | 2 | | 1 | 3 |

Listens: | user_id | song_id | day | |---------|---------|------------| | 1 | 31 | 2024-06-10 | | 1 | 32 | 2024-06-10 | | 1 | 33 | 2024-06-10 | | 2 | 31 | 2024-06-10 | | 2 | 32 | 2024-06-10 | | 2 | 33 | 2024-06-10 | | 2 | 40 | 2024-06-11 | | 2 | 41 | 2024-06-11 | | 2 | 42 | 2024-06-11 | | 4 | 40 | 2024-06-12 | | 4 | 41 | 2024-06-12 | | 4 | 42 | 2024-06-12 | | 4 | 50 | 2024-06-13 | | 4 | 51 | 2024-06-13 | | 4 | 52 | 2024-06-13 | | 5 | 50 | 2024-06-13 | | 5 | 51 | 2024-06-13 | | 5 | 52 | 2024-06-13 | Friendship: | user1_id | user2_id | |----------|----------| | 1 | 2 | | 2 | 4 | | 4 | 5 |