Compute exclusive execution time from logs

Q: Compute exclusive execution time from logs

This is a Coding & Algorithms interview question from Uber for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Problem

You are given execution logs from a single-threaded CPU that runs n functions labeled 0..n-1. The CPU can run only one function at a time. A function may call another function; when that happens, the caller is paused until the callee returns.

Each log entry is a string in the format:

"<function_id>:<event>:<timestamp>"

<event> is either "start" or "end" .
timestamp is a non-negative integer.
Logs are provided in chronological order.
An end event at time t means the function finishes at the end of time unit t (i.e., inclusive end).

Task

Return an array exclusiveTime of length n where exclusiveTime[i] is the exclusive CPU time spent executing function i (time spent in i itself, excluding time spent in functions called by i).

Input

Integer n (number of functions)
Array of strings logs

Output

Integer array exclusiveTime of length n

Example

Input:

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

Output:

[3, 4]

Explanation (one valid interpretation):

Function 0 runs from time 0 to 1 (2 units), then is paused.
Function 1 runs from time 2 to 5 (4 units).
Function 0 resumes at time 6 (1 unit).
Exclusive times: function 0 → 3, function 1 → 4.

Constraints (assume typical interview constraints)

1 <= n <= 10^5
1 <= logs.length <= 2 * 10^5
Logs are valid and properly nested (well-formed call stack).