Exclusive Time of Functions

Medium
1400.

Exclusive Time of Functions

Exclusive Time of Functions is a medium coding problem on arrays and stack, asked in Amazon, Meta, Uber and LinkedIn interviews.

A single-threaded CPU runs a program made of n functions with ids 0 to n - 1. Calls may nest (a function may call another, or itself), and the CPU always runs the most recently started call that has not finished yet.

Every call is recorded by two entries in logs, given in chronological order, each written "{id}:start:{t}" or "{id}:end:{t}". A start at t means the call begins at the beginning of time unit t; an end at t means it finishes at the end of time unit t. So "0:start:3" followed by "0:end:4" is a call that ran for 2 units.

The exclusive time of a function is the total number of units the CPU spent running its own calls — time spent inside the calls it makes does not count. Return an array whose i-th value is the exclusive time of function i.

Example 1

Input
n = 2, logs = ["0:start:0","1:start:3","1:end:4","0:end:7"]
Output
[6,2]
Explanation
Function 0 runs units 0–2 and 5–7 (6 units); function 1 runs units 3–4.

Example 2

Input
n = 1, logs = ["0:start:0","0:start:2","0:end:5","0:end:6"]
Output
[7]
Explanation
The recursive call covers units 2–5 and the outer call units 0–1 and 6; both count for function 0.

Example 3

Input
n = 3, logs = ["0:start:0","0:end:1","2:start:2","2:end:2","1:start:4","1:end:4"]
Output
[2,1,1]
Explanation
The CPU is idle during unit 3.

Constraints

  • 1 <= n <= 100
  • 2 <= logs.length <= 500
  • 0 <= id < n
  • 0 <= t <= 10^9
  • No two start entries share a timestamp, and no two end entries share a timestamp.
  • Every start has a matching end, and the log is properly nested.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {string[]} logs
 * @return {number[]}
 */
var exclusiveTime = function(n, logs) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Exclusive Time of Functions — Solution in Python, Java & C++

Exclusive Time of Functions solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Exclusive Time of Functions is a medium coding problem on arrays and stack, asked in Amazon, Meta, Uber and LinkedIn interviews.

  • Difficulty: Medium
  • Topics: Arrays, Stack
  • Asked at: Amazon, Meta, Uber, LinkedIn
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A single-threaded CPU runs a program made of n functions with ids 0 to n - 1. Calls may nest (a function may call another, or itself), and the CPU always runs the most recently started call that has not finished yet.

Every call is recorded by two entries in logs, given in chronological order, each written "{id}:start:{t}" or "{id}:end:{t}". A start at t means the call begins at the beginning of time unit t; an end at t means it finishes at the end of time unit t. So "0:start:3" followed by "0:end:4" is a call that ran for 2 units.

The exclusive time of a function is the total number of units the CPU spent running its own calls — time spent inside the calls it makes does not count. Return an array whose i-th value is the exclusive time of function i.

Example 1

Input: n = 2, logs = ["0:start:0","1:start:3","1:end:4","0:end:7"]
Output: [6,2]
Explanation: Function 0 runs units 0–2 and 5–7 (6 units); function 1 runs units 3–4.

Example 2

Input: n = 1, logs = ["0:start:0","0:start:2","0:end:5","0:end:6"]
Output: [7]
Explanation: The recursive call covers units 2–5 and the outer call units 0–1 and 6; both count for function 0.

Example 3

Input: n = 3, logs = ["0:start:0","0:end:1","2:start:2","2:end:2","1:start:4","1:end:4"]
Output: [2,1,1]
Explanation: The CPU is idle during unit 3.

Constraints

  • 1 <= n <= 100
  • 2 <= logs.length <= 500
  • 0 <= id < n
  • 0 <= t <= 10^9
  • No two start entries share a timestamp, and no two end entries share a timestamp.
  • Every start has a matching end, and the log is properly nested.

