OA: Stack trace reconstruction

A tracer records every function entry and exit. Implement

stack_segments(events: list[tuple[int, str, str]]) -> list[tuple[int, int, tuple[str, ...]]]

Each event is (ts, kind, name) with kind either "enter" or "exit". Events are sorted by ts (several may share a timestamp). An exit closes the most recent still-open enter, and its name must match; raise ValueError if it doesn't, or if there is nothing open.

Return the timeline of the active call stack as (start, end, stack) segments, where stack is a tuple from outermost to innermost frame and the stack is exactly that on [start, end):

• A segment runs from one event's timestamp to the next event's timestamp.
• Leave out segments of zero length and segments where the stack is empty.
• Merge a segment into the previous one when they touch (prev.end == start) and hold the same stack.
• Frames still open after the last event produce nothing further (there is no end time).

stack_segments([
    (0, "enter", "main"),
    (2, "enter", "load"),
    (5, "exit", "load"),
    (5, "enter", "load"),   # re-entered at the same instant
    (7, "exit", "load"),
    (9, "exit", "main"),
])
# [(0, 2, ('main',)), (2, 7, ('main', 'load')), (7, 9, ('main',))]

Up to 150,000 events; aim for O(n · depth) overall.

Ask yourself what the interviewer would want confirmed up front: is the log well formed, can recursion put the same name on the stack twice (yes), what happens to unmatched frames.