Skip to content

Latest commit

 

History

History
171 lines (151 loc) · 7.26 KB

_636. Exclusive Time of Functions.md

File metadata and controls

171 lines (151 loc) · 7.26 KB

636. Exclusive Time of Functions

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

First completed : August 28, 2024

Last updated : August 28, 2024

Related Topics : Array, Stack

Acceptance Rate : 62.56 %

Test case error

Reference link: LeetCode-Feedback/LeetCode-Feedback#22693 (comment)

Found that one of the test cases was invalid and submitted it when I originally solved this question since it was preventing my code from working. This was verified by LeetCode in their feedback and now passes, so I've uploaded the code I originally had as the removal allows it to pass now.

Work shown:

Bug Description

Test case 121/123

n=3

logs = ["1:start:0","0:start:2","1:start:3","2:start:4","2:end:4","0:end:6","1:end:7","1:end:8"])

has an expected output [2, 6, 1] which I believe to be invalid. Going through it by hand I believe it should be [1, 7, 1]

If I am mistaken then I do apologize for the confusion / inconvenience.

Two possible reasons:

  1. 0:end:6 is invalid based on the question description since it's not the current active process
  2. Assuming that we can cancel/end non-actives, the summed exclusive runtime of Process-0 at the time of cancellation is 1, meaning it cannot have an expected answer of 2. See below for the step-by-step.

["1:start:0","0:start:2","1:start:3","2:start:4","2:end:4","0:end:6","1:end:7","1:end:8"]

With this, we can construct a table of [0-8] to fill.

Time 0 1 2 3 4 5 6 7 8
Process 0
Process 1
Process 2

1:start:0 process 1 starts at t=0

Time 0 1 2 3 4 5 6 7 8
Process 0
Process 1 x
Process 2

0:start:2 Process 0 starts at time 2 Note that the start of a process is stated to be at the beginning of whatever t is set

Time 0 1 2 3 4 5 6 7 8
Process 0 x
Process 1 x x
Process 2

1:start:3 Process 1v2 (recursive process) starts at t=3

Time 0 1 2 3 4 5 6 7 8
Process 0 x
Process 1 x x
Process 1v2 x
Process 2

2:start:4 Process 2 starts at time 4, pausing process 1v2

Time 0 1 2 3 4 5 6 7 8
Process 0 x
Process 1 x x
Process 1v2 x
Process 2 x

2:end:4 Process 2 immediately ends. Note, START starts at the beginning of the time and END ends at the end of the time slot, so process 2 gets +1 on it's output. As a result, Process 1v2 continues

0:end:6 occurs and halts that process but since it's not active, it has no effect.

Time 0 1 2 3 4 5 6 7 8
Process 0 x
Process 1 x x
Process 1v2 x x x x
Process 2 x

1:end:7 Process ends at the end of 7, swapping back to process 1 (process 0 has already ended)

Time 0 1 2 3 4 5 6 7 8
Process 0 x
Process 1 x x x
Process 1v2 x x x x
Process 2 x

1:end:8 process ends at time 8 (at the end of it, adding 1 to the output)

Summing the values we get: Process 0: 1 Process 1: 7 (3 from p1 and 4 from p1v2) Process 2: 1

Solutions

Python

m636.py

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        stk = [] # schema: (functionNo, start=True/False, time)
        output = [0] * n

        # "{function_id}:{"start" | "end"}:{timestamp}"
        # e.g. "0:start:3"
        
        for log in logs :
            log = log.split(':')
            functionId = int(log[0])
            start = (log[1] == 'start')
            time = int(log[2])

            if start :
                while stk and not stk[-1] :
                    stk.pop()

                if stk :
                    output[stk[-1][0]] += time - stk[-1][2]
                stk.append([functionId, start, time])
            else : # end
                previous = stk.pop()

                while stk and stk[-1] == 0 :
                    stk.pop()

                if previous[0] == functionId : # if previous is the start of the current process
                    output[functionId] += time - previous[2] + 1
                    if stk :
                        stk[-1][2] = time + 1 # end means ending at the end of time ___
                else : # the log before isn't for the ending process
                    stk.append(previous)
                    for i in range(len(stk) - 1, -1, -1) :
                        if stk[i][0] == functionId :
                            stk[i] = 0
                            break

        return output