Hints for Exclusive Time of Functions

  1. Hint 1

    The function running at any moment is the one on top of the call stack.

  2. Hint 2

    Keep a pointer prev to the first time unit not yet credited to anyone. Every log entry credits the stretch since prev to whoever was on top.

  3. Hint 3

    On a start at t, the old top earns t - prev and prev = t. On an end at t, the finishing call earns t - prev + 1 and prev = t + 1.

How to solve Exclusive Time of Functions

Replay the log with a stack of active calls. Between two consecutive entries exactly one function — the top of the stack — owns the CPU, so each entry closes a stretch of time and credits it to that function.

Approach

  1. Create res of size n, an empty stack, and prev = 0, the first unit not yet credited.
  2. Parse each entry into id, kind and t.
  3. Start: if the stack is not empty, add t - prev to the top function; push id; set prev = t.
  4. End: pop the top (it is id), add t - prev + 1 to it, and set prev = t + 1 because unit t is fully used.
  5. Return res.

Why it works

The stack mirrors the real call stack, so its top is always the running function. Every time unit between the first start and the last end belongs to the segment between two consecutive entries, and each segment is credited exactly once — to the call that was running through it. Idle gaps between top-level calls happen while the stack is empty and are credited to nobody.

Complexity

  • Time — O(L) for L log entries (each is parsed once)
  • Space — O(L) for the stack

Pitfalls

  • Starts and ends use different boundaries: a start begins at t, an end finishes after t — hence the + 1 on ends and prev = t + 1.
  • Recursion means the same id can be on the stack several times; credit the top entry, not a per-id timer.
  • Parse the timestamp as a number — comparing strings would order 10 before 9.

Reference solution

Python

from typing import List

def exclusiveTime(n: int, logs: List[str]) -> List[int]:
    res = [0] * n
    stack = []
    prev = 0
    for entry in logs:
        fid, kind, ts = entry.split(':')
        t = int(ts)
        if kind == 'start':
            if stack:
                res[stack[-1]] += t - prev
            stack.append(int(fid))
            prev = t
        else:
            res[stack.pop()] += t - prev + 1
            prev = t + 1
    return res

Java

public static int[] exclusiveTime(int n, String[] logs) {
    int[] res = new int[n];
    int[] stack = new int[logs.length];
    int top = 0, prev = 0;
    for (String entry : logs) {
        String[] parts = entry.split(":");
        int id = Integer.parseInt(parts[0]);
        int t = Integer.parseInt(parts[2]);
        if (parts[1].equals("start")) {
            if (top > 0) res[stack[top - 1]] += t - prev;
            stack[top++] = id;
            prev = t;
        } else {
            res[stack[--top]] += t - prev + 1;
            prev = t + 1;
        }
    }
    return res;
}

C++

vector<int> exclusiveTime(int n, vector<string>& logs) {
    vector<int> res(n, 0);
    vector<int> st;
    int prev = 0;
    for (const string& entry : logs) {
        size_t a = entry.find(':');
        size_t b = entry.find(':', a + 1);
        int id = stoi(entry.substr(0, a));
        string kind = entry.substr(a + 1, b - a - 1);
        int t = stoi(entry.substr(b + 1));
        if (kind == "start") {
            if (!st.empty()) res[st.back()] += t - prev;
            st.push_back(id);
            prev = t;
        } else {
            res[st.back()] += t - prev + 1;
            st.pop_back();
            prev = t + 1;
        }
    }
    return res;
}

JavaScript

var exclusiveTime = function(n, logs) {
    var res = new Array(n).fill(0);
    var stack = [];
    var prev = 0;
    for (var i = 0; i < logs.length; i++) {
        var parts = logs[i].split(":");
        var id = parseInt(parts[0], 10);
        var t = parseInt(parts[2], 10);
        if (parts[1] === "start") {
            if (stack.length > 0) res[stack[stack.length - 1]] += t - prev;
            stack.push(id);
            prev = t;
        } else {
            res[stack.pop()] += t - prev + 1;
            prev = t + 1;
        }
    }
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Stack Data Structure