algoadvance

Leetcode 636. Exclusive Time of Functions

Problem Statement

The problem is taken from LeetCode’s Problem 636 - Exclusive Time of Functions. Here is the complete problem description:

You have a single-threaded CPU and are given a list of functions that are executed by the CPU. Each function has a unique ID between 0 and n-1.

You are also given a list logs, where logs[i] represents a string with three pieces of information: the function id, whether it is a start or end event for that function, and the timestamp when the event happens.

Each line in the logs list follows this format: “function_id:start_or_end:timestamp”. For example, “0:start:10” means function 0 started at time 10, and “1:end:15” means function 1 ended at time 15.

The CPU can execute only one function at a time, and it will always finish executing the current function before starting a new one. Functions can be recursive, meaning a function might call another function (or itself) during its execution.

You need to return a list of integers representing the exclusive time of each function. The exclusive time of a function is the total time spent executing that function, excluding the time spent executing other functions called within it.

Clarifying Questions

Before jumping to the solution, let’s clarify a few things about the problem:

  1. How is time represented in the logs? Is it guaranteed to be in a sorted order?
  2. What are the constraints on the number of functions n and the length of the logs list?
  3. Can there be more than one function starting at the same timestamp, or is it strictly sequential?

Assumptions:

Strategy

To solve this problem, we can use a stack to keep track of the functions being executed. Here’s a step-by-step approach:

  1. Initialize a stack to keep track of function IDs.
  2. Initialize an array result to keep track of the exclusive time for each function ID.
  3. Keep a variable prev_time to track the time of the last processed log.
  4. Iterate through each log entry. Depending on whether it’s a start or end event:
    • If it’s a start event, calculate the time spent on the previous function (if any), update the result for the function at the stack’s top, then push the current function onto the stack.
    • If it’s an end event, calculate the time spent on the current function, pop it from the stack, then update prev_time.

Boundary conditions and updates will be carefully managed to avoid off-by-one errors in time calculations.

Code

import java.util.List;
import java.util.Stack;

public class Solution {
    public int[] exclusiveTime(int n, List<String> logs) {
        // Result array to store exclusive times
        int[] result = new int[n];
        
        // Stack to keep track of function calls
        Stack<Integer> stack = new Stack<>();
        // Variable to keep track of previous timestamp
        int prevTime = 0;
        
        for(String log : logs) {
            String[] parts = log.split(":");
            int funcId = Integer.parseInt(parts[0]);
            String action = parts[1];
            int currTime = Integer.parseInt(parts[2]);
            
            if(action.equals("start")) {
                if(!stack.isEmpty()) {
                    // Update the top function's exclusive time using the diff between
                    // current time and previous time
                    result[stack.peek()] += currTime - prevTime;
                }
                // Push the current function onto the stack
                stack.push(funcId);
                // Update previous time to current time
                prevTime = currTime;
            } else { // action.equals("end")
                // Update the current function's exclusive time
                result[stack.peek()] += currTime - prevTime + 1;
                // Pop the function from stack as its execution has ended
                stack.pop();
                // Update previous time to current time + 1 because "end" log includes current timestamp
                prevTime = currTime + 1;
            }
        }
        
        return result;
    }
}

Time Complexity

Feel free to ask if you have any more questions or need further clarifications!

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