Bloomberg Ordered Stream：乱序插入后返回连续输出块

题意与假设

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

• 训练版初始化 n 个 1-based 槽，insert(id,value) 设置空槽并返回从 pointer 开始连续存在的最大值列表。
• 重复 ID 报错，缺口时返回 []；题目没有披露这些细节，不能说这就是面试原版完整接口。

解题路线

1. 数组 values[1..n] 存各位置，pointer 初始 1，始终指向尚未输出的最小 ID。
2. insert 先校验 ID/重复，将值存槽；从 pointer 起连续非空就逐个输出并向右移动，遇第一个空槽停。
3. pointer 只单调前进且每槽至多被输出一次，故所有插入累计线性，单次可因一次补洞吐出很长块。
4. 若 ID 域很大或动态增长，可用哈希存槽和同样指针，空间按实际插入量；仍要定义上界与迟到重复。

手动走一遍

n=4：insert(3,C)→[]，insert(1,A)→[A]，insert(4,D)→[]，insert(2,B)→[B,C,D]；pointer 从 1 最终到 5。

Python 参考实现

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

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

class OrderedStream:
    def __init__(self, n):
        if n < 0:
            raise ValueError("n must be nonnegative")
        self.values = [None] * (n + 1)
        self.pointer = 1

    def insert(self, position, value):
        if not 1 <= position < len(self.values):
            raise IndexError(position)
        if self.values[position] is not None:
            raise ValueError("position already set")
        self.values[position] = value
        chunk = []
        while self.pointer < len(self.values) and self.values[self.pointer] is not None:
            chunk.append(self.values[self.pointer])
            self.pointer += 1
        return chunk

复杂度

数组版初始化/空间 O(n)，m 次插入合计 O(n+m)（含输出），单次最坏 O(n) 因可能输出 n 项；不应声称每次严格 O(1)。

易错点与追问

容易失分的边界

• 插入 3 时立刻输出 3，跳过缺口。
• 重复 ID 再次输出。
• 把摊还 O(1) 输出维护误写成单次 O(1)。
• 未说明训练接口来自题名推定。

继续深挖

• 若 ID 动态无上界？
• 允许覆写已经输出的 ID 吗？
• 多线程乱序插入如何同步 pointer？