Problem Description

The "Page Recommendations II" problem involves recommending pages to users based on their friendship network and page likes. You are given two lists: one representing friendships among users, and another representing which users like which pages. For a specific user, you are asked to recommend pages that their friends like, but the user does not already like. The recommendations should not include pages the user already likes, and each recommended page should be unique.

Key constraints:

• Do not recommend pages that the user already likes.
• Each recommendation must be unique (no duplicates).
• Only recommend pages liked by the user's friends.
• There is no requirement to recommend every possible page; just those that match the criteria.

• friendships: List of pairs [user1, user2] indicating a bidirectional friendship between user1 and user2.
• page_likes: List of pairs [user, page] showing which user likes which page.
• user_id: The user for whom you are to recommend pages.

• List of recommended page IDs for user_id, following the above rules.

Thought Process

The main idea is to leverage the user's social network to make personalized recommendations. At first, you might think of simply iterating through all friendships and page likes to find suitable recommendations. However, this brute-force approach can be inefficient, especially if the lists are large.

To optimize, you should:

• Quickly identify all friends of the target user.
• Quickly find all pages liked by those friends.
• Exclude any pages the user already likes.
• Ensure each recommendation is unique.

Solution Approach

Here is a step-by-step strategy to solve the problem efficiently:

1. Build a friendship map:
   • Create a mapping from each user to a set of their friends. Since friendships are bidirectional, for each pair [A, B], add B to A's friend set and A to B's friend set.
2. Build a user-to-pages-liked map:
   • Create a mapping from each user to the set of pages they like. This makes it easy to look up which pages a user likes in constant time.
3. Find all friends of the target user:
   • Use the friendship map to get the set of friends for user_id.
4. Aggregate pages liked by friends:
   • For each friend, get their liked pages and add them to a recommendation set.
5. Exclude pages already liked by the user:
   • Remove from the recommendation set any pages that user_id already likes.
6. Return the recommendations:
   • Convert the set of recommended pages to a list and return it.

We use sets and hash maps because they allow for fast lookups and insertions, making the algorithm efficient even for large inputs.

Example Walkthrough

Sample Input:

• friendships = [[1, 2], [1, 3], [2, 4]]
• page_likes = [[2, 101], [3, 101], [3, 102], [4, 103], [1, 104]]
• user_id = 1

1. Build friendship map:
   • 1: {2, 3}
   • 2: {1, 4}
   • 3: {1}
   • 4: {2}
2. Build user-to-pages-liked map:
   • 2: {101}
   • 3: {101, 102}
   • 4: {103}
   • 1: {104}
3. User 1's friends are 2 and 3.
4. Pages liked by friends:
   • 2: {101}
   • 3: {101, 102}
   Combined: {101, 102}
5. Pages already liked by user 1: {104}
6. Exclude 104 from recommendations. Final set: {101, 102}
7. Return [101, 102] (order does not matter).

Time and Space Complexity

Brute-force approach:

• Time: O(F * P), where F is number of friendships and P is number of page likes (for each friend, scan all page likes).
• Space: O(P) for storing all page likes.

• Time: O(F + P), where F is number of friendships and P is number of page likes. Building the maps and collecting recommendations are all linear operations.
• Space: O(U + P), where U is number of users (for friendship and likes maps) and P is number of page likes.

The optimized approach is much better for large datasets because all lookups and insertions are done in constant time.

Summary

To recommend pages to a user based on their friends' likes, we build efficient mappings using hash maps and sets. This allows us to quickly gather all pages liked by friends, exclude pages the user already likes, and ensure each recommendation is unique. The approach is both efficient and elegant, leveraging basic data structures to solve a real-world recommendation problem.

Code Implementation

def page_recommendations(friendships, page_likes, user_id):
    from collections import defaultdict

    # Build friendship map
    friends_map = defaultdict(set)
    for u, v in friendships:
        friends_map[u].add(v)
        friends_map[v].add(u)

    # Build user to liked pages map
    likes_map = defaultdict(set)
    for u, page in page_likes:
        likes_map[u].add(page)

    # Get user's friends
    friends = friends_map.get(user_id, set())
    # Get pages user already likes
    user_likes = likes_map.get(user_id, set())

    # Gather recommendations
    recommendations = set()
    for friend in friends:
        recommendations.update(likes_map.get(friend, set()))
    # Exclude pages user already likes
    recommendations -= user_likes

    return list(recommendations)
      

#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

vector<int> pageRecommendations(vector<vector<int>>& friendships, vector<vector<int>>& page_likes, int user_id) {
    unordered_map<int, unordered_set<int>> friends_map;
    unordered_map<int, unordered_set<int>> likes_map;

    // Build friendship map
    for (const auto& f : friendships) {
        friends_map[f[0]].insert(f[1]);
        friends_map[f[1]].insert(f[0]);
    }

    // Build likes map
    for (const auto& l : page_likes) {
        likes_map[l[0]].insert(l[1]);
    }

    unordered_set<int> friends = friends_map[user_id];
    unordered_set<int> user_likes = likes_map[user_id];
    unordered_set<int> recommendations;

    for (int friend_id : friends) {
        for (int page : likes_map[friend_id]) {
            if (user_likes.find(page) == user_likes.end()) {
                recommendations.insert(page);
            }
        }
    }

    return vector<int>(recommendations.begin(), recommendations.end());
}
      

import java.util.*;

public class Solution {
    public List<Integer> pageRecommendations(int[][] friendships, int[][] pageLikes, int userId) {
        Map<Integer, Set<Integer>> friendsMap = new HashMap<>();
        Map<Integer, Set<Integer>> likesMap = new HashMap<>();

        // Build friendship map
        for (int[] f : friendships) {
            friendsMap.computeIfAbsent(f[0], k -> new HashSet<>()).add(f[1]);
            friendsMap.computeIfAbsent(f[1], k -> new HashSet<>()).add(f[0]);
        }

        // Build likes map
        for (int[] l : pageLikes) {
            likesMap.computeIfAbsent(l[0], k -> new HashSet<>()).add(l[1]);
        }

        Set<Integer> friends = friendsMap.getOrDefault(userId, new HashSet<>());
        Set<Integer> userLikes = likesMap.getOrDefault(userId, new HashSet<>());
        Set<Integer> recommendations = new HashSet<>();

        for (int friendId : friends) {
            for (int page : likesMap.getOrDefault(friendId, new HashSet<>())) {
                if (!userLikes.contains(page)) {
                    recommendations.add(page);
                }
            }
        }

        return new ArrayList<>(recommendations);
    }
}
      

function pageRecommendations(friendships, pageLikes, userId) {
    const friendsMap = new Map();
    const likesMap = new Map();

    // Build friendship map
    for (const [u, v] of friendships) {
        if (!friendsMap.has(u)) friendsMap.set(u, new Set());
        if (!friendsMap.has(v)) friendsMap.set(v, new Set());
        friendsMap.get(u).add(v);
        friendsMap.get(v).add(u);
    }

    // Build likes map
    for (const [u, page] of pageLikes) {
        if (!likesMap.has(u)) likesMap.set(u, new Set());
        likesMap.get(u).add(page);
    }

    const friends = friendsMap.get(userId) || new Set();
    const userLikes = likesMap.get(userId) || new Set();
    const recommendations = new Set();

    for (const friend of friends) {
        const friendLikes = likesMap.get(friend) || new Set();
        for (const page of friendLikes) {
            if (!userLikes.has(page)) {
                recommendations.add(page);
            }
        }
    }

    return Array.from(recommendations);
}