Compute exclusive execution time from logs
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## 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).
Quick Answer: This question evaluates understanding of event log interpretation, nested call stack behavior, and exclusive time accounting for functions in a single-threaded execution model.
You are given execution logs from a single-threaded CPU that runs n functions labeled 0 to n-1. Each log is a string in the format "<function_id>:<event>:<timestamp>" where event is either "start" or "end". When a function calls another function, the caller is paused until the callee returns. An end event at time t means the function finishes at the end of time unit t, so the ending timestamp is inclusive. Return an array exclusiveTime where exclusiveTime[i] is the total time function i spent executing, excluding time spent inside functions it called.
Constraints
- 1 <= n <= 10^5
- 1 <= len(logs) <= 2 * 10^5
- Each log has the form "<function_id>:<event>:<timestamp>"
- 0 <= timestamp
- Logs are in chronological order and form a valid properly nested call stack
Examples
Input: (2, ["0:start:0", "1:start:2", "1:end:5", "0:end:6"])
Expected Output: [3, 4]
Explanation: Function 0 runs from 0 to 1, function 1 runs from 2 to 5, and function 0 resumes at 6. So the exclusive times are 3 and 4.
Input: (1, ["0:start:0", "0:end:0"])
Expected Output: [1]
Explanation: A single function starts and ends at the same timestamp, so it executes for exactly one time unit.
Hints
- Use a stack to track which function is currently running.
- Keep a previous timestamp pointer. When processing an end event at time t, remember that the function used the CPU through time t, so you should add one extra unit and move the pointer to t + 1.