We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Exclusive Time of Functions

Difficulty: Medium

Problem Description

Given a list of log messages representing the start and end times of function calls in a single-threaded CPU, return the exclusive time of each function, where the value at each index represents the exclusive time for the function with that ID.

Key Insights

  • Functions are executed in a stack-like manner, where a function can call another function.
  • The exclusive time for a function is the total time it is actively running, not including the time spent in called functions.
  • The logs contain timestamps that help determine the duration of each function's execution.
  • Each "start" log pushes the function onto the stack, and each "end" log pops it, allowing tracking of execution time.

Space and Time Complexity

Time Complexity: O(m), where m is the number of logs, since we process each log once. Space Complexity: O(n), where n is the number of functions, due to the storage of exclusive times and the stack for active function calls.

Solution

To solve the problem, we can use a stack to keep track of the currently executing functions. As we iterate through the logs, we will:

  1. Push the function ID onto the stack when we encounter a "start" log.
  2. Calculate the time spent by the currently executing function when we encounter an "end" log, and update its exclusive time.
  3. Manage time accounting by keeping track of the last timestamp processed.

This approach ensures that we correctly calculate the exclusive time for each function while accounting for nested calls.

Code Solutions

def exclusiveTime(n, logs):
    times = [0] * n
    stack = []
    last_time = 0
    
    for log in logs:
        function_id, status, timestamp = log.split(':')
        function_id = int(function_id)
        timestamp = int(timestamp)
        
        if stack:
            # Update the time for the function at the top of the stack
            times[stack[-1]] += timestamp - last_time
        
        if status == "start":
            stack.append(function_id)
            last_time = timestamp
        else:  # status == "end"
            times[stack.pop()] += 1 + timestamp - last_time
            last_time = timestamp + 1
            
    return times
← Back to All Questions