Snowflake addTask/executeTask：优先级、时间戳与重复任务

题目重点：Onsite 公开 addTask(taskId,priority,timestamp)、重复添加和 executeTask 跳过已执行任务；用堆与执行集合实现并验证。

题意与假设

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

训练版数值越大优先级越高；同优先级按 timestamp 越早越先，同时间按加入顺序。executeTask 返回 taskId；没有待执行任务返回 None。
每个 taskId 在队列生命周期中最多真正执行一次；执行后再次 add 也会被跳过。这是对‘already executed skip’的直接训练解释，若允许新版本重执行需加入版本 ID。
调用单线程；多 worker 并发领取需队列出堆与 executed 记录原子化。

解题路线

将每次添加都按 (-priority,timestamp,sequence,taskId) 放入最小堆，保留重复条目；sequence 确定最终并列。
executeTask 反复弹出最高排序条目，若 taskId 已在 executed 则跳过；遇未执行 taskId 则先标记再返回。
每条堆记录最终最多弹出一次，故虽某次 executeTask 可能跳过许多旧项，长期摊销仍由总添加数控制。
用独立全列表排序基线随机执行 30 万次 add/execute 操作，检查同优先级、时间戳乱序、同 task 多次提交与空队列。

手动走一遍

add(A,5,100)、add(B,7,120)、add(A,9,130)：第一次 execute 返回 A（priority 9），第二次返回 B（7），再弹到 A(priority 5) 时已执行而跳过，之后返回 None。若优先级定义相反，堆键需改。

Python 参考实现

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

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

"""Execute highest-priority queued task once, skipping duplicate stale entries."""

import heapq


class TaskQueue:
    def __init__(self):
        self.heap = []
        self.executed = set()
        self.sequence = 0

    def add_task(self, task_id: str, priority: int, timestamp: int) -> None:
        heapq.heappush(self.heap, (-priority, timestamp, self.sequence, task_id))
        self.sequence += 1

    def execute_task(self) -> str | None:
        while self.heap:
            _, _, _, task_id = heapq.heappop(self.heap)
            if task_id in self.executed:
                continue
            self.executed.add(task_id)
            return task_id
        return None

复杂度

N 次添加各 O(log N)，每个条目最多弹出一次，共 O(N log N)；单次 executeTask 最坏 O(N log N) 因可能清理旧重复项，摊销按弹出条目计为 O(log N)。堆 O(N)、执行集合 O(U)，U 为不同 taskId 数。

易错点与追问

容易失分的边界

只用 taskId→最新任务覆盖旧项，却未确认重复添加的优先级语义。
执行前不原子标记，同一任务可能被两个 worker 领取。
说 executeTask 单次严格 O(log N)，忽略跳过大量已执行堆项。
没有确定 timestamp/加入序号的同优先级顺序。
把已执行 task 永久保留而无任务生命周期或 GC 策略。

继续深挖

若重加同一 taskId 是新版本，如何设计复合 execution key？
多 worker 下如何用 lease 处理执行中崩溃与至少一次重试？
若 priority 可动态修改，怎样处理堆中旧版本？
执行记录保留多久，如何防止过期后错误重复执行？