Domain 1EasyCORE

Ad-Free Sessions

The problem requires us to determine the number of ad-free sessions for users in a given dataset. An ad-free session is defined as a session where no ads were shown. The input consists of two tables: `Sessions` and `Ads`. The `Sessions` table contains information about user sessions, including a unique session ID, user ID, and session start time. The `Ads` table contains records of ads shown during sessions, with fields for ad ID, session ID, and ad type.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#**FAANG asked:** 1

1809. Ad-Free Sessions

Model: qwen2.5-coder:14b
Topics:
FAANG asked: 1
Acceptance rate: 71.5%


Problem Breakdown

The problem requires us to determine the number of ad-free sessions for users in a given dataset. An ad-free session is defined as a session where no ads were shown. The input consists of two tables: Sessions and Ads. The Sessions table contains information about user sessions, including a unique session ID, user ID, and session start time. The Ads table contains records of ads shown during sessions, with fields for ad ID, session ID, and ad type.

Inputs:

  • Sessions table:

    • session_id: Unique identifier for each session.
    • user_id: Identifier for the user who had the session.
    • start_time: Timestamp when the session started.
  • Ads table:

    • ad_id: Unique identifier for each ad.
    • session_id: Identifier linking the ad to a specific session.
    • ad_type: Type of ad shown (e.g., banner, video).

Outputs:

  • The number of ad-free sessions for each user.

Implicit Constraints/Edge Cases:

  • There might be users with no sessions or no ads in their sessions.
  • Sessions can have multiple ads, but we only care if there are any ads at all.
  • The dataset could be large, so the solution should be efficient in terms of time and space complexity.

Intuition

A brute-force approach would involve iterating over each session and checking if it has any associated ads. This would require joining the Sessions table with the Ads table for every session, which could be inefficient for large datasets due to its O(n*m) complexity, where n is the number of sessions and m is the average number of ads per session.

The key insight is to use a set or hash map to store all session IDs that have ads. Then, we can iterate over the Sessions table once, checking if each session ID is in the set of ad-containing sessions. This reduces the complexity to O(n + m), where n is the number of sessions and m is the number of ads.

Approach

  1. Create a Set of Ad-Containing Sessions:

    • Join the Sessions table with the Ads table on session_id.
    • Extract unique session_ids from this joined result to form a set of ad-containing sessions.
  2. Count Ad-Free Sessions for Each User:

    • Iterate over each session in the Sessions table.
    • For each session, check if its session_id is not in the set of ad-containing sessions.
    • If it’s not in the set, increment a counter for that user.
  3. Return the Count of Ad-Free Sessions per User:

    • Group the results by user_id and return the count of ad-free sessions for each user.

Complexity Analysis

  • Time Complexity: O(n + m), where n is the number of sessions and m is the number of ads. This is because we iterate over all sessions once to build the set and then iterate over all sessions again to count ad-free sessions.

  • Space Complexity: O(m) for storing the set of ad-containing session IDs.

Solution

import pandas as pd

def count_ad_free_sessions(sessions: pd.DataFrame, ads: pd.DataFrame) -> pd.DataFrame:
    # Step 1: Create a set of ad-containing sessions
    ad_containing_sessions = set(ads['session_id'].unique())
    
    # Step 2: Count ad-free sessions for each user
    sessions['ad_free'] = ~sessions['session_id'].isin(ad_containing_sessions)
    ad_free_counts = sessions.groupby('user_id')['ad_free'].sum().reset_index(name='ad_free_session_count')
    
    return ad_free_counts

# Example usage:
# sessions_df = pd.DataFrame({'session_id': [1, 2, 3], 'user_id': [101, 102, 101]})
# ads_df = pd.DataFrame({'ad_id': [10, 20], 'session_id': [1, 2]})
# result = count_ad_free_sessions(sessions_df, ads_df)
# print(result)

Edge Cases Handled

  • No Ads: If there are no ads in the Ads table, all sessions will be considered ad-free.
  • No Sessions: If there are no sessions in the Sessions table, the result should be an empty DataFrame.
  • Multiple Ads per Session: The solution correctly handles sessions with multiple ads by using a set to track any session that has at least one ad.