← 返回编程题库
coding-orphan-cancel-count中等免费版2000ms未尝试

路由可靠性检查:统计孤儿撤单数量

Router Reliability Check: Count Orphan Cancellations

开始编码

实现 solution(events: list[list[str]]) -> int。一个交易路由器按到达顺序输出订单生命周期事件流 events,每个事件为 [order_id, action],其中 action 取值为 "NEW"(订单上线)或 "CANCEL"(撤单)。一条撤单被视为孤儿当且仅当其 order_id 在该事件之前从未"NEW" 出现过。返回孤儿撤单的数量

例:solution([["O-1","NEW"],["O-2","CANCEL"],["O-1","CANCEL"],["O-3","CANCEL"]]) 返回 2。第一条事件是 O-1 的 NEW;第二条是 O-2 的 CANCEL,但 O-2 此前从未 NEW,故计为孤儿;第三条是 O-1 的 CANCEL,由于 O-1 已经 NEW 过,故为非孤儿;第四条是 O-3 的 CANCEL,此前也从未 NEW,再计一份孤儿。合计孤儿数 = 2。

需要明确的细节:空输入返回 0;同一 id 的重复 NEW 是幂等的(一次 NEW 足以让该 id 之后的所有 CANCEL 都非孤儿);同一从未 NEW 过的 id 多次 CANCEL,每次各计一份孤儿(它们在线路上是独立事件);当一条 NEW 出现在某 id 的 CANCEL 之后时,不会回溯把更早那条 CANCEL 转为非孤儿——孤儿与否在 CANCEL 到达的那一刻就根据"截至此刻已见的内容"判定。

直接做 O(N^2) 的回溯比较在小样本下尚可,但隐藏用例会把 N 推到上限以测试线性方案;用一个哈希集合维护"截至当前曾以 NEW 出现的所有 order_id",边扫边判即可把整体复杂度压到 O(N)。

实现细节由 stubs/stub.py 提供。

实践背景

交易路由器在客户端引擎与交易所网关之间承上启下:每条向外发送的子单都应先以 NEW 出现在线路上,随后等待成交、撤单或两者都有。一旦路由器对某个未曾发出 NEW 的 order_id 发出了 CANCEL,这条撤单就是"孤儿"——多半意味着上游 NEW 丢失、会话被无状态回放,或者两条路由腿之间的命名空间产生了串扰。运维侧通常按分钟桶聚合孤儿撤单数量,超过会话阈值即触发告警;这里关心的并非头寸或盈亏,而是计数本身——每一条孤儿撤单都是一次需要查清的簿记缺口。判定刻意是 CANCEL 到达时的一锤定音:到孤儿信号被触发的那一刻,上游因果链已经断了,再回看后到的 NEW 也无补于事。

约束条件

  • 0 <= N <= 2000,其中 N 为 solution(events) 的输入长度
  • 每个 events[i] 是含两个元素的列表 [order_id: str, action: str]
  • action 取值仅为 "NEW" 或 "CANCEL";order_id 为长度在 1 到 32 之间的 ASCII 字符串,区分大小写
  • 空输入返回 0;若不存在任何 CANCEL,结果为 0
  • 输出为非负整数,使用精确比对

样例

Case 1 · statement-example: O-2 and O-3 are orphan, O-1 is not

输入: [[["O-1","NEW"],["O-2","CANCEL"],["O-1","CANCEL"],["O-3","CANCEL"]]]

期望: 2

O-1 已先 NEW 故其 CANCEL 非孤儿;O-2 与 O-3 此前未 NEW,各计 1,合计 2。

Case 2 · visible: empty input returns 0

输入: [[]]

期望: 0

空输入直接返回 0。

Case 3 · visible: NEW after orphan CANCEL does not retroactively un-orphan

输入: [[["O-9","CANCEL"],["O-9","NEW"],["O-9","CANCEL"]]]

期望: 1

第一条 CANCEL 在 O-9 NEW 之前到达,已计为孤儿;第三条 CANCEL 之前 O-9 已 NEW,非孤儿;合计 1。

最近提交

还没有提交记录。

编码区

实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

Case 1 · statement-example: O-2 and O-3 are orphan, O-1 is not

输入: [[["O-1","NEW"],["O-2","CANCEL"],["O-1","CANCEL"],["O-3","CANCEL"]]]

期望: 2

O-1 已先 NEW 故其 CANCEL 非孤儿;O-2 与 O-3 此前未 NEW,各计 1,合计 2。

Case 2 · visible: empty input returns 0

输入: [[]]

期望: 0

空输入直接返回 0。

Case 3 · visible: NEW after orphan CANCEL does not retroactively un-orphan

输入: [[["O-9","CANCEL"],["O-9","NEW"],["O-9","CANCEL"]]]

期望: 1

第一条 CANCEL 在 O-9 NEW 之前到达,已计为孤儿;第三条 CANCEL 之前 O-9 已 NEW,非孤儿;合计 1。