Problem

Table: Sessions

+---------------+----------+
| Column Name   | Type     |
+---------------+----------+
| user_id       | int      |
| session_start | datetime |
| session_end   | datetime |
| session_id    | int      |
| session_type  | enum     |
+---------------+----------+
session_id is column of unique values for this table.
session_type is an ENUM (category) type of (Viewer, Streamer).
This table contains user id, session start, session end, session id and session type.

Write a solution to find the the users who have had at least one consecutive session of the same type (either ‘Viewer ’ or ‘Streamer ‘) with a maximum gap of 12 hours between sessions.

Return the result table ordered byuser_id inascending order.

The result format is in the following example.

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Input: 
Sessions table:
+---------+---------------------+---------------------+------------+--------------+
| user_id | session_start       | session_end         | session_id | session_type | 
+---------+---------------------+---------------------+------------+--------------+
| 101     | 2023-11-01 08:00:00 | 2023-11-01 09:00:00 | 1          | Viewer       |  
| 101     | 2023-11-01 10:00:00 | 2023-11-01 11:00:00 | 2          | Streamer     |   
| 102     | 2023-11-01 13:00:00 | 2023-11-01 14:00:00 | 3          | Viewer       | 
| 102     | 2023-11-01 15:00:00 | 2023-11-01 16:00:00 | 4          | Viewer       | 
| 101     | 2023-11-02 09:00:00 | 2023-11-02 10:00:00 | 5          | Viewer       | 
| 102     | 2023-11-02 12:00:00 | 2023-11-02 13:00:00 | 6          | Streamer     | 
| 101     | 2023-11-02 13:00:00 | 2023-11-02 14:00:00 | 7          | Streamer     | 
| 102     | 2023-11-02 16:00:00 | 2023-11-02 17:00:00 | 8          | Viewer       | 
| 103     | 2023-11-01 08:00:00 | 2023-11-01 09:00:00 | 9          | Viewer       | 
| 103     | 2023-11-02 20:00:00 | 2023-11-02 23:00:00 | 10         | Viewer       | 
| 103     | 2023-11-03 09:00:00 | 2023-11-03 10:00:00 | 11         | Viewer       | 
+---------+---------------------+---------------------+------------+--------------+
Output: 
+---------+
| user_id |
+---------+
| 102     |
| 103     |
+---------+
Explanation:
- User ID 101 will not be included in the final output as they do not have any consecutive sessions of the same session type.
- User ID 102 will be included in the final output as they had two viewer sessions with session IDs 3 and 4, respectively, and the time gap between them was less than 12 hours.
- User ID 103 participated in two viewer sessions with a gap of less than 12 hours between them, identified by session IDs 10 and 11. Therefore, user 103 will be included in the final output.
Output table is ordered by user_id in increasing order.

Solution

Method 1 – Window Functions and Self-Join

Intuition

We need to find users who have at least one pair of consecutive sessions of the same type with a gap of at most 12 hours. We can use window functions (LAG/LEAD) or a self-join to compare each session with the next one for the same user and type.

Approach

  1. For each user and session type, order sessions by start time.
  2. For each session, compare its start time to the previous session’s end time (using LAG or a self-join).
  3. If the session type matches and the gap is <= 12 hours, include the user.
  4. Return distinct user_ids in ascending order.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
SELECT DISTINCT user_id
FROM (
  SELECT user_id, session_type,
         session_start,
         LAG(session_end) OVER (PARTITION BY user_id, session_type ORDER BY session_start) AS prev_end
  FROM Sessions
) t
WHERE prev_end IS NOT NULL
  AND TIMESTAMPDIFF(HOUR, prev_end, session_start) <= 12
ORDER BY user_id;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
SELECT DISTINCT user_id
FROM (
  SELECT user_id, session_type,
         session_start,
         LAG(session_end) OVER (PARTITION BY user_id, session_type ORDER BY session_start) AS prev_end
  FROM Sessions
) t
WHERE prev_end IS NOT NULL
  AND session_start - prev_end <= INTERVAL '12 hours'
ORDER BY user_id;

Complexity

  • ⏰ Time complexity: O(n log n) — Sorting sessions per user and type.
  • 🧺 Space complexity: O(n) — For window function buffers.