Coding - Exclusive Time of Functions

Here is the full interview question "Coding - Exclusive Time of Functions" asked at Uber:

Uber Interview Question: Exclusive Time of Functions

You are given a list of logs generated by a program. Each log contains a unique function name and a time stamp in the format function_name:start_time or function_name:end_time. Your task is to calculate the exclusive time of each function, which is the total time spent in the function excluding the time spent in its nested functions.

Problem Statement:

Given a list of logs generated by a program, each log contains a unique function name and a time stamp in the format function_name:start_time or function_name:end_time. Your task is to calculate the exclusive time of each function, which is the total time spent in the function excluding the time spent in its nested functions.

Examples:

Example 1:

Input: n = 2, logs = ["0:start:0","1:start:2","0:end:5","1:end:6"] Output: [3, 4]

Explanation:

• Function 0 starts at time 0, ends at time 5, so it spends 5 - 0 = 5 units of time.
• Function 1 starts at time 2, ends at time 6, so it spends 6 - 2 = 4 units of time.

Example 2:

Input: n = 2, logs = ["0:start:0","1:start:1","0:end:5","1:end:6"] Output: [8, 1]

Explanation:

• Function 0 starts at time 0, ends at time 5, so it spends 5 - 0 = 5 units of time.
• Function 1 starts at time 1, ends at time 6, so it spends 6 - 1 = 5 units of time.
• However, function 1 is nested inside function 0, so we need to subtract the time spent in function 1 from the time spent in function 0.
• Therefore, the exclusive time of function 0 is 5 - 5 = 0 units of time, and the exclusive time of function 1 is 5 units of time.

Constraints:

• 1 <= n <= 100
• 1 <= logs.length <= 500
• Each log follows the format function_name:start_time or function_name:end_time.
• The function name consists of lowercase English letters and digits.
• The start time and end time are integers between 0 and 10000.

Hints:

1. Use a stack to keep track of the current function and its start time.
2. Iterate through the logs and update the exclusive time of each function accordingly.

Solution:

To solve this problem, you can use a stack to keep track of the current function and its start time. Iterate through the logs and update the exclusive time of each function accordingly. Here's a Python solution:

python class Solution: def exclusiveTime(self, n: int, logs: List[str]) -> List[int]: stack = [] time = 0 result = [0] * n for log in logs: id, type_, time = log.split(":") id, time = int(id), int(time) if type_ == "start": if stack: result[stack[-1]] += time - prev_time prev_time = time stack.append(id) else: result[stack.pop()] += time - prev_time + 1 prev_time = time + 1 return result

This solution uses a stack to keep track of the current function and its start time. It iterates through the logs and updates the exclusive time of each function accordingly. The time complexity is O(n), where n is the number of logs.