Convert Stack Samples into Trace Events

Problem Statement

You are given a list of call stack samples collected at uniform time intervals. Each sample is a list of function names representing the call stack from the root (index 0) to the leaf (the currently executing function).

Your task is to convert these discrete samples into a sequential trace of events. An event is either a START or an END .

To minimize the trace, you must only record changes between consecutive samples S[i] and S[i+1].

1. Identify the longest common prefix (LCP) between S[i] and S[i+1].
2. Close functions that exist in S[i] but are not part of the LCP, in reverse order (leaf-to-root).
3. Open functions that exist in S[i+1] but are not part of the LCP, in order (root-to-leaf).

If the first sample is non-empty, open all functions in that stack from root to leaf. If the last sample is non-empty, close all functions remaining in the stack from leaf to root.

Function Signature

def generate_trace(samples: list[list[str]]) -> list[str]:
    # returns a list of strings: e.g., ["START main", "START f1", "END f1", ...]

Example

Input:

samples = [
    ["main", "f1"],
    ["main", "f2"]
]

Output:

["START main", "START f1", "END f1", "START f2", "END f2", "END main"]

Explanation:

• Start with ["main", "f1"]: Open main, then f1.
• Transition from ["main", "f1"] to ["main", "f2"]: The LCP is ["main"]. Close f1, then open f2.
• Final step: Close f2 then main.

Constraints

• 0 <= len(samples) <= 10^5
• 0 <= len(sample) <= 100
• Empty samples may exist between non-empty ones.