Solution: Exclusive Time of Functions

Explore how to calculate the exclusive execution time of functions running on a single-threaded CPU by leveraging stacks. Understand the algorithm that matches start and end events, manages nested function calls, and efficiently calculates execution time with O(m) time complexity. This lesson helps you master stack usage for solving such interview coding problems.

We'll cover the following...

Statement
- Solution
  - Time complexity
  - Space complexity

Statement

We are given an integer number, n, representing the number of functions running in a single-threaded CPU, and an execution log, which is essentially a list of strings. Each string has the format {function id}:{"start" | "end"}:{timestamp}, indicating that the function with function id either started or stopped execution at the time identified by the timestamp value. Each function has a unique ID between $0$ and $n-1$ . Compute the exclusive time of the functions in the program.

Note: The exclusive time is the sum of the execution times for all the calls to a specific function.

Constraints:

$1 \leq$ n $\leq 100$

...