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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Exclusive Time of Functions

Number: 636

Difficulty: Medium

Paid? No

Companies: Meta, LinkedIn, Amazon, Google, IBM, Snap, Uber

Problem Description

Given a list of logs representing the start and end times of function calls on a single-threaded CPU, compute the exclusive time spent in each function. The exclusive time for a function is the sum of execution times for all instances of that function, excluding the time spent executing other functions called within it.

Key Insights

  • Use a stack to simulate function calls; the top of the stack represents the currently executing function.
  • When a function starts while another is running, update the exclusive time of the currently running function.
  • For an "end" log, add the elapsed time (including the current timestamp) to the function on top of the stack.
  • Keep track of the previous timestamp to calculate elapsed durations correctly.

Space and Time Complexity

Time Complexity: O(n) where n is the number of log entries. Space Complexity: O(n) in the worst-case scenario due to the stack.

Solution

We use a stack to track the active functions. As we iterate through each log:

  1. For a "start" log, if there is a function currently executing (top of the stack), update its exclusive time with the time elapsed since the last timestamp.
  2. Then push the new function onto the stack and update the previous timestamp.
  3. For an "end" log, pop the completed function from the stack and update its exclusive time by adding the elapsed time plus one (to account for the inclusive end timestamp). Then update the previous timestamp to one more than the current timestamp. This approach efficiently tracks the execution time intervals for each function.

Code Solutions

# Python solution for Exclusive Time of Functions

def exclusiveTime(n, logs):
    # Initialize result array with zeros for each function
    result = [0] * n
    # Stack to keep track of the function ids
    stack = []
    # Previous timestamp to calculate elapsed time
    prev_time = 0
    
    # Process each log entry
    for log in logs:
        # Split the log string into parts
        fn_id, typ, time_str = log.split(":")
        curr_time = int(time_str)
        fn_id = int(fn_id)
        
        if typ == "start":
            # If there is a function currently running, update its exclusive time
            if stack:
                result[stack[-1]] += curr_time - prev_time
            # Push the new function id onto the stack
            stack.append(fn_id)
            # Update previous time to current timestamp
            prev_time = curr_time
        else:  # 'end' log
            # Pop the current function from the stack
            completed_fn = stack.pop()
            # Add the elapsed time including the current time unit
            result[completed_fn] += curr_time - prev_time + 1
            # Update previous time to one unit after the current timestamp
            prev_time = curr_time + 1
            
    return result

# Example usage:
n = 2
logs = ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]
print(exclusiveTime(n, logs))  # Output: [3, 4]
← Back to All Questions