LinkedIn 多线程函数 Inclusive/Exclusive Time：每线程调用栈计时

题目重点：以半开 start/end 时间戳计算调用总时长，减子调用得到独占时间；同名递归和多线程分别累计。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

训练事件为 (thread_id,function,kind,timestamp)，同线程事件非降序，end 为半开结束时间；每线程调用栈正确嵌套，跨线程可交错。
同一函数多次调用/递归时把各调用耗时累计到该函数名；若题目问单次 invocation，应输出调用 ID 明细而非聚合。

解题路线

给每个 thread 独立栈，每个 frame 保存函数名、start、直接子调用 inclusive 累计。start 压栈；end 必须匹配栈顶，计算 elapsed=end-start，exclusive=elapsed-child_time，分别累加。
结束一个 frame 后把其 elapsed 加到父 frame 的 child_time；这样父函数只扣直接子调用，其孙调用已包含在子调用 elapsed 中，避免重复扣。
不同线程不共享调用栈；若线程内事件未排序，要先按 timestamp 与同时间戳 start/end 规则排序。墙钟时间不等于 CPU 实际运行时间，如果需求真是 CPU time，事件需提供调度上下文/CPU 采样，题目名称不能自动证明有这个数据。
可在线处理日志 O(E)，但未关闭 frame 到流结束需标错误或保留状态；日志丢失/时间回退需要检测。

手动走一遍

AB start0、CD start3、EF start5/end6、CD end8、AB end9：EF inclusive/exclusive 1，CD inclusive5/exclusive4，AB inclusive9/exclusive4。若 CD 在另一线程，它不能从 AB 的 exclusive 中扣掉。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from collections import defaultdict


def function_times(events):
    """Events: (thread_id, function_name, 'start'|'end', timestamp). End exclusive."""
    stacks = defaultdict(list)
    totals = defaultdict(lambda: [0, 0])  # inclusive, exclusive
    last_time = {}
    for thread, function, kind, timestamp in events:
        if timestamp < last_time.get(thread, timestamp):
            raise ValueError("events out of order within thread")
        last_time[thread] = timestamp
        stack = stacks[thread]
        if kind == "start":
            stack.append([function, timestamp, 0])  # child elapsed time
        elif kind == "end":
            if not stack or stack[-1][0] != function:
                raise ValueError("unmatched end")
            _, start, child_time = stack.pop()
            elapsed = timestamp - start
            if elapsed < child_time:
                raise ValueError("invalid nested timestamps")
            totals[function][0] += elapsed
            totals[function][1] += elapsed - child_time
            if stack:
                stack[-1][2] += elapsed
        else:
            raise ValueError("unknown event kind")
    if any(stacks.values()):
        raise ValueError("unclosed function")
    return {name: tuple(times) for name, times in totals.items()}

复杂度

E 条事件处理 O(E) 时间；栈空间 O(所有线程当前最大并发调用深度)，聚合表 O(不同函数数)。训练代码用题目样例和 10,000 组随机多线程嵌套日志，对逐时间单位独立计数 oracle 验证。

易错点与追问

容易失分的边界

全局只用一个栈，跨线程嵌套错乱。
父函数把孙调用又扣一次。
end-start 与含端点 `+1` 规则混用。
把 wall-clock inclusive 宣称真实 CPU 使用时间。
同名递归层未单独建 frame。

继续深挖

日志乱序但有 invocation ID 怎么重建？
真实 CPU running time 与墙钟时间如何区分？
跨线程 async task 如何关联因果时间？
同时间戳 end/start 顺序怎么定？