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:
-
Sessionstable:session_id: Unique identifier for each session.user_id: Identifier for the user who had the session.start_time: Timestamp when the session started.
-
Adstable: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
-
Create a Set of Ad-Containing Sessions:
- Join the
Sessionstable with theAdstable onsession_id. - Extract unique
session_ids from this joined result to form a set of ad-containing sessions.
- Join the
-
Count Ad-Free Sessions for Each User:
- Iterate over each session in the
Sessionstable. - For each session, check if its
session_idis not in the set of ad-containing sessions. - If it’s not in the set, increment a counter for that user.
- Iterate over each session in the
-
Return the Count of Ad-Free Sessions per User:
- Group the results by
user_idand return the count of ad-free sessions for each user.
- Group the results by
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
Adstable, all sessions will be considered ad-free. - No Sessions: If there are no sessions in the
Sessionstable, 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.