LeetCode 636: Exclusive Time of Functions

From pairs of consecutive logs we find exclusive time piecemeal and attribute to the correct function.

Exclusive cpu time

A log represents two timestamps: (1) end timestamp of the previous function and (2) start timestamp of the next function. If log timestamp is $\texttt{logtime}$ , then:

“start” log:
- end timestamp of previous function = $\texttt{logtime} - 1$
- start timestamp of the next function = $\texttt{logtime}$ .
“end” log:
- end timestamp of previous function = $\texttt{logtime}$
- start timestamp of the next function = $\texttt{logtime} + 1$ .

From a pair of consecutive logs: $( \texttt{id}_{i}, \texttt{prev-end}_{i}, \texttt{next-start}_{i} )$ and $( \texttt{id}_{i+1}, \texttt{prev-end}_{i+1}, \texttt{next-start}_{i+1} )$ , we find the exclusive cpu time as $\texttt{prev-end}_{i+1} - \texttt{next-start}_{i} + 1$ .

Attribution

A function call-stack is two-dimensional: it has height (who is active) and width (time). When the call-stack comes back to its previous height, an earlier function resumes and we do not have a log for resume. As a result, just by looking at two consecutive (start/end) logs, we could not tell which function the in-between cpu time should belong to. An example below:

So, we simulate the function calls with a stack and attribute exclusive time to the function at the top of the stack.

Time: $\mathcal{O}(n)$ , space: same.

class Solution:
    def parse_log(self, log) -> Tuple[int, bool, int]:
        parts = log.split(":")
        func_id = int(parts[0])
        is_end = parts[1] == "end"
         
        log_timestamp = int(parts[2])
        prev_end_time = log_timestamp if is_end else log_timestamp-1
        start_time = log_timestamp + 1 if is_end else log_timestamp
         
        return func_id, is_end, prev_end_time, start_time
 
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        exclusive_times = [0] * n
        prev_start_time = 0
        call_stack = []
        for log in logs:
            func_id, is_end, prev_end_time, start_time = self.parse_log( log )
            cpu_time = prev_end_time - prev_start_time + 1
            prev_start_time = start_time
 
            prev_func_id = call_stack[-1] if call_stack else func_id
            exclusive_times[ prev_func_id ] += cpu_time
             
            if is_end:
                call_stack.pop()
            else:
                call_stack.append(func_id)
 
        return exclusive_times

unreasonably effective