Watch the video solution for Leetcodify Friends Recommendations, a hard level problem involving Database. This walkthrough by Everyday Data Science has 800 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Table: Listens
+-------------+---------+ | Column Name | Type | +-------------+---------+ | user_id | int | | song_id | int | | day | date | +-------------+---------+ This table may contain duplicates (In other words, there is no primary key for this table in SQL). Each row of this table indicates that the user user_id listened to the song song_id on the day day.
Table: Friendship
+---------------+---------+ | Column Name | Type | +---------------+---------+ | user1_id | int | | user2_id | int | +---------------+---------+ In SQL,(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.
Recommend friends to Leetcodify users. We recommend user x to user y if:
x and y are not friends, andx 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 result format is in the following example.
Example 1:
Input: 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 | +----------+----------+ Output: +---------+----------------+ | user_id | recommended_id | +---------+----------------+ | 1 | 3 | | 2 | 3 | | 3 | 1 | | 3 | 2 | +---------+----------------+ Explanation: 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.
Problem Overview: You have listening activity from a music platform and a friendship graph between users. The task is to recommend songs to a user when multiple friends listened to the same song on the same day, while ensuring the user has not already listened to that song that day.
Approach 1: Friendship Expansion + Listening Join (SQL Aggregation) (Time: O(n log n), Space: O(n))
The core idea is to combine the friendship relationships with listening activity and count how many friends listened to the same song_id on a specific day. Start by normalizing the friendship table so every relationship appears in both directions (user → friend and friend → user). Join this expanded friendship set with the Listens table to fetch songs played by friends. Then group by user_id, song_id, and day and count distinct friends who listened to that song. If the count reaches the required threshold (for example, three friends), the song becomes a candidate recommendation.
Next, filter out songs the user already listened to on that same day. This is typically done with a LEFT JOIN or NOT EXISTS check against the user's own listening records. The result contains the recommended song_id for each user and day based on collective friend activity.
This approach relies heavily on relational operations: self-expanding friendships, joining activity logs, and using GROUP BY with COUNT(DISTINCT ...). SQL engines handle these operations efficiently when indexes exist on user_id, song_id, and day. Problems like this are classic relational analytics tasks and appear frequently when practicing database queries involving SQL joins and aggregation.
Recommended for interviews: The aggregation-based SQL approach is the expected solution. Interviewers want to see that you can expand bidirectional friendships, join behavioral data, and filter results using grouping and exclusion logic. A brute-force comparison of every user against every friend would be inefficient and difficult to express in SQL, while the join + aggregation strategy shows strong relational query design.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Friend Comparison | O(F × L) | O(1) | Conceptual baseline; rarely used in SQL because it scales poorly with large listening logs. |
| Friendship Expansion + Join + Aggregation | O(n log n) | O(n) | Best general solution. Uses joins and GROUP BY to count friend listens efficiently. |
| Join with NOT EXISTS Filtering | O(n log n) | O(n) | Preferred when explicitly excluding songs already listened to by the user. |