Compute exclusive CPU time from nested logs
Company: Decagon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given logs from a single-threaded CPU that runs `n` functions (IDs `0` to `n-1`). Each log entry is a string in the format:
- `"functionId:start:timestamp"` or
- `"functionId:end:timestamp"`
Rules/semantics:
- The CPU runs at most one function at a time.
- A function can call other functions; calls are properly nested (well-formed like a stack).
- `start` means the function begins executing at the **start** of `timestamp`.
- `end` means the function finishes executing at the **end** of `timestamp` (inclusive).
- Timestamps are non-decreasing across the log list.
**Task:** Return an array `ans` of length `n` where `ans[i]` is the **exclusive** time spent executing function `i` (time spent in its own body excluding time spent in functions it calls).
**Input:**
- Integer `n`
- List of strings `logs`
**Output:**
- Integer array `ans`
**Example:**
- `n = 2`
- `logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]`
- Output: `[3,4]`
**Constraints (typical interview assumptions):**
- `1 <= n <= 10^5`
- `1 <= logs.length <= 10^5`
- Log format is valid and properly nested.
Quick Answer: This question evaluates the ability to interpret execution logs and compute exclusive CPU time, testing skills in parsing structured logs, reasoning about nested execution intervals, and precise time accounting.
You are given logs from a single-threaded CPU running n functions with IDs from 0 to n - 1. Each log entry has the format "functionId:start:timestamp" or "functionId:end:timestamp". A start log means the function begins executing at the start of that timestamp, and an end log means the function finishes executing at the end of that timestamp, so end timestamps are inclusive. Function calls are properly nested like a stack, and the CPU runs at most one function at a time. Return an array ans where ans[i] is the exclusive execution time of function i, excluding time spent inside functions it calls.
Constraints
- 1 <= n <= 10^5
- 1 <= logs.length <= 10^5
- 0 <= functionId < n
- 0 <= timestamp <= 10^9
- Timestamps are non-decreasing across logs
- Logs are valid and properly nested
Examples
Input: (2, ["0:start:0", "1:start:2", "1:end:5", "0:end:6"])
Expected Output: [3, 4]
Explanation: Function 0 runs at times 0, 1, and 6 for a total of 3. Function 1 runs at times 2 through 5 inclusive for a total of 4.
Input: (1, ["0:start:0", "0:end:0"])
Expected Output: [1]
Explanation: The function starts and ends at timestamp 0, which counts as 1 unit because end timestamps are inclusive.
Hints
- Because function calls are properly nested, consider using a stack to track which function is currently running.
- Keep track of the previous timestamp boundary. When a new function starts, the function on top of the stack has been running until just before that timestamp. When a function ends, remember that the end timestamp is inclusive.