Exclusive Execution Time of Functions

Try to solve the Exclusive Execution Time of Functions problem.

We'll cover the following

Statement#

We are given an integer number, n, representing the number of functions running in a single-threaded CPU, and an execution log, which is essentially a list of strings. Each string has the format {function id}:{"start" | "end"}:{timestamp}, indicating that the function with function id either started or stopped execution at the time identified by the timestamp value. Each function has a unique ID between 00 and n−1n-1. Compute the exclusive time of the functions in the program.

Note: The exclusive time is the sum of the execution times for all the calls to a specific function.

Constraints:

  • 1≤1 \leq n ≤100\leq 100
  • 1≤1 \leq logs.length ≤500\leq 500
  • 0≤0 \leq function id << n
  • 0≤0 \leq timestamp ≤103\leq 10^3
  • No two start events and two end events will happen at the same timestamp.
  • Each function has an end log entry for each start log entry.

Examples#

Each function is identified in the logs by a function id. Each log entry is formatted in the following way:

{function id}:{"start" | "end"}:{timestamp}
"0:start:0"
"0:start:0"
"1:start:2"
"1:start:2"
"1:end:3"
"1:end:3"
"2:end:7"
"2:end:7"
"0:end:8"
"0:end:8"
"2:start:4"
"2:start:4"Viewer does not support full SVG 1.1

The above log entries indicate that three functions with IDs 0, 1, and 2 are executed as shown in the following figure. The function with ID 0 started execution at time 0 and ended at time 8. However, since this is a single-threaded CPU, only one function can run at a time. So, when the function with ID 1 starts execution at time 2, the function with ID 0 is preempted. As soon as the function with ID 1 stops execution at time 3, the function with ID 2 starts execution, so the function with ID 0 still remains preempted. Finally, the function with ID 2 ends execution at time 7 and the function with ID 0 resumes and finishes execution at time 8.

f-0 start
f-0 start
f-2 start
f-2 start
f-1 start
f-1 start
f-2 end
f-2 end
f-1 end
f-1 end
f-0 end
f-0 end
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8Viewer does not support full SVG 1.1

Our task is to return the total time for which each function ran. For example, the function with ID 0 ran for a total of 3 time units.

Here are some example inputs and the corresponding expected output:

Created with Fabric.js 3.6.6 logs 0:start:0 1:start:2 1:end:3 2:start:4 2:end:7 0:end:8 n = 3 Output 3 2 4 Sample example 1Input

1 of 2

Created with Fabric.js 3.6.6 7 1 Output Sample example 2InputThe second log represents a recursive call to function 0 logs 0:start:0 0:start:2 0:end:5 1:start:6 1:end:6 0:end:7 n = 2

2 of 2

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Exclusive Execution Time of Functions

2

Given the following logs and value of nn, what will be the output?

logs == [‘0:start:0’, ‘1:start:3’, ‘1:end:6’, ‘0:end:10’]

n == 2

Your Answer
A)

[4, 7]

Correct Answer
B)

[7, 4]

Explanation

The function with ID 0 starts at timestamp 0 and preempts at timestamp 3 as the second function starts.

The second function runs for 4 units of time and the function with ID 0 then resumes at timestamp 6 and ends at timestamp 10.

C)

[6, 3]

Question 2 of 22 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Retrieve function ID, start/end and timestamp from the log string.

If the string contains “start”, push the log details to the stack.

Else if, the string contains “end”, pop from the stack and compute the function’s execution time.

If the stack is not empty after the pop operation, subtract the execution time of the called function from the calling function.

Store the execution time in a results array and return.

Try it yourself#

Implement your solution in main.py in the following coding playground. You will need the provided supporting code to implement your solution. We have also provided some useful code templates that you may build on to solve this problem.

Python
main.py
logs.py
stack.py
Powered by AI
Input #1
Input #2
Exclusive Execution Time of Functions

Solution: Minimum Remove to Make Valid Parentheses

Solution: Exclusive Execution Time of Functions