Leetcodify Friends Recommendations Problem


Description

LeetCode Problem 1917.

Table: Listens

1
2
3
4
5
6
7
8
9
+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| user_id     | int     |
| song_id     | int     |
| day         | date    |
+-------------+---------+
There is no primary key for this table. It may contain duplicates.
Each row of this table indicates that the user user_id listened to the song song_id on the day day.

Table: Friendship

1
2
3
4
5
6
7
8
9
+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| user1_id      | int     |
| user2_id      | int     |
+---------------+---------+
(user1_id, user2_id) is the primary key for this table.
Each row of this table indicates that the users user1_id and user2_id are friends.
Note that user1_id < user2_id.

Write an SQL query to recommend friends to Leetcodify users. We recommend user x to user y if:

  • Users x and y are not friends, and
  • Users x and y listened to the same three or more different songs on the same day.

Note that friend recommendations are unidirectional, meaning if user x and user y should be recommended to each other, the result table should have both user x recommended to user y and user y recommended to user x. Also, note that the result table should not contain duplicates (i.e., user y should not be recommended to user x multiple times.).

Return the result table in any order.

The query result format is in the following example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
Listens table:
+---------+---------+------------+
| 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 |
| 3       | 10      | 2021-03-15 |
| 3       | 11      | 2021-03-15 |
| 3       | 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 table:
+----------+----------+
| user1_id | user2_id |
+----------+----------+
| 1        | 2        |
+----------+----------+

Result table:
+---------+----------------+
| user_id | recommended_id |
+---------+----------------+
| 1       | 3              |
| 2       | 3              |
| 3       | 1              |
| 3       | 2              |
+---------+----------------+
Users 1 and 2 listened to songs 10, 11, and 12 on the same day, but they are already friends.
Users 1 and 3 listened to songs 10, 11, and 12 on the same day. Since they are not friends, we recommend them to each other.
Users 1 and 4 did not listen to the same three songs.
Users 1 and 5 listened to songs 10, 11, and 12, but on different days.

Similarly, we can see that users 2 and 3 listened to songs 10, 11, and 12 on the same day and are not friends, so we recommend them to each other.


MySQL Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
with allRecs as (
	select distinct
	  l1.user_id as user1_id,
	  l2.user_id as user2_id
	from Listens l1 inner join Listens l2 on l1.song_id = l2.song_id and l1.day=l2.day and l1.user_id < l2.user_id
	where not exists(select * from Friendship f where l1.user_id = f.user1_id and l2.user_id = f.user2_id)
	group by l1.user_id, l2.user_id, l1.day
	having count(distinct l1.song_id) >= 3
) 
select user1_id as user_id,
       user2_id as recommended_id
from allRecs
union
select user2_id as user_id,
       user1_id as recommended_id
from allRecs




Related Posts

Leetcodify Friends Recommendations Problem

LeetCode 1917. Write an SQL query to recommend friends to...

Count Salary Categories Problem

LeetCode 1907. Write an SQL query to report the number...

The Latest Login in 2020 Problem

LeetCode 1890. Write an SQL query to report the latest...

Suspicious Bank Accounts Problem

LeetCode 1843. Write an SQL query to report the IDs...

Page Recommendations II Problem

LeetCode 1892. Write an SQL query to find all the...

Orders With Maximum Quantity Above Average Problem

LeetCode 1867. Write an SQL query to find the order_id...