How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Decagon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Decagon during technical interviews.

Compute exclusive CPU time from nested logs

Q: Compute exclusive CPU time from nested logs

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.

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.

Input: (2, ["0:start:0", "0:end:2", "1:start:3", "1:end:4"])

Expected Output: [3, 2]

Explanation: Function 0 runs from 0 through 2 for 3 units. Function 1 runs from 3 through 4 for 2 units.

Input: (1, ["0:start:0", "0:start:2", "0:end:3", "0:end:4"])

Expected Output: [5]

Explanation: Function 0 calls itself. Across both invocations, function 0 is executing during every timestamp from 0 through 4, for 5 total units.

Input: (3, ["0:start:0", "1:start:1", "1:end:2", "2:start:3", "2:end:3", "0:end:4"])

Expected Output: [2, 2, 1]

Explanation: Function 0 runs at timestamps 0 and 4. Function 1 runs at timestamps 1 and 2. Function 2 runs only at timestamp 3.

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.

Quick Overview

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.