题目重点：由带时间戳的完整调用栈样本重建进入和退出事件；解释最长公共前缀、同名递归、尾部未闭帧与连续 n 次出现的追问。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版每个样本的 stack 是从根到叶的完整帧名序列，时间戳严格递增；同名递归以深度和完整前缀区分。
- 相邻两次采样的最长公共前缀视为持续调用；样本之间的真实调用时刻不可知，用新样本时间戳给退出和进入打点，这是采样近似。
- 同一时间戳先按深到浅结束旧帧，再按浅到深开始新帧；末尾仍存在的帧不虚构 end。连续 n 次追问和只有最后 m 帧的追问因原始判定规则不全，只讨论设计和缺口，不塞进基础代码。
解题路线
- 维护上一个完整栈 prev。对当前栈 cur，线性求最长公共前缀长度 k；`prev[k:]` 的帧按深到浅发 end，`cur[k:]` 按浅到深发 start。然后将 cur 复制为 prev。
- 比较整条前缀而非只比较帧名集合：`[A,A]→[A]` 应只结束深度 1 的 A；`[A,B]→[A,C]` 应结束 B 再开始 C。
- 若要求帧连续出现至少 n 个样本才发事件，可为每个候选前缀保留首次出现位置和计数，到第 n 次才确认；是否把 start 回填到首次出现时间、未确认帧是否参与子帧事件，需要面试官定义。
- 只提供尾部 m 帧时，未知的祖先层不可直接补成完整根栈。可引入未知前缀标记，只对可对齐的后缀报告可证的变化；递归同名帧会使对齐歧义，必须列出可能解释或请求额外调用 id。
手动走一遍
样本 `(1,[A,A])` 发 `start(0,A), start(1,A)`；`(2,[A])` 只发 `end(1,A)`。再从 `[A,B]` 到 `[A,C]`，公共前缀只有 A，在新时间戳先 end B 后 start C。最后一个样本仍有 A 时保持开放，不能凭空补 end。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections.abc import Iterable
def stack_samples_to_events(
samples: Iterable[tuple[int, list[str]]],
) -> list[tuple[int, str, int, str]]:
"""Convert full root-to-leaf stack samples into start/end events.
Training contract: timestamps strictly increase; simultaneous ends are
deepest first, then starts shallowest first. Open frames stay open.
"""
events: list[tuple[int, str, int, str]] = []
previous: list[str] = []
last_time = None
for timestamp, current in samples:
if last_time is not None and timestamp <= last_time:
raise ValueError("timestamps must strictly increase")
common = 0
while (
common < len(previous)
and common < len(current)
and previous[common] == current[common]
):
common += 1
for depth in range(len(previous) - 1, common - 1, -1):
events.append((timestamp, "end", depth, previous[depth]))
for depth in range(common, len(current)):
events.append((timestamp, "start", depth, current[depth]))
previous = list(current)
last_time = timestamp
return events
复杂度
每次转换扫描公共前缀和变化后缀，若第 i 个栈长为 d_i，总时间 O(Σd_i)，输出上界同量级；额外状态 O(max d_i)，不含输出。连续 n 次追问可能需要 O(n·最大栈深) 的未决缓冲，具体取决于是否回填事件时间。
易错点与追问
容易失分的边界
- 把相同函数名去重，破坏递归帧的深度。
- 末尾自动结束所有活动帧，违背公开帖提到的最后 end 不用打印。
- 把采样时间当成真实调用发生的准确时间。
- 未定义 n 次确认是滑窗还是连续样本、start 时间取哪一帧，就声称已实现原 follow-up。
- 只有后缀 m 帧时，用普通 LCP 当成完整调用链，会虚构祖先的 start/end。
继续深挖
- 同时间戳多个样本的排序规则如何固定？
- 若帧包含函数名和调用 id，递归/重复帧识别会怎样改变？
- 对缺样、尾部 m 帧与连续 n 次过滤，怎样区分可证明事件和推断事件？
