Average Time of Process per Machine

Difficulty: Easy | Acceptance: 66.80% | Paid: No Topics: Database

Table: Activity

+----------------+---------+ | Column Name | Type | +----------------+---------+ | machine_id | int | | process_id | int | | thread_id | int | | activity_type | enum | | timestamp | float | +----------------+---------+ The table shows the user activities for a factory. (machine_id, process_id, thread_id) is the primary key of this table. activity_type is an ENUM (type) of (‘start’, ‘end’). timestamp is a float representing seconds. Each row represents a thread running a process on a machine.

Write a solution to find the average time each machine takes to complete a process.

The time to complete a process is the ‘end’ timestamp minus the ‘start’ timestamp for the same process_id and machine_id. The average time is calculated per machine.

Return the result table in any order.

The result format is in the following example.

• Examples
• Constraints
• Approach 1: Self Join and Aggregation
• Approach 2: Conditional Aggregation

Examples

Example 1:

Input: Activity table: +------------+------------+------------+--------------+-----------+ | machine_id | process_id | thread_id | activity_type| timestamp | +------------+------------+------------+--------------+-----------+ | 0 | 0 | 0 | start | 0.712 | | 0 | 0 | 0 | end | 4.52 | | 0 | 1 | 0 | start | 3.14 | | 0 | 1 | 0 | end | 5.12 | | 1 | 0 | 0 | start | 0.55 | | 1 | 0 | 0 | end | 1.55 | | 1 | 1 | 0 | start | 0.43 | | 1 | 1 | 0 | end | 1.42 | | 2 | 0 | 0 | start | 4.1 | | 2 | 0 | 0 | end | 4.512 | | 2 | 1 | 0 | start | 2.5 | | 2 | 1 | 0 | end | 5.0 | +------------+------------+------------+--------------+-----------+

Output: +------------+-----------------+ | machine_id | processing_time | +------------+-----------------+ | 0 | 3.74 | | 1 | 0.995 | | 2 | 1.456 | +------------+-----------------+ Explanation:

• There are 3 machines running 2 processes each.
• Machine 0:
  • Process 0: end time 4.52 - start time 0.712 = 3.808
  • Process 1: end time 5.12 - start time 3.14 = 1.98
  • Average: (3.808 + 1.98) / 2 = 3.74
• Machine 1:
  • Process 0: end time 1.55 - start time 0.55 = 1.0
  • Process 1: end time 1.42 - start time 0.43 = 0.99
  • Average: (1.0 + 0.99) / 2 = 0.995
• Machine 2:
  • Process 0: end time 4.512 - start time 4.1 = 0.412
  • Process 1: end time 5.0 - start time 2.5 = 2.5
  • Average: (0.412 + 2.5) / 2 = 1.456

Constraints

machine_id is between 0 and 1000.
process_id is between 0 and 1000.
thread_id is between 0 and 1000.
timestamp is a positive float.
activity_type is either 'start' or 'end'.

Self Join and Aggregation

Intuition We can join the table with itself to match the ‘start’ and ‘end’ rows for the same process and machine. By subtracting the start timestamp from the end timestamp, we get the duration for each process. Finally, we group by machine_id to calculate the average duration.

Steps

• Join the Activity table with itself on machine_id and process_id.
• Filter the joined table so that the left side represents ‘start’ activity and the right side represents ‘end’ activity.
• Calculate the difference between the timestamps (end - start).
• Group by machine_id and compute the average of these differences.
• Round the result to 3 decimal places.

# Write your MySQL query statement below
query = """
SELECT
    a1.machine_id,
    ROUND(AVG(a2.timestamp - a1.timestamp), 3) AS processing_time
FROM
    Activity a1
JOIN
    Activity a2 ON a1.machine_id = a2.machine_id AND a1.process_id = a2.process_id
WHERE
    a1.activity_type = 'start' AND a2.activity_type = 'end'
GROUP BY
    a1.machine_id
"""

Complexity

• Time: O(N) where N is the number of rows in the Activity table, assuming a hash join is used.
• Space: O(N) for the intermediate join result.
• Notes: This approach is intuitive and easy to read. It effectively pairs start and end events.

Conditional Aggregation

Intuition Instead of joining the table, we can pivot the data using conditional aggregation. For each machine and process, we can extract the start timestamp and the end timestamp into separate columns within the same row. Then, we simply subtract and average.

Steps

• Group by machine_id and process_id.
• Use MAX(CASE…) or similar aggregate functions to get the ‘start’ timestamp and ‘end’ timestamp for each group.
• This creates a view where each row has machine_id, process_id, start_time, and end_time.
• Calculate the duration (end_time - start_time).
• Group by machine_id on this derived table to calculate the average duration.
• Round the result to 3 decimal places.

# Write your MySQL query statement below
query = """
SELECT
    machine_id,
    ROUND(AVG(end_time - start_time), 3) AS processing_time
FROM (
    SELECT
        machine_id,
        process_id,
        MAX(CASE WHEN activity_type = 'end' THEN timestamp END) AS end_time,
        MAX(CASE WHEN activity_type = 'start' THEN timestamp END) AS start_time
    FROM
        Activity
    GROUP BY
        machine_id, process_id
) sub
GROUP BY
    machine_id
"""

Complexity

• Time: O(N) where N is the number of rows in the Activity table.
• Space: O(N) for the intermediate subquery result.
• Notes: This approach avoids the overhead of a join and can be more efficient in some database engines, especially if the table is already sorted or indexed by the grouping keys.