Leetcodify Friends Recommendations - Practice Coding Problems

Leetcodify Friends Recommendations - Problem

Database Hard

You are working on a music streaming platform called Leetcodify. Your task is to create a friend recommendation system based on listening habits.

Tables:

Listens: Records when users listen to songs on specific days
Friendship: Tracks existing friendships between users

Recommendation Rules:

Users x and y are not already friends
Users x and y listened to the same 3 or more different songs on the same day
Recommendations are bidirectional (if x should be recommended to y, then y should also be recommended to x)
No duplicate recommendations

Return all friend recommendations with columns user_id and recommended_id.

Table Schema

Listens

Column Name	Type	Description
`user_id`	int	ID of the user who listened
`song_id`	int	ID of the song that was played
`day`	date	Date when the song was listened to

Primary Key: None (table may contain duplicates)

Note: Records user listening history with possible duplicates

Friendship

Column Name	Type	Description
`user1_id` PK	int	First user in friendship (always smaller ID)
`user2_id` PK	int	Second user in friendship (always larger ID)

Primary Key: (user1_id, user2_id)

Note: Stores friendships where user1_id < user2_id

Input & Output

Example 1 — Basic Friend Recommendations

Input Tables:

Listens

user_id	song_id	day
1	10	2024-03-15
1	11	2024-03-15
1	12	2024-03-15
2	10	2024-03-15
2	11	2024-03-15
2	12	2024-03-15
3	10	2024-03-15
3	11	2024-03-15

Friendship

user1_id	user2_id
1	3

Output:

user_id	recommended_id
1	2
2	1

💡 Note:

Users 1 and 2 both listened to songs 10, 11, and 12 on 2024-03-15 (3 shared songs), and they are not friends. Users 1 and 3 listened to songs 10 and 11 together (only 2 shared songs), which doesn't meet the 3+ requirement. Also, users 1 and 3 are already friends, so no recommendation is made.

Example 2 — Multiple Days and No Recommendations

Input Tables:

Listens

user_id	song_id	day
1	10	2024-03-15
1	11	2024-03-15
2	10	2024-03-16
2	11	2024-03-16
3	20	2024-03-15
4	21	2024-03-15

Friendship

user1_id	user2_id
1	2

Output:

user_id	recommended_id

💡 Note:

No recommendations are made because: Users 1 and 2 listened to same songs but on different days (must be same day). Users 3 and 4 listened on the same day but to completely different songs. No pair of users has 3+ shared songs on the same day while not being friends.

Constraints

1 ≤ user_id ≤ 1000
1 ≤ song_id ≤ 100000
day is a valid date
In Friendship table, user1_id < user2_id
Listens table may contain duplicate rows

Visualization

Tap to expand

Understanding the Visualization

Input Tables

Listens (user listening history) and Friendship (existing connections)

Find Overlaps

Self-join on same songs and same day, count distinct shared songs

Apply Rules

Filter for 3+ shared songs, exclude existing friends, make bidirectional

Key Takeaway

🎯 Key Insight: Use self-join on listening data to find music compatibility, then exclude existing relationships

Asked in

S Spotify 28 A Amazon 22 M Meta 18 A Apple 15

Use CTE with self-join on Listens table to find users with 3+ shared songs on same day. LEFT JOIN with Friendship to exclude existing friends, then UNION for bidirectional recommendations.

Table Schema

Listens

Column Name	Type	Description
`user_id`	int	ID of the user who listened
`song_id`	int	ID of the song that was played
`day`	date	Date when the song was listened to

Primary Key: None (table may contain duplicates)

Note: Records user listening history with possible duplicates

Friendship

Column Name	Type	Description
`user1_id` PK	int	First user in friendship (always smaller ID)
`user2_id` PK	int	Second user in friendship (always larger ID)

Primary Key: (user1_id, user2_id)

Note: Stores friendships where user1_id < user2_id

Common Approaches

Approach	Time	Space	Notes
✓ CTE with Cross Join and Aggregation	O(L² × F)	O(L²)	Use CTE to find song overlaps, then filter out existing friendships

CTE with Cross Join and Aggregation — Algorithm Steps

Step 1: Cross join Listens table to find users who listened to same songs on same day
Step 2: Group by user pair and day, count distinct shared songs
Step 3: Filter pairs with 3+ shared songs and ensure user1 ≠ user2
Step 4: LEFT JOIN with Friendship to exclude existing friends
Step 5: Generate bidirectional recommendations

Visualization

Tap to expand

Step-by-Step Walkthrough

Join Listens

Find users with same songs on same day

Count & Filter

Keep pairs with 3+ shared songs

Exclude Friends

Remove existing friendships

Bidirectional

Create both directions

Code -

solution.c — C

Time & Space Complexity

Time Complexity

⏱️

O(L² × F)

L² for cross join of Listens, F for friendship lookup

✓ Linear Growth

Space Complexity

O(L²)

Intermediate cross join results

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Table Schema

Input & Output

Constraints

Visualization

Related Problems

Table Schema

Common Approaches

CTE with Cross Join and Aggregation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler