Watch the video solution for Ad-Free Sessions, a easy level problem involving Database. This walkthrough by Everyday Data Science has 1,905 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Table: Playback
+-------------+------+ | Column Name | Type | +-------------+------+ | session_id | int | | customer_id | int | | start_time | int | | end_time | int | +-------------+------+ session_id is the column with unique values for this table. customer_id is the ID of the customer watching this session. The session runs during the inclusive interval between start_time and end_time. It is guaranteed that start_time <= end_time and that two sessions for the same customer do not intersect.
Table: Ads
+-------------+------+ | Column Name | Type | +-------------+------+ | ad_id | int | | customer_id | int | | timestamp | int | +-------------+------+ ad_id is the column with unique values for this table. customer_id is the ID of the customer viewing this ad. timestamp is the moment of time at which the ad was shown.
Write a solution to report all the sessions that did not get shown any ads.
Return the result table in any order.
The result format is in the following example.
Example 1:
Input: Playback table: +------------+-------------+------------+----------+ | session_id | customer_id | start_time | end_time | +------------+-------------+------------+----------+ | 1 | 1 | 1 | 5 | | 2 | 1 | 15 | 23 | | 3 | 2 | 10 | 12 | | 4 | 2 | 17 | 28 | | 5 | 2 | 2 | 8 | +------------+-------------+------------+----------+ Ads table: +-------+-------------+-----------+ | ad_id | customer_id | timestamp | +-------+-------------+-----------+ | 1 | 1 | 5 | | 2 | 2 | 17 | | 3 | 2 | 20 | +-------+-------------+-----------+ Output: +------------+ | session_id | +------------+ | 2 | | 3 | | 5 | +------------+ Explanation: The ad with ID 1 was shown to user 1 at time 5 while they were in session 1. The ad with ID 2 was shown to user 2 at time 17 while they were in session 4. The ad with ID 3 was shown to user 2 at time 20 while they were in session 4. We can see that sessions 1 and 4 had at least one ad. Sessions 2, 3, and 5 did not have any ads, so we return them.
Problem Overview: You’re given playback sessions and ad events for each customer. A session is considered ad‑free if no ad timestamp falls between the session’s start_time and end_time for the same customer. The task is to return the session_id of all sessions where this condition holds.
Approach 1: NOT EXISTS Anti-Subquery (O(P * A) without indexes, ~O(P log A) with indexes)
Scan each session in the Playback table and check whether an ad exists for the same customer_id within the session time range. A correlated subquery with NOT EXISTS filters out sessions that contain at least one matching ad. The key idea is that the database stops searching as soon as it finds a matching row, making this efficient with proper indexes on (customer_id, timestamp). This pattern is a classic anti-join used frequently in SQL and database interview problems.
Approach 2: LEFT JOIN with NULL Filter (O(P * A) without indexes, ~O(P log A) with indexes)
Another way is performing a LEFT JOIN between Playback and Ads on matching customer_id and a timestamp range condition: Ads.timestamp BETWEEN Playback.start_time AND Playback.end_time. If a session has no matching ad rows, the joined columns from Ads remain NULL. Filtering rows where the ad column is NULL keeps only ad‑free sessions. This approach expresses the same anti-join logic but through a join operation, which some developers find easier to read when working with SQL joins.
Recommended for interviews: The NOT EXISTS solution is typically preferred. It directly models the requirement: return sessions where no ad exists in the time range. Interviewers often expect this form because it clearly communicates the anti-join logic and avoids accidental duplicates that can appear with joins if grouping is not handled carefully.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| NOT EXISTS Anti-Subquery | O(P * A) worst case, ~O(P log A) with index | O(1) | Best general solution. Clear anti-join logic and efficient with indexes. |
| LEFT JOIN + NULL Filter | O(P * A) worst case, ~O(P log A) with index | O(1) | Useful when you prefer explicit joins or when combining with other joined tables. |
