Google VO 面试真题解析：Receives Log Entries and Detect Timed-Out RPCs

Imagine you have an RPC server that produces log entries and you’re analyzing it offline. There are two entries for each call: one when the RPC starts and one when the RPC finishes processing.

Your task is to efficiently determine if any RPC in the log timed out.

You can assume your function receives two arguments:

• A timeout duration.
• A collection of pre-parsed log entries, already sorted by timestamp.

To test your understanding, consider the following example:

Input timeout: 3

Input log:

| ID | Timestamp | Event Type |
|----|-----------|------------|
| 1  | 0         | Start      |
| 2  | 1         | Start      |
| 1  | 2         | End        |
| 3  | 6         | Start      |
| 2  | 7         | End        |
| 3  | 8         | End        |

Graphical representation of the log:

ID 1: [0, 2]
ID 2: [1, 7]
ID 3: [6, 8]

这道题要求在已经按时间排序的 RPC 日志中，判断是否存在超时调用。每条调用都会对应一对日志：Start 和 End，因此可以在遍历时用哈希表记录每个 ID 的开始时间，遇到 End 时计算持续时间是否超过阈值。由于输入已经有序，整题可以用一次线性扫描完成，时间复杂度 O(n)，空间复杂度 O(k)，其中 k 是同时未结束的调用数。