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 Uber.

What role is this question designed for?

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

Compute exclusive execution time from logs

Q: Compute exclusive execution time from logs

This question evaluates understanding of event log interpretation, nested call stack behavior, and exclusive time accounting for functions in a single-threaded execution model.

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.

Input: (1, ["0:start:0", "0:start:2", "0:end:5", "0:end:6"])

Expected Output: [7]

Explanation: The same function calls itself recursively. The outer call contributes 3 exclusive units and the inner call contributes 4, for a total of 7 for function 0.

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

Expected Output: [2, 1, 2]

Explanation: There is no nesting here. Each function's exclusive time is simply its full runtime.

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

Expected Output: [2, 1, 3]

Explanation: Function 0 runs at time 0 and again at time 5. Function 1 runs for 1 unit and function 2 runs from 2 to 4 for 3 units.

Solution

def solution(n, logs):
    exclusive = [0] * n
    stack = []
    prev_time = 0

    for log in logs:
        fn_id_str, event, ts_str = log.split(":")
        fn_id = int(fn_id_str)
        ts = int(ts_str)

        if event == "start":
            if stack:
                exclusive[stack[-1]] += ts - prev_time
            stack.append(fn_id)
            prev_time = ts
        else:
            exclusive[stack.pop()] += ts - prev_time + 1
            prev_time = ts + 1

    return exclusive

Time complexity: O(len(logs)). Space complexity: O(n + max_call_depth).

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.

Quick Overview

This question evaluates understanding of event log interpretation, nested call stack behavior, and exclusive time accounting for functions in a single-threaded execution model.