Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Day 26 : Execution Time

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
21 upvotes
Asked in companies
DirectiUberFacebook

Problem statement

This time we are executing a program containing ‘N’ functions on a single-threaded CPU. Each function has a unique ‘ID’ between 0 and (N-1) and each time it starts or ends, we write a log with the ID, whether it started or ended, and the TIMESTAMP.

You are given a 2D array of integers containing information about ‘L’ logs where ith column represents the ith log message. Each column contains 3 rows to describe the ith log where,

1st Row - represents the ID of the function.

2nd Row - represents whether the function has started or ended where 1 denotes the start and -1 denotes the end.

3rd Row - represents the TIMESTAMP of the log.

You are required to return an array where the value at the ith index represents the exclusive time for the function with ID ‘i’.

Note:

1. The exclusive time of a function is the sum of execution times for all calls of that function.

2. A function can be called multiple times, possibly recursively.

3. No two events will happen at the same time where an event denotes either a start or end of a function call. This basically means no two logs have the same timestamp. 

4. Each function has an end log for each start log. 

For Example:

Consider the following input
0 1 1 1 2 2 1 0
1 1 1 -1 1 -1 -1 -1
0 2 5 7 8 10 11 14

alt-text

Thus, we return [5, 7, 3] as a process with ID 0 has taken 5 units of time and process with ID 1 has taken 7 units of time and process ID 2 has taken 3 units of time. A process’s exclusive time is the sum of exclusive times for all function calls in the program. As process Id 1 has called itself so exclusive time is the sum of exclusive times(5 + 2).
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
1 <= T <= 10
1 <= N <= 10 ^ 2
2 <= L <= 5 * (10 ^ 2) and L is even.
0 <= TIMESTAMP <= 10 ^ 9

Time Limit: 1 sec.
Sample Input 1:
1
2 4
0 1 1 0
1 1 -1 -1
0 2 5 6
Sample Output 1:
3 4
Explanation for Input 1:
Function 0 starts at the beginning of timestamp 0, then it executes for 2 units of time and reaches the end of timestamp 1. 

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

Function 0 resumes execution at the beginning of timestamp 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.
Sample Input 2:
1
1 6
0 0 0 0 0 0
1 1 -1 1 -1 -1
0 2 5 6 6 7
Sample Output 2:
8
Full screen
Console