algoadvance

Leetcode 636. Exclusive Time of Functions

Problem Statement

  1. Exclusive Time of Functions

On a single-threaded CPU, we have a set of n functions that are to be executed. Each function has a unique ID between 0 and n-1.

Function calls are stored in a log stack in the order they were called. The log array is given in the following format:

Each function has two entries, one with start and one with end. When a function starts or ends, it does not overlap with any other function.

The exclusive time of a function is the time spent running that function, excluding the time spent running other functions called within.

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

Clarifying Questions

  1. Can the start and end log entries be in any particular order?
    • No. The entries come in chronological order.
  2. How are nested function calls handled?
    • When a function is called within another, the time spent on the nested function is not counted towards the parent function’s execution time.
  3. What does a log entry look like?
    • Each entry is a string in the format "function_id:start_or_end:timestamp".

Code

#include <vector>
#include <string>
#include <stack>
#include <sstream>
#include <iostream>

using namespace std;

vector<int> exclusiveTime(int n, vector<string>& logs) {
    vector<int> result(n, 0);
    stack<int> callStack;
    int prevTime = 0;
    
    for (const string& log : logs) {
        istringstream iss(log);
        string idStr, type, timeStr;
        getline(iss, idStr, ':');
        getline(iss, type, ':');
        getline(iss, timeStr, ':');
        
        int id = stoi(idStr);
        int time = stoi(timeStr);
        
        if (type == "start") {
            if (!callStack.empty()) {
                result[callStack.top()] += time - prevTime;
            }
            callStack.push(id);
            prevTime = time;
        } else {
            result[callStack.top()] += time - prevTime + 1;
            callStack.pop();
            prevTime = time + 1;
        }
    }
    
    return result;
}

// Helper function to print vector of integers
void printVector(const vector<int>& v) {
    for (int num : v) {
        cout << num << " ";
    }
    cout << endl;
}
 
int main() {
    vector<string> logs = {
        "0:start:0",
        "1:start:2",
        "1:end:5",
        "0:end:6"
    };
    int n = 2;
    vector<int> result = exclusiveTime(n, logs);
    
    printVector(result); // Output: [3, 4]
    return 0;
}

Strategy

  1. Initialization:
    • Create a result vector initialized to 0 to store exclusive times.
    • Initialize a stack to keep track of function calls.
    • Track prevTime to manage the previous timestamp.
  2. Process Each Log Entry:
    • Parse the current log entry to get id, type, and timestamp.
    • If it’s a "start" type:
      • Update the exclusive time for the function at the top of the stack.
      • Push the new function id onto the stack.
      • Update prevTime.
    • If it’s an "end" type:
      • Calculate and update the exclusive time for the current function.
      • Pop the function from the stack.
      • Update prevTime.
  3. Return the Result:
    • Return the result vector containing exclusive times for each function.

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI