Compute Exclusive Time from Stack Events

Given entry and exit events from one thread, compute the total exclusive running time of each function. The interview report preserves only the topic "Stack Trace" and notes that it had follow-ups; the event encoding and time semantics below are explicit practice assumptions, not a reconstruction of those missing follow-ups.

def exclusive_function_times(
 events: list[list[object]],
) -> list[list[object]]:
 ...

Each event is exactly [function_name, kind, timestamp]:

• function_name is a nonempty string;
• kind is exactly "start" or "end"; and
• timestamp is a nonnegative integer.

Events are listed in nondecreasing timestamp order. A start event pushes a function onto the active call stack. An end event must name the currently active top function and pops it. Recursion is allowed.

Treat time as continuous and intervals as half-open. If function A starts at time 2, calls B at time 5, B ends at time 8, and A ends at time 10, then B receives 8 - 5 = 3 units and A receives (5 - 2) + (10 - 8) = 5 units. Events sharing a timestamp consume no time between them and are applied in list order.

Return one [function_name, exclusive_time] record per distinct function name, sorted by function name lexicographically. An empty input returns [].

Example

Input:
events = [
 ["main", "start", 0],
 ["work", "start", 2],
 ["work", "end", 7],
 ["main", "end", 10]
]

Output: [["main", 5], ["work", 5]]

Constraints and Errors

• 0 <= len(events) <= 500_000
• 0 <= timestamp <= 10**18
• Timestamps must be nondecreasing.
• The trace must begin from an empty stack and end with an empty stack.
• An end event with an empty stack or a name different from the active function is invalid.
• A malformed event, invalid field type, empty name, invalid kind, Boolean timestamp, decreasing timestamp, or unbalanced trace raises ValueError.
• Do not mutate the input.

Hints

• Maintain the active function stack and the timestamp of the previous event.
• Before applying each event, charge elapsed time to the function currently at the top, if any.
• Aggregate by function name even when the same function is called recursively or from several callers.