grid47 Exploring patterns and algorithms
Sep 4, 2024
7 min read
Solution to LeetCode 636: Exclusive Time of Functions Problem
You are given a list of logs representing the execution of n functions on a single-threaded CPU. Each log contains a function’s ID, whether the function has started or ended, and the timestamp of the event. The goal is to calculate the exclusive time of each function, which is the total time the function spends executing, excluding the time spent on other nested function calls.
Problem
Approach
Steps
Complexity
Input: You are given a list of logs formatted as strings with the structure {function_id}:{start|end}:{timestamp}. The logs indicate when a function starts or ends at a given timestamp.
Example: n = 2, logs = ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]
Constraints:
• 1 <= n <= 100
• 1 <= logs.length <= 500
• 0 <= function_id < n
• 0 <= timestamp <= 10^9
• No two start events will happen at the same timestamp.
• No two end events will happen at the same timestamp.
Output: Return the exclusive time for each function as an array, where the value at the ith index represents the exclusive time for function i.
Example: [3, 4]
Constraints:
• The output will be an array of n integers representing the exclusive times for each function.
Goal: Calculate the exclusive time for each function based on the logs.
Steps:
• Iterate through the logs and simulate the execution of the functions using a stack.
• Track the start and end times for each function call and compute the total time spent executing each function.
Goal: The solution must handle all values of n and logs within the given constraints efficiently.
Steps:
• The function must process logs of length up to 500 efficiently.
• Ensure that the time spent on each function is calculated correctly, considering recursive calls.
• Explanation: Function 0 starts at time 0 and runs for 2 units of time, function 1 starts at time 2 and runs for 4 units. Function 0 resumes at time 6 and runs for 1 unit, making the total exclusive time of function 0 equal to 3, and function 1 equal to 4.
Approach: We use a stack to simulate the function calls and calculate the exclusive time by tracking the start and end timestamps.
Observations:
• Each function's exclusive time needs to account for recursive calls and nested execution times.
• By using a stack to keep track of function calls and their start times, we can easily calculate the total exclusive time for each function.
Steps:
• Initialize an array to store the exclusive time of each function.
• Iterate through the logs, processing start and end events and adjusting the exclusive time for the functions accordingly.
Empty Inputs:
• The input will not be empty, as logs always contain at least one function call.
Large Inputs:
• The solution should be efficient enough to handle up to 500 logs.
Special Values:
• Consider cases with recursive function calls where a function calls itself multiple times.
Constraints:
• Ensure the solution is efficient for the given problem size.
vector<int> exclusiveTime(int n, vector<string>& logs) {
This line defines the function `exclusiveTime` that takes an integer `n` (number of tasks) and a vector of logs. It returns a vector of integers representing the exclusive time for each task.
2 : Variable Initialization
vector<int> ans(n, 0);
A vector `ans` is initialized with size `n` (number of tasks), and all elements are set to 0. This will store the exclusive time for each task.
3 : Stack Declaration
stack<Log> stk;
A stack `stk` is declared to hold `Log` objects, which will track the tasks as they are being processed. The stack is used to manage nested tasks.
4 : Log Iteration
for(string log : logs) {
A `for` loop is used to iterate through each log in the `logs` vector, where each log is processed to extract task information.
5 : Log Parsing
stringstream ss(log);
A stringstream `ss` is created from the current log to easily extract individual components (task ID, status, and time).
6 : Log Variables Declaration
string num, adj, time;
Three string variables `num`, `adj`, and `time` are declared to hold the task ID, status (start or end), and time values extracted from the log.
7 : Extract Task ID
getline(ss, num, ':');
The task ID (`num`) is extracted from the log by reading until the first colon `:`.
8 : Extract Status
getline(ss, adj, ':');
The task status (`adj`), which indicates whether the task has started or ended, is extracted by reading the next section of the log.
9 : Extract Time
getline(ss, time, ':');
The task time (`time`) is extracted by reading the final section of the log.
10 : Log Item Creation
Log item = { stoi(num), adj, stoi(time) };
A `Log` object is created with the parsed task ID (`num`), status (`adj`), and time (`time`). The `stoi` function is used to convert the `num` and `time` from strings to integers.
11 : Start Task Handling
if(item.status =="start") {
If the task status is 'start', the task is pushed onto the stack, indicating that it has started.
12 : Push Task to Stack
stk.push(item);
The `item` (task) is pushed onto the stack to keep track of the active task.
13 : End Task Handling
} else {
If the task status is not 'start' (i.e., it's 'end'), the function proceeds to handle the task completion.
14 : Assert Task ID Match
assert(stk.top().id == item.id);
This assertion checks that the task ID of the current log matches the task ID of the task at the top of the stack, ensuring that tasks are being ended in the correct order.
15 : Calculate Task Duration
int t = item.time - stk.top().time +1;
The exclusive time for the task is calculated as the difference between the current time and the time of the task at the top of the stack, plus 1.
16 : Add Duration to Task
ans[item.id] += t;
The calculated exclusive time `t` is added to the corresponding task ID in the `ans` vector.
17 : Pop Task from Stack
stk.pop();
The task is removed from the stack after processing its end time.
18 : Handle Nested Task
if(!stk.empty()){
If there are still tasks in the stack (indicating a nested task), the function continues to handle the exclusive time for the parent task.
19 : Assert Parent Task is Start
assert(stk.top().status =="start");
This assertion checks that the task at the top of the stack is a 'start' task, ensuring the parent task is still active.
20 : Subtract Duration from Parent Task
ans[stk.top().id] -= t;
The exclusive time of the parent task is reduced by `t` to ensure the nested task's time is not counted in the parent.
21 : Return Result
return ans;
The function returns the `ans` vector, which contains the exclusive time for each task.
Best Case: O(n)
Average Case: O(m)
Worst Case: O(m)
Description: The time complexity is linear in terms of the number of logs.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the storage of the call stack.
