Co-Listening Friend Recommendation Pairs

Hard

A music discovery platform wants to suggest new social connections from shared listening behavior. Table: Listens user_id: listener identifier song_id: song identifier day: calendar date of the listening event duplicate rows may exist and must not inflate distinct-song logic Table: Friendship user1_id: first user in an existing friendship edge user2_id: second user in an existing friendship edge each row is one existing undirected friendship user1_id < user2_id Recommendation policy: Recommend user x to user y if: x and y are not already friends, and there exists at least one day where x and y both listened to at least 3 distinct songs in common. Important output behavior: Recommendations are directional. If users a and b qualify, return both (a -> b) and (b -> a). Return unique rows only. Output requirements: Return exactly two columns: user_id recommended_id Result order is not important. Supported submission environments: SQL (SQLite 3.27.2) Pandas (Python)

Example 1

Input

Listens:
| user_id | song_id | day        |
|---------|---------|------------|
| 1       | 10      | 2024-03-01 |
| 1       | 11      | 2024-03-01 |
| 1       | 12      | 2024-03-01 |
| 2       | 10      | 2024-03-01 |
| 2       | 11      | 2024-03-01 |
| 2       | 12      | 2024-03-01 |
| 3       | 10      | 2024-03-01 |
| 3       | 11      | 2024-03-01 |
| 3       | 12      | 2024-03-01 |
| 4       | 10      | 2024-03-01 |
| 4       | 11      | 2024-03-01 |
| 4       | 13      | 2024-03-01 |

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

Output

[
  {"user_id":1,"recommended_id":3},
  {"user_id":2,"recommended_id":3},
  {"user_id":3,"recommended_id":1},
  {"user_id":3,"recommended_id":2}
]

Explanation

Users (1,3) and (2,3) each share 3 songs on the same day and are not friends. Pair (1,2) is excluded because they are already friends.

Example 2

Input

Listens:
| user_id | song_id | day        |
|---------|---------|------------|
| 1       | 20      | 2024-05-10 |
| 1       | 20      | 2024-05-10 |
| 1       | 21      | 2024-05-10 |
| 1       | 22      | 2024-05-10 |
| 2       | 20      | 2024-05-10 |
| 2       | 20      | 2024-05-10 |
| 2       | 21      | 2024-05-10 |
| 3       | 20      | 2024-05-10 |
| 3       | 21      | 2024-05-10 |
| 3       | 22      | 2024-05-10 |

Friendship:
| user1_id | user2_id |
|----------|----------|
| (no rows) |

Output

[
  {"user_id":1,"recommended_id":3},
  {"user_id":3,"recommended_id":1}
]

Explanation

Duplicate listen rows do not increase distinct shared-song count. Users 1 and 3 share {20,21,22}; pairs involving user 2 share only two distinct songs.

Example 3

Input

Listens:
| user_id | song_id | day        |
|---------|---------|------------|
| 7       | 31      | 2024-07-01 |
| 7       | 32      | 2024-07-01 |
| 7       | 33      | 2024-07-01 |
| 8       | 31      | 2024-07-01 |
| 8       | 32      | 2024-07-01 |
| 8       | 33      | 2024-07-01 |
| 7       | 40      | 2024-07-02 |
| 7       | 41      | 2024-07-02 |
| 7       | 42      | 2024-07-02 |
| 9       | 40      | 2024-07-02 |
| 9       | 41      | 2024-07-02 |
| 9       | 42      | 2024-07-02 |

Friendship:
| user1_id | user2_id |
|----------|----------|
| 7        | 8        |

Output

[
  {"user_id":7,"recommended_id":9},
  {"user_id":9,"recommended_id":7}
]

Explanation

Users 7 and 8 qualify by listening overlap but are filtered out because they are already friends. Users 7 and 9 qualify and are not friends, so both directions are returned.

Constraints

0 <= number of rows in Listens <= 500000
0 <= number of rows in Friendship <= 250000
1 <= user_id, song_id, user1_id, user2_id <= 1000000000
Listens may contain duplicate rows
(user1_id, user2_id) is unique in Friendship
Friendship.user1_id < Friendship.user2_id
day is a valid date value
Shared-song threshold is based on distinct song_id values on the same day
Recommendations must exclude existing friendships
Return directional recommendations
Do not return duplicate (user_id, recommended_id) rows
For SQL submissions, use SQLite 3.27.2 semantics
For Pandas submissions, return a DataFrame with columns: user_id, recommended_id

Listens: | user_id | song_id | day | |---------|---------|------------| | 1 | 10 | 2024-03-01 | | 1 | 11 | 2024-03-01 | | 1 | 12 | 2024-03-01 | | 2 | 10 | 2024-03-01 | | 2 | 11 | 2024-03-01 | | 2 | 12 | 2024-03-01 | | 3 | 10 | 2024-03-01 | | 3 | 11 | 2024-03-01 | | 3 | 12 | 2024-03-01 | | 4 | 10 | 2024-03-01 | | 4 | 11 | 2024-03-01 | | 4 | 13 | 2024-03-01 | Friendship: | user1_id | user2_id | |----------|----------| | 1 | 2 |

Listens: | user_id | song_id | day | |---------|---------|------------| | 1 | 20 | 2024-05-10 | | 1 | 20 | 2024-05-10 | | 1 | 21 | 2024-05-10 | | 1 | 22 | 2024-05-10 | | 2 | 20 | 2024-05-10 | | 2 | 20 | 2024-05-10 | | 2 | 21 | 2024-05-10 | | 3 | 20 | 2024-05-10 | | 3 | 21 | 2024-05-10 | | 3 | 22 | 2024-05-10 | Friendship: | user1_id | user2_id | |----------|----------| | (no rows) |

Listens: | user_id | song_id | day | |---------|---------|------------| | 7 | 31 | 2024-07-01 | | 7 | 32 | 2024-07-01 | | 7 | 33 | 2024-07-01 | | 8 | 31 | 2024-07-01 | | 8 | 32 | 2024-07-01 | | 8 | 33 | 2024-07-01 | | 7 | 40 | 2024-07-02 | | 7 | 41 | 2024-07-02 | | 7 | 42 | 2024-07-02 | | 9 | 40 | 2024-07-02 | | 9 | 41 | 2024-07-02 | | 9 | 42 | 2024-07-02 | Friendship: | user1_id | user2_id | |----------|----------| | 7 | 8 |