Table: Friendship
+---------------+---------+ | Column Name | Type | +---------------+---------+ | user1_id | int | | user2_id | int | +---------------+---------+ (user1_id, user2_id) is the primary key (combination of columns with unique values) for this table. Each row of this table indicates that the users user1_id and user2_id are friends.
Table: Likes
+-------------+---------+ | Column Name | Type | +-------------+---------+ | user_id | int | | page_id | int | +-------------+---------+ (user_id, page_id) is the primary key (combination of columns with unique values) for this table. Each row of this table indicates that user_id likes page_id.
You are implementing a page recommendation system for a social media website. Your system will recommend a page to user_id if the page is liked by at least one friend of user_id and is not liked by user_id.
Write a solution to find all the possible page recommendations for every user. Each recommendation should appear as a row in the result table with these columns:
user_id: The ID of the user that your system is making the recommendation to.page_id: The ID of the page that will be recommended to user_id.friends_likes: The number of the friends of user_id that like page_id.Return the result table in any order.
The result format is in the following example.
Example 1:
Input: Friendship table: +----------+----------+ | user1_id | user2_id | +----------+----------+ | 1 | 2 | | 1 | 3 | | 1 | 4 | | 2 | 3 | | 2 | 4 | | 2 | 5 | | 6 | 1 | +----------+----------+ Likes table: +---------+---------+ | user_id | page_id | +---------+---------+ | 1 | 88 | | 2 | 23 | | 3 | 24 | | 4 | 56 | | 5 | 11 | | 6 | 33 | | 2 | 77 | | 3 | 77 | | 6 | 88 | +---------+---------+ Output: +---------+---------+---------------+ | user_id | page_id | friends_likes | +---------+---------+---------------+ | 1 | 77 | 2 | | 1 | 23 | 1 | | 1 | 24 | 1 | | 1 | 56 | 1 | | 1 | 33 | 1 | | 2 | 24 | 1 | | 2 | 56 | 1 | | 2 | 11 | 1 | | 2 | 88 | 1 | | 3 | 88 | 1 | | 3 | 23 | 1 | | 4 | 88 | 1 | | 4 | 77 | 1 | | 4 | 23 | 1 | | 5 | 77 | 1 | | 5 | 23 | 1 | +---------+---------+---------------+ Explanation: Take user 1 as an example: - User 1 is friends with users 2, 3, 4, and 6. - Recommended pages are 23 (user 2 liked it), 24 (user 3 liked it), 56 (user 3 liked it), 33 (user 6 liked it), and 77 (user 2 and user 3 liked it). - Note that page 88 is not recommended because user 1 already liked it. Another example is user 6: - User 6 is friends with user 1. - User 1 only liked page 88, but user 6 already liked it. Hence, user 6 has no recommendations. You can recommend pages for users 2, 3, 4, and 5 using a similar process.
Problem Overview: You need to recommend pages to a user based on what their friends like. A page should appear in the result if at least one of the user's friends liked it, but the user has not liked it yet. The tables typically include a friendship relation and a page-like relation, so the task becomes joining these relationships and filtering out pages the user already interacted with.
Approach 1: Join Friends with Likes + Exclusion Filter (SQL Join Strategy) (Time: O(F + L), Space: O(F))
The core idea is to first identify all friends of the target user from the friendship table, then check which pages those friends liked. Because friendships can be stored as pairs (user1_id, user2_id), you usually normalize the relationship using a UNION so each friendship becomes a consistent (user_id, friend_id) mapping. Once you have the friend list, join it with the Likes table to retrieve all pages liked by those friends.
Next, remove pages the user has already liked. This is typically done using a NOT IN or NOT EXISTS subquery against the user's own likes. Finally, aggregate by page_id using GROUP BY and count how many friends liked each page. The grouping step helps rank or prioritize pages based on how many friends interacted with them.
This approach relies heavily on relational operations: joins to connect friendships with likes, filtering to remove already-liked pages, and aggregation to compute recommendation strength. Database engines optimize joins well when indexes exist on user_id and page_id, making the query efficient even with large datasets.
The key insight is converting the social graph into a simple relational pipeline: friends → their likes → remove user's likes → aggregate recommendations. This pattern appears frequently in recommendation systems and social feed ranking.
Recommended for interviews: The join + aggregation approach is what interviewers expect for SQL-based problems. It shows you understand relational modeling, filtering with NOT EXISTS, and grouping with COUNT. A naive approach that scans likes first demonstrates basic understanding, but structuring the query around the friend relationship demonstrates stronger database reasoning. Concepts here overlap with SQL Joins, GROUP BY aggregation, and database query optimization.
MySQL
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Scan with Subqueries | O(F * L) | O(1) | Small datasets or when writing quick exploratory queries without heavy joins |
| Friend Join + Likes Aggregation (Optimal SQL) | O(F + L) | O(F) | General case. Efficient when indexes exist on user_id and page_id and when computing recommendations from social graphs |
| CTE with Normalized Friendship Graph | O(F + L) | O(F) | Best for readability when friendships are stored in two-directional pairs and need normalization |
Leetcode HARD 1892 - Page Recommendations 2 : Using JOINs to FILTER TABLES - Explained by EDS • Everyday Data Science • 763 views views
Practice Page Recommendations II with our built-in code editor and test cases.
Practice on FleetCode