Exclusive Time of Functions

medium stack

Problem

Process 'fid:start|end:ts' events. Return total exclusive time per function id.

Inputn=2 logs=['0:start:0','1:start:2','1:end:5','0:end:6']

Output[3, 4]

Function 0 ran for ts 0..2 and 6 = 3; function 1 ran ts 2..5 = 4.

input

def exclusive_time(n, logs):
    out = [0] * n; stk = []; prev = 0
    for log in logs:
        fid, typ, ts = log.split(':'); fid, ts = int(fid), int(ts)
        if typ == 'start':
            if stk: out[stk[-1]] += ts - prev
            stk.append(fid); prev = ts
        else:
            out[stk.pop()] += ts - prev + 1; prev = ts + 1
    return out

function exclusiveTime(n, logs) {
  const out = new Array(n).fill(0); const stk = []; let prev = 0;
  for (const log of logs) {
    const [f, typ, t] = log.split(':'); const fid = +f, ts = +t;
    if (typ === 'start') {
      if (stk.length) out[stk[stk.length-1]] += ts - prev;
      stk.push(fid); prev = ts;
    } else {
      out[stk.pop()] += ts - prev + 1; prev = ts + 1;
    }
  }
  return out;
}

int[] exclusiveTime(int n, List logs) {
    int[] out = new int[n]; Deque stk = new ArrayDeque<>(); int prev = 0;
    for (String log : logs) {
        String[] p = log.split(":"); int fid = Integer.parseInt(p[0]), ts = Integer.parseInt(p[2]);
        if (p[1].equals("start")) {
            if (!stk.isEmpty()) out[stk.peek()] += ts - prev;
            stk.push(fid); prev = ts;
        } else {
            out[stk.pop()] += ts - prev + 1; prev = ts + 1;
        }
    }
    return out;
}

vector exclusiveTime(int n, vector& logs) {
    vector out(n, 0); stack stk; int prev = 0;
    for (auto& log : logs) {
        size_t a = log.find(':'), b = log.rfind(':');
        int fid = stoi(log.substr(0, a)); int ts = stoi(log.substr(b + 1));
        string typ = log.substr(a + 1, b - a - 1);
        if (typ == "start") {
            if (!stk.empty()) out[stk.top()] += ts - prev;
            stk.push(fid); prev = ts;
        } else {
            out[stk.top()] += ts - prev + 1; stk.pop(); prev = ts + 1;
        }
    }
    return out;
}

Explanation

Function calls nest like a call stack, so a stack of the currently-running function ids mirrors exactly what the CPU does. The trick is to credit elapsed time to whichever function is on top right now.

We keep a stack stk of running ids and a variable prev = the timestamp where the current top last started accumulating. On a start at time ts, if something is already running we give it the time it spent so far (ts - prev), then push the new id and set prev = ts.

On an end at time ts, that function ran through the whole tick, so we add ts - prev + 1 to it (the +1 because end timestamps are inclusive), pop it, and set prev = ts + 1 so its parent resumes counting from the next tick.

Example: logs ['0:start:0','1:start:2','1:end:5','0:end:6']. Function 0 gets 2 (ts 0..2) plus 1 (the final tick 6) = 3; function 1 gets 5-2+1 = 4. Answer: [3, 4].

Each log line is handled once, so this is a single linear pass over the events.

Time: O(n) Space: O(n)