Amazon 前端 Coding：失败后持续失败，二分找首次失败日志

题意与假设

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

• 训练日志按timestamp非降序并可随机访问，状态模式success* failure*。
• 返回首条失败记录时间；没有失败返回None。它不是两次观测之间真实故障发生时刻的精确推断。

解题路线

1. 以半开[lo,hi)搜索第一条failed。mid失败则答案在mid或左边，hi=mid；mid成功则答案严格在右边，lo=mid+1。收敛位置可能等于n，表示全成功。
2. 不变量：lo左侧已经证明成功，hi及右侧（若存在）已经证明失败；每步保留所有可能的首失败位置。空输入也自然返回None。
3. 二分依赖数组顺序与状态单调。若日志乱序需要先排序O(n log n)，若会恢复成功，谓词不单调只能扫描或按每次事故分段；不能为了二分忽略反例。
4. 若只有流式日志或网络API，随机访问成本另算；最后一次成功t0和首次失败t1只定位检测区间，实际发生可在(t0,t1]而非必为t1。

手动走一遍

训练例[(1,F),(3,F),(7,T),(9,T)]返回7；若t3成功、t7失败，首次观察失败为7而真实发生时间只能界定在(3,7]。

Python 参考实现

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

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

def first_failure(logs):
    """(timestamp, failed) sorted chronologically; False* True* status contract."""
    lo,hi = 0,len(logs)
    while lo < hi:
        mid = (lo+hi)//2
        if logs[mid][1]:
            hi = mid
        else:
            lo = mid+1
    return None if lo == len(logs) else logs[lo][0]

复杂度

合同成立O(log n)状态查询、O(1)空间；确认单调本身O(n)，不能每次全量确认又声称整体对未知数据O(log n)。

易错点与追问

容易失分的边界

• 忽略日志排序。
• 恢复后False破坏二分却仍运行。
• 把首条观测时间当真实事件精确时间。

继续深挖

• API访问昂贵如何缓存探测？
• 不知长度的日志怎样指数扩展？
• 实时append后故障恢复如何表示多个段？