#636

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Exclusive Time of Functions

Solve the 'Exclusive Time of Functions' problem using stack-based state management for accurate function execution time calculations.

array stack

Problem Statement

You are given a list of logs where each log describes a function call in the format '{function_id}:{'start'|'end'}:{timestamp}'. Each function starts with a 'start' event and ends with an 'end' event. The goal is to calculate the exclusive time each function has spent executing, where the exclusive time means the time spent on a function excluding the time spent on any nested function calls.

The functions are executed on a single-threaded CPU, and you are provided with the execution order through logs. You need to manage the recursive function calls using a stack, keeping track of which function is executing and when it starts or ends, to compute the total exclusive time for each function.

Examples

Example 1

Input: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]

Output: [3,4]

Function 0 starts at the beginning of time 0, then it executes 2 for units of time and reaches the end of time 1. Function 1 starts at the beginning of time 2, executes for 4 units of time, and ends at the end of time 5. Function 0 resumes execution at the beginning of time 6 and executes for 1 unit of time. So function 0 spends 2 + 1 = 3 units of total time executing, and function 1 spends 4 units of total time executing.

Example 2

Input: n = 1, logs = ["0:start:0","0:start:2","0:end:5","0:start:6","0:end:6","0:end:7"]

Output: [8]

Function 0 starts at the beginning of time 0, executes for 2 units of time, and recursively calls itself. Function 0 (recursive call) starts at the beginning of time 2 and executes for 4 units of time. Function 0 (initial call) resumes execution then immediately calls itself again. Function 0 (2nd recursive call) starts at the beginning of time 6 and executes for 1 unit of time. Function 0 (initial call) resumes execution at the beginning of time 7 and executes for 1 unit of time. So function 0 spends 2 + 4 + 1 + 1 = 8 units of total time executing.

Example 3

Input: n = 2, logs = ["0:start:0","0:start:2","0:end:5","1:start:6","1:end:6","0:end:7"]

Output: [7,1]

Function 0 starts at the beginning of time 0, executes for 2 units of time, and recursively calls itself. Function 0 (recursive call) starts at the beginning of time 2 and executes for 4 units of time. Function 0 (initial call) resumes execution then immediately calls function 1. Function 1 starts at the beginning of time 6, executes 1 unit of time, and ends at the end of time 6. Function 0 resumes execution at the beginning of time 6 and executes for 2 units of time. So function 0 spends 2 + 4 + 1 = 7 units of total time executing, and function 1 spends 1 unit of total time executing.

Constraints

1 <= n <= 100
2 <= logs.length <= 500
0 <= function_id < n
0 <= timestamp <= 109
No two start events will happen at the same timestamp.
No two end events will happen at the same timestamp.
Each function has an "end" log for each "start" log.

Solution Approach

Stack-based Tracking

The problem is best tackled using a stack. As each 'start' event is encountered, push the function ID onto the stack. When an 'end' event is encountered, pop the function ID from the stack, and calculate the time spent executing by subtracting the current timestamp from the previous function's timestamp. This stack allows us to keep track of the current executing function and manage recursion.

Managing Time Calculation

To ensure accurate time calculations, each function's execution time is broken down into the time spent during its call and the time spent during nested recursive calls. When a function starts, the stack tracks it, and when it ends, the time difference between the 'start' and 'end' events is calculated and added to its execution time.

Handling Recursive Calls

Recursive calls are managed by tracking the start and end of each function call in the stack. After calculating the execution time for a function, the remaining time for the current function will be adjusted as it resumes execution after finishing a nested call.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution is O(n) where n is the length of the logs, as each log is processed once. The space complexity is O(n) for storing the stack, which grows as deep as the number of recursive calls.

What Interviewers Usually Probe

The candidate should understand how stack-based state management works for handling recursive function calls.
The solution must clearly handle edge cases such as recursive calls and nested 'start'/'end' events.
Check if the candidate can manage and track time effectively between start and end timestamps.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly manage recursive function calls and nesting.
Not correctly calculating the exclusive time by failing to subtract nested execution times.
Misunderstanding how to manage the stack and the timing of function execution.

Follow-up variants

Consider scenarios where no recursion occurs, and each function call is independent.
The problem may also include a variation with more complex timestamps or additional constraints.
Handling large numbers of logs with time-based constraints can test efficiency and edge case management.

FAQ

What is the main approach for solving the Exclusive Time of Functions problem?

The primary approach is to use stack-based state management to track the start and end times of functions while managing recursion.

How does the stack help in solving the problem?

The stack helps track the function calls and manage their recursive relationships, ensuring that execution times are correctly computed.

Can recursive function calls impact the execution time calculation?

Yes, recursive function calls need to be carefully handled, as the execution time of the calling function is affected by the time spent in its recursive calls.

What is the time complexity of the solution?

The time complexity is O(n), where n is the number of logs, since each log is processed once.

How do you handle nested function calls in this problem?

Nested calls are handled by pushing the function ID onto the stack for each 'start' event and calculating the execution time upon encountering the 'end' event.

terminal

Solution

Solution 1: Stack + Simulation

We define a stack $\textit{stk}$ to store the identifiers of the currently executing functions. We also define an array $\textit{ans}$ to store the exclusive time of each function, initially setting the exclusive time of each function to $0$. We use a variable $\textit{pre}$ to record the previous timestamp.

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        stk = []
        ans = [0] * n
        pre = 0
        for log in logs:
            i, op, t = log.split(":")
            i, cur = int(i), int(t)
            if op[0] == "s":
                if stk:
                    ans[stk[-1]] += cur - pre
                stk.append(i)
                pre = cur
            else:
                ans[stk.pop()] += cur - pre + 1
                pre = cur + 1
        return ans

Continue Practicing

#654 maximum binary tree #682 baseball game #581 shortest unsorted continuous subarray