Exclusive Time of Functions

Exclusive Time of Functions

What is this problem about?

The Exclusive Time of Functions interview question asks you to calculate the total execution time for each function in a single-threaded CPU. You are given a list of logs, where each log contains a function ID, an action ("start" or "end"), and a timestamp. "Exclusive time" means the time spent only in that function, excluding time spent in any other functions it calls.

Why is this asked in interviews?

Companies like Uber, Microsoft, and Meta use this Stack interview pattern to see if you can model process execution. It mimics how profilers and operating systems track CPU usage. It tests your ability to handle nested events and manage "paused" state using a stack. It also checks for precision in calculating time intervals (handling the inclusive nature of timestamps).

Algorithmic pattern used

This problem is a classic application of a Stack.

1. Use a stack to keep track of the currently running function IDs.
2. Maintain a prev_time variable.
3. For each log entry:
   • If it's a "start":
     • If the stack is not empty, add the time elapsed since prev_time to the function at the top of the stack.
     • Push the new function ID onto the stack.
     • Update prev_time.
   • If it's an "end":
     • Pop the top function ID.
     • Add the time elapsed since prev_time (inclusive) to that function's total.
     • Update prev_time to the next second.

Example explanation

Logs: ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]

1. 0:start:0: Push 0. prev = 0.
2. 1:start:2: Stack has 0. 0 ran for 2-0 = 2 seconds. Push 1. prev = 2.
3. 1:end:5: Pop 1. 1 ran for 5-2 + 1 = 4 seconds. prev = 6.
4. 0:end:6: Pop 0. 0 ran for 6-6 + 1 = 1 more second. Total: 0: 3s, 1: 4s.

Common mistakes candidates make

• Interval calculation: Forgetting that start/end timestamps are usually inclusive, so end:5 after start:2 is 4 seconds (2, 3, 4, 5), not 3.
• Nested updates: Not updating the "parent" function's time when a "child" function starts.
• Timestamp inconsistencies: Mixing up when to add 1 to the time difference.

Interview preparation tip

Draw a timeline on a piece of paper. Visualize how the "active" function changes and how the clock ticks. This makes it much easier to decide exactly when to update the prev_time pointer.