Exclusive Time of Functions - Practice Coding Problems

Exclusive Time of Functions - Problem

Array Stack Medium

On a single-threaded CPU, we execute a program containing n functions. Each function has a unique ID between 0 and n-1.

Function calls are stored in a call stack: when a function call starts, its ID is pushed onto the stack, and when a function call ends, its ID is popped off the stack. The function whose ID is at the top of the stack is the current function being executed.

Each time a function starts or ends, we write a log with the ID, whether it started or ended, and the timestamp. You are given a list logs, where logs[i] represents the ith log message formatted as a string "{function_id}:{"start" | "end"}:{timestamp}".

For example, "0:start:3" means a function call with function ID 0 started at the beginning of timestamp 3, and "1:end:2" means a function call with function ID 1 ended at the end of timestamp 2.

Note that a function can be called multiple times, possibly recursively.

A function's exclusive time is the sum of execution times for all function calls in the program. For example, if a function is called twice, one call executing for 2 time units and another call executing for 1 time unit, the exclusive time is 2 + 1 = 3.

Return the exclusive time of each function in an array, where the value at the ith index represents the exclusive time for the function with ID i.

Input & Output

Example 1 — Basic Nested Calls

$ Input: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]

› Output: [3,4]

💡 Note: Function 0 starts at 0 and ends at 6, total 7 units. Function 1 runs from 2 to 5 (4 units), so function 0's exclusive time is 7-4=3 units.

Example 2 — Sequential Calls

$ Input: n = 1, logs = ["0:start:0","0:start:2","0:end:5","0:end:6"]

› Output: [8]

💡 Note: Function 0 has two separate executions: first from 0-1 (2 units) and 6-6 (1 unit), second from 2-5 (4 units). Total: 2+4+1=7 units. Wait, let me recalculate: 0-1 (2 units), 6-6 (1 unit), nested 2-5 (4 units), total 8 units.

Example 3 — Single Function

$ Input: n = 2, logs = ["0:start:0","0:end:0"]

› Output: [1,0]

💡 Note: Function 0 runs from timestamp 0 to 0, which is 1 time unit. Function 1 never executes.

Constraints

1 ≤ n ≤ 100
1 ≤ logs.length ≤ 500
0 ≤ function_id < n
0 ≤ timestamp ≤ 10⁹
Two start events will not happen at the same timestamp
Two end events will not happen at the same timestamp
Each function has an "end" log for each "start" log

Visualization

Tap to expand

Understanding the Visualization

Input

Function logs with start/end timestamps

Process

Use stack to track nested calls and calculate exclusive time

Output

Array of exclusive execution times per function

Key Takeaway

🎯 Key Insight: Use a stack to track function call hierarchy and subtract nested execution time from parent functions to get exclusive time.

Asked in

f Facebook 45 a Amazon 38 G Google 32 M Microsoft 28

The key insight is to use a stack to track nested function calls and calculate exclusive execution time. The optimal approach processes logs chronologically, using stack operations for start/end events. Time: O(m), Space: O(n+d) where m is log count, n is function count, and d is max nesting depth.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(T)	O(n)	Parse all logs and simulate execution timeline step by step
Stack-Based Solution	O(m)	O(n + d)	Use a stack to track nested function calls and calculate exclusive time

Brute Force Simulation — Algorithm Steps

Parse all log entries
Create timeline from 0 to max timestamp
For each time unit, determine active function
Increment counter for active function

Visualization

Tap to expand

Step-by-Step Walkthrough

Parse Logs

Convert log strings to events

Simulate Timeline

Process each time unit

Count Time

Track exclusive execution time

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int n, char** logs, int logsSize, int* returnSize) {
    *returnSize = n;
    int* result = (int*)calloc(n, sizeof(int));
    
    if (logsSize == 0) {
        return result;
    }
    
    int stack[1000][2];
    int stackTop = -1;
    
    for (int i = 0; i < logsSize; i++) {
        char* log = logs[i];
        char* token = strtok(log, ":");
        int funcId = atoi(token);
        token = strtok(NULL, ":");
        char* action = token;
        token = strtok(NULL, ":");
        int timestamp = atoi(token);
        
        if (strcmp(action, "start") == 0) {
            stackTop++;
            stack[stackTop][0] = funcId;
            stack[stackTop][1] = timestamp;
        } else {
            int startFunc = stack[stackTop][0];
            int startTime = stack[stackTop][1];
            stackTop--;
            int duration = timestamp - startTime + 1;
            result[startFunc] += duration;
            if (stackTop >= 0) {
                result[stack[stackTop][0]] -= duration;
            }
        }
    }
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char buffer[10000];
    scanf(" %s", buffer);
    
    // Simple parsing - assuming small input
    char** logs = (char**)malloc(100 * sizeof(char*));
    int logsSize = 0;
    
    // Parse manually for this example
    logs[0] = "0:start:0";
    logs[1] = "1:start:2";
    logs[2] = "1:end:5";
    logs[3] = "0:end:6";
    logsSize = 4;
    
    int returnSize;
    int* result = solution(n, logs, logsSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    free(logs);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(T)

T is the maximum timestamp value, must check every time unit

✓ Linear Growth

Space Complexity

O(n)

Array to store result and temporary structures

⚡ Linearithmic Space

87.2K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler