Domain 2MediumMEDIUM

Page Recommendations

LeetCode problem 1264: Page Recommendations (medium).

Domain: medium•Updated: 2026-09-13
#Algorithms

Problem Breakdown

The problem asks us to generate page recommendations based on user view history. Although the SQL schema header was empty in the prompt description for this specific walkthrough, standard problems with this title (often associated with “Page Views” analytics) typically involve a Views table containing (user_id, page_id) pairs.

Inputs:

  • A list of records representing views: each record contains a unique user identifier and a page identifier they viewed.
  • Implicitly, we assume the goal is to recommend pages that have been viewed by other users but not yet by the current user (or based on popularity thresholds if specified). For this walkthrough, I will implement logic to identify popular or co-viewed pages suitable for recommendation.

Outputs:

  • A list of recommendations mapping each user_id to a set of recommended page_ids.

Constraints & Edge Cases:

  1. Duplicates: The input may contain duplicate (user_id, page_id) pairs (same user viewing same page multiple times). We must handle this by treating views as sets or using counts that ignore duplicates for eligibility.
  2. Empty Input: If no views exist, the output should be empty.
  3. Single User/View: A user who has viewed everything available gets zero recommendations (or all pages if we recommend based on popularity).
  4. Overflow: While Python handles large integers automatically, in a SQL context this would require BIGINT. In Python logic, memory usage is the primary concern with very large datasets.

Intuition

Brute Force Approach: For every user and page combination they haven’t seen yet, iterate through all other users’ view history to see if that specific page was viewed by anyone else.

  • Complexity: If UU is unique users and PP is pages, checking each pair against others leads to roughly O(U×P)O(U \times P) or worse depending on implementation (O(N2)O(N^2) where N is total rows). This becomes prohibitively slow for large datasets (e.g., millions of views).

Key Insight: We can decouple the logic into two phases:

  1. Global Aggregation: Identify which pages are “popular” or simply track all unique pages viewed globally and by each user individually using hash maps/sets.
  2. Filtering: For a specific recommendation strategy (e.g., recommend any page not yet seen), we can use set difference operations (AllPages−UserViewsAllPages - UserViews). If the requirement is popularity-based, we pre-calculate view counts per page in O(N)O(N) time and filter based on thresholds.

Optimal Approach: Use dictionary comprehensions to aggregate views per user (sets) and global pages. This allows O(1)O(1) lookups during recommendation generation. The complexity drops significantly compared to nested loops over the raw data rows.

Approach

  1. Data Ingestion & Aggregation:
    • Parse the input views list into a structure that tracks unique views per user (e.g., {user_id: set(page_ids)}).
    • Simultaneously track global page popularity or existence using another dictionary/set to identify “candidate” pages for recommendation.
  2. Recommendation Logic:
    • Iterate through each user_id.
    • For the current user, determine which pages qualify as recommendations (e.g., any page viewed by at least one other user).
    • Collect these into a result list of tuples (user_id, recommended_page).
  3. Result Formatting:
    • Ensure output is sorted or structured consistently for downstream consumption (optional but good practice in interviews).

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the number of view records. We iterate through the input once to build our sets/dictionaries, and then iterate through users/pages again which sums up linearly with respect to unique elements found during ingestion. Set operations are average O(1)O(1).
  • Space Complexity: O(N)O(N) in worst case (storing all views per user). If we only store global page counts or sets of seen pages, it is proportional to the number of unique users and pages (U+PU + P), which is bounded by NN.

Solution

from collections import defaultdict
from typing import List, Tuple, Set

def get_page_recommendations(views: List[Tuple[int, int]]) -> List[Tuple[int, str]]:
    """
    Generates page recommendations for users based on view history.
    
    Assumption (Standard Interview Logic): 
    Recommend a 'page_id' to a user if it has been viewed by at least one other user,
    and the current user has not yet seen that specific page.
    
    Args:
        views: List of tuples (user_id, page_id) representing view history.
        
    Returns:
        List of tuples (user_id, recommended_page).
    """
    if not views:
        return []

    # 1. Aggregate user-specific views and global popularity/existence
    user_views = defaultdict(set)      # Maps user_id -> set of page_ids they viewed
    all_pages_viewed_by_others = set() # Tracks pages seen by anyone (for filtering later if needed)
    
    # We need to know which pages are "available" for recommendation. 
    # Common logic: Recommend any page that exists in the system but not yet with this user?
    # Or recommend popular ones. Let's assume we track global unique pages first,
    # then filter out what each specific user has seen.
    
    all_unique_pages = set()           # All pages ever viewed
    
    for uid, pid in views:
        if pid not in user_views[uid]:  # Avoid adding duplicates to the set immediately
            user_views[uid].add(pid)
        
        all_unique_pages.add(pid)

    recommendations = []
    
    # 2. Generate Recommendations per User
    # Logic: Recommend pages that exist globally but are NOT in this specific user's history.
    # Note: In a real SQL problem, there might be constraints like 'view_count > X'. 
    # Here we implement the set-difference logic for robustness without schema specifics.
    
    for uid in sorted(user_views.keys()):
        current_user_pages = user_views[uid]
        
        # Calculate pages to recommend (Global - Current User's History)
        recommended_for_uid = all_unique_pages - current_user_pages
        
        # Add recommendations as tuples. 
        # If a page is not viewed by anyone else, it might still be valid depending on requirements.
        # Assuming we only want to recommend if the page has some "social proof" or simply exists globally.
        
        for rec_page in recommended_for_uid:
            recommendations.append((uid, rec_page))

    return sorted(recommendations)