Leetcode MEDIUM 3126 - Server Utilization Time CTEs SELF JOIN - Explained by Everyday Data Science
Server Utilization Time - Video Solution
Watch 2 video solutions for Server Utilization Time, a medium level problem involving Database. This walkthrough by Everyday Data Science has 666 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Table: Servers
+----------------+----------+
| Column Name | Type |
+----------------+----------+
| server_id | int |
| status_time | datetime |
| session_status | enum |
+----------------+----------+
(server_id, status_time, session_status) is the primary key (combination of columns with unique values) for this table.
session_status is an ENUM (category) type of ('start', 'stop').
Each row of this table contains server_id, status_time, and session_status.
Write a solution to find the total time when servers were running. The output should be rounded down to the nearest number of full days.
Return the result table in any order.
The result format is in the following example.
Example:
Input:
Servers table:
+-----------+---------------------+----------------+ | server_id | status_time | session_status | +-----------+---------------------+----------------+ | 3 | 2023-11-04 16:29:47 | start | | 3 | 2023-11-05 01:49:47 | stop | | 3 | 2023-11-25 01:37:08 | start | | 3 | 2023-11-25 03:50:08 | stop | | 1 | 2023-11-13 03:05:31 | start | | 1 | 2023-11-13 11:10:31 | stop | | 4 | 2023-11-29 15:11:17 | start | | 4 | 2023-11-29 15:42:17 | stop | | 4 | 2023-11-20 00:31:44 | start | | 4 | 2023-11-20 07:03:44 | stop | | 1 | 2023-11-20 00:27:11 | start | | 1 | 2023-11-20 01:41:11 | stop | | 3 | 2023-11-04 23:16:48 | start | | 3 | 2023-11-05 01:15:48 | stop | | 4 | 2023-11-30 15:09:18 | start | | 4 | 2023-11-30 20:48:18 | stop | | 4 | 2023-11-25 21:09:06 | start | | 4 | 2023-11-26 04:58:06 | stop | | 5 | 2023-11-16 19:42:22 | start | | 5 | 2023-11-16 21:08:22 | stop | +-----------+---------------------+----------------+
Output:
+-------------------+ | total_uptime_days | +-------------------+ | 1 | +-------------------+
Explanation:
- For server ID 3:
- From 2023-11-04 16:29:47 to 2023-11-05 01:49:47: ~9.3 hours
- From 2023-11-25 01:37:08 to 2023-11-25 03:50:08: ~2.2 hours
- From 2023-11-04 23:16:48 to 2023-11-05 01:15:48: ~1.98 hours
- For server ID 1:
- From 2023-11-13 03:05:31 to 2023-11-13 11:10:31: ~8 hours
- From 2023-11-20 00:27:11 to 2023-11-20 01:41:11: ~1.23 hours
- For server ID 4:
- From 2023-11-29 15:11:17 to 2023-11-29 15:42:17: ~0.52 hours
- From 2023-11-20 00:31:44 to 2023-11-20 07:03:44: ~6.53 hours
- From 2023-11-30 15:09:18 to 2023-11-30 20:48:18: ~5.65 hours
- From 2023-11-25 21:09:06 to 2023-11-26 04:58:06: ~7.82 hours
- For server ID 5:
- From 2023-11-16 19:42:22 to 2023-11-16 21:08:22: ~1.43 hours
Approach Overview
Problem Overview: Each row represents a server event (start or stop) with a timestamp. The task is to compute the total time each server was actively running by pairing every start event with its corresponding stop event and summing the duration.
Approach 1: Self Join Event Pairing (O(n log n) time, O(n) space)
One straightforward SQL strategy pairs start rows with the next stop row for the same server using a self join. You join the table with itself on server_id and ensure the stop timestamp is greater than the start timestamp. Then filter to keep the nearest stop event and compute stop_time - start_time. Finally, aggregate the durations with SUM() grouped by server. This works but requires extra filtering logic to ensure the correct pairing and usually involves sorting or subqueries.
Because every event may compare with multiple later rows, the query becomes heavier on large logs. The logic is also harder to maintain when event ordering matters. This method still works in relational systems without strong window function support.
Approach 2: Window Function Pairing with LEAD (O(n log n) time, O(n) space)
The clean solution uses SQL window functions. Partition the events by server_id and order them by timestamp. Apply LEAD(timestamp) to fetch the timestamp of the next event for the same server. When the current row is a start event, the next row should be the corresponding stop. The difference between these timestamps gives the utilization duration for that session.
After computing these session durations, aggregate them with SUM() per server. Window functions handle event pairing in a single pass over each server's ordered events, making the query concise and reliable. This approach is the standard pattern for event log problems involving start/stop intervals.
This technique relies on ordered partitions and sequential access, which is exactly what SQL window functions are designed for. Problems involving time intervals, sessionization, or log processing frequently use LEAD or LAG from window functions inside relational databases. Efficient querying and aggregation like this are core patterns in database interview questions.
Recommended for interviews: The window function solution is what interviewers typically expect. It shows you understand event sequencing and modern SQL features. Explaining the self-join approach first demonstrates reasoning about pairing events, but implementing it with LEAD shows stronger SQL fluency and cleaner query design.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Self Join Event Pairing | O(n log n) | O(n) | When window functions are unavailable or when using older SQL systems |
| Window Functions with LEAD | O(n log n) | O(n) | Best approach for ordered event logs and modern SQL databases like MySQL/PostgreSQL |