algoadvance

The “Exclusive Time of Functions” problem from LeetCode is defined as follows:

On a single-threaded CPU, we execute a set of functions. Each function has a unique ID from 0 to n-1.

You are given a list of logs, where logs[i] is the string representation of an ID and whether the function call is a start or end event, and the timestamp. The format of a log is one of the following:

Logs are sorted by timestamp, and start/end events are given as strings in the format:

"{function_id}:start:{timestamp}" and "{function_id}:end:{timestamp}".

A function’s exclusive time is the total time spent in this function excluding the time spent in other functions that overlap in time. Return the exclusive time of each function in the form of an array.

Example:

Input:

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

Output:

[3, 4]

Explanation: Function 0 starts at time 0, then function 1 starts at time 2, and function 1 ends at time 5. Function 0 resumes at time 5 and ends at time 6. The exclusive time is:

Clarifying Questions

  1. Can we assume that the function IDs are sequential starting from 0 and are contiguous up to n-1?
  2. Is it guaranteed that the logs are given in chronological order?
  3. Can we assume that the start and end events are always properly paired?

Strategy

  1. Use a stack to keep track of the functions that are currently running.
  2. Initialize an array exclusive_times to store the exclusive times of each function.
  3. Traverse through the logs:
    • For a “start” log, push the function ID and timestamp onto the stack.
    • For an “end” log, pop the stack to get the function ID and its corresponding start time, and calculate the time spent.
    • Adjust exclusive_times accordingly using the calculated times.
  4. Ensure that any intermediate running function is paused when a new one starts and resumed when it ends.

Code

Here is the Python code to solve the problem:

def exclusiveTime(n, logs):
    exclusive_times = [0] * n
    stack = []

    for log in logs:
        func_id, typ, timestamp = log.split(":")
        func_id, timestamp = int(func_id), int(timestamp)
        
        if typ == "start":
            if stack:
                exclusive_times[stack[-1][0]] += timestamp - stack[-1][1]
            stack.append([func_id, timestamp])
        else:
            last_func_id, start_time = stack.pop()
            exclusive_times[last_func_id] += timestamp - start_time + 1
            if stack:
                stack[-1][1] = timestamp + 1
    
    return exclusive_times

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

Time Complexity

The time complexity of the solution is O(m), where m is the total number of logs provided. This is because we process each log exactly once.

The space complexity is also O(m) due to the stack used to keep track of the function calls. The array exclusive_times uses O(n) space where n is the number of functions.

Try our interview co-pilot at AlgoAdvance.com