Bloomberg 活动报名公平队列：注册、注销与最早 Top K

题意与假设

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

• 训练版 fair 指按成功注册时间先后；重复注册不改变位置，注销后重新注册排到尾部。
• topK 返回仍在队列的最早 k 个 ID；题目未定义重复/重报/负 k 返回语义，训练版明确约定。

解题路线

1. 维持双向链表保存报名顺序，hash map 由 userId 定位节点，注册存在则拒绝，否则尾插。
2. 注销借 map O(1) 找节点、在链表两侧重连后删除映射；topK 从头遍历 min(k,n) 个。
3. Python OrderedDict 的插入顺序可作为训练实现；生产并发时 register/unregister/topK 要约定线性化视图或在同一锁内快照。
4. 若 topK 高频而取消/重报频繁仍是 O(k) 输出下界；不能承诺生成 k 个 ID 用 O(1) 时间。

手动走一遍

A、B、C 注册，B 注销，再 B 注册：队列变 A,C,B；topK(2)=[A,C]。重复 A 注册若约定 no-op，顺序仍 A,C,B。

Python 参考实现

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

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

from collections import OrderedDict
from itertools import islice


class RegistrationQueue:
    def __init__(self):
        self.order = OrderedDict()

    def register(self, user_id):
        if user_id in self.order:
            return False
        self.order[user_id] = None
        return True

    def unregister(self, user_id):
        if user_id not in self.order:
            return False
        del self.order[user_id]
        return True

    def topK(self, k):
        if k < 0:
            raise ValueError("k must be nonnegative")
        return list(islice(self.order, k))

复杂度

hash+双链/OrderedDict 的注册与注销期望 O(1)，topK O(min(k,n)) 时间，空间 O(n)。

易错点与追问

容易失分的边界

• 用普通数组 remove 导致 O(n) 删除。
• 注销后保留旧链节点造成脏结果。
• 把取消后重报继续保留原优先级而未约定。
• 宣称 topK 输出 k 人仍为 O(1)。

继续深挖

• 如果要随机抽签而非先到先得？
• 多实例并发报名怎样保持同一顺序？
• 若用户有优先级或预约时段，fair 如何重定义？