636. Exclusive Time Of Functions – SOFTWARE ENGINEERING

/**

* 636. Exclusive Time of Functions

* 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: n = 2, logs = [“0:start:0″,”1:start:2″,”1:end:5″,”0:end:6”]

* Output: [3,4]

* Explanation:

* Function 0 starts at the beginning of time 0, then it executes 2 for units of time and reaches the end of time 1.

* Function 1 starts at the beginning of time 2, executes for 4 units of time, and ends at the end of time 5.

* Function 0 resumes execution at the beginning of time 6 and executes for 1 unit of time.

* So function 0 spends 2 + 1 = 3 units of total time executing, and function 1 spends 4 units of total time executing.

See the solution on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/face_book/medium/ExclusiveTimeOfFunctions.java

Observation: The problem puts work units on a call stack with a start time, overlayed with another start or an end time. Clearly, we can use a stack to identify previous items on call stack. There are a few edge cases though, an item on stack can be overlayed with another item, when that occurs, we need to store the time the original item was on cpu. A map would serve well to track amount of time a function had on cpu. We also need to track time a function was on cpu based off when the prior function ended or started, we can store the prior time in a variable. Lastly, we need to return the function times back in order in which they were seen, we can keep track of new functions in a linked list and return in same order.

Logic:

Create a map to store function times on cpu
Create a list to store order in which functions are seen
Create a stack to keep functions which are active on call stack
We start processing the logs:
1. If we see a new start
  1. we check the prior function which was on top of stack
  1. We use the current time – prior time to track the time function spent on cpu
  1. We update the above time in the map in 1
  1. If this function was seen for the first time, we add it to the list created above in 2 so that we can return the functions in correct order
  1. We update the prior time to the time in log
1. If we see an end time
  1. We take the end time and subtract from prior time (add 1 to identify end of slot) to get time on cpu
  1. We update the time on map created above in 1
  1. We pop the function of the call stack
  1. We update the prior time to 1 ahead of the end time
We return the times in an array based off the order the functions were seen (#2) and their times obtained from map (#1)

Here is the code:

public int[] exclusiveTime(int n, List<String> logs) {
    //use a map to count time for a function
    Map<Integer, Integer> idToTime = new HashMap<>();
    //use a list to indicate order in which functions are seen
    List<Integer> functionOrder = new ArrayList<>();
    //use a stack to track the current running functions
    Stack<Integer> workingFunctions = new Stack<>();
    int priorTime = 0;
    for (String info : logs) {
        String [] steps = info.split(":");
        int id = Integer.parseInt(steps[0]);
        int time = Integer.parseInt(steps[2]);
        String workType = steps[1];
        if (workType.equals("start")) {
            if (!workingFunctions.isEmpty()) {
                //add the time for prior function when a new one starts
                int priorIdTmp = workingFunctions.peek();
                int timeWorked = time - priorTime;
                timeWorked += idToTime.getOrDefault(priorIdTmp, 0);
                idToTime.put(priorIdTmp, timeWorked);
            }
            if (!idToTime.containsKey(id)) {
                //if its a new function, add its time as 0 in map
                functionOrder.add(id);
                idToTime.put(id, 0);
            }
            //add function on stack
            workingFunctions.push(id);
            priorTime = time;
        } else {
            //update the time in map when a function ends.
            //end is till end of the given time slot. hence add 1 to the diff of time - prior
            int timeOnCpu = time - priorTime + 1;
            timeOnCpu += idToTime.get(id);
            idToTime.put(id, timeOnCpu);
            workingFunctions.pop();
            priorTime = time;
            priorTime++; //move time ahead since end takes the current slot
        }
    }
    int [] retList = new int[functionOrder.size()];
    int i = 0;
    for (int id : functionOrder) {
        retList[i++] = idToTime.get(id);
    }
    return retList;
}