最近一场 Apple 软件工程师面试，Coding 环节遇到了一道比较典型的数据处理题。题目本身不算特别难，但面试官比较关注边界情况，以及代码在真实系统中的可靠性。

Interview Question

Given a list of device events, return the latest status of each device. Events may arrive out of order.

Each event contains:

device_id
status
timestamp

For example:

[
  {device_id: "A", status: "online",  timestamp: 100},
  {device_id: "B", status: "offline", timestamp: 120},
  {device_id: "A", status: "offline", timestamp: 150},
  {device_id: "A", status: "online",  timestamp: 130}
]

Expected result:

{
  "A": "offline",
  "B": "offline"
}

中文简单来说，就是：

给你一批设备状态事件，因为网络延迟等原因，这些事件到达的顺序不一定和真实发生时间一致。需要根据 timestamp，找出每台设备最新的状态。

面试过程

刚看到题目的时候，一个比较自然的思路是按照 timestamp 排序，然后从前往后更新每个 device 的状态。

这个方案当然能做，但需要：

O(n log n)

面试官随后问了一句：

Do we actually need to sort all the events?

这里基本就是在提示优化。

其实我们只关心每台设备 timestamp 最大的那条记录，所以不需要对所有事件排序。

遍历一次事件列表，对每个 device_id 保存当前见过的最大 timestamp 和对应 status 即可。

核心逻辑类似：

latest = {}

for event in events:
    device_id = event["device_id"]

    if (
        device_id not in latest
        or event["timestamp"] > latest[device_id]["timestamp"]
    ):
        latest[device_id] = event

这样时间复杂度可以降到：

O(n)

空间复杂度取决于设备数量：

O(k)

其中 k 是不同 device 的数量。

后面的追问

写完基础版本后，面试官继续加了一个条件：

What if two events for the same device have exactly the same timestamp?

这个地方就不能自己默认答案了。

我先和面试官确认：

如果 timestamp 相同，是保留第一条、最后一条，还是还有一个额外的 sequence number 可以判断顺序？

面试官最后给的规则是：

If timestamps are equal, keep the event that appears later in the input.

这样修改其实很简单。

判断条件从：

timestamp > previous_timestamp

改成：

timestamp >= previous_timestamp

因为后出现的事件会覆盖前面的记录。

这个追问代码本身并不复杂，但比较考验候选人有没有意识到：

timestamp 并不一定能够唯一确定事件顺序。

csoahelp 的实时文本辅助比较适合这种场景：面试过程中可以实时整理面试官的问题，并快速给出当前题目的思路、复杂度、边界情况以及后续追问方向。

如果想提前适应这种真实面试节奏，也可以通过 Mock Interview 模拟这种“先给基础题，再连续追加 requirement”的面试方式。

相比单纯刷题，这种训练会更接近 Apple、Google、Stripe 等公司的实际 Coding Interview。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~