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

报价引擎活跃集合:并发活跃报价的峰值数量

Quote Engine Active Set: Peak Concurrently-Live Quotes

开始编码

实现 solution(events: list[list[str]]) -> int。某做市报价服务按到达顺序发出报价生命周期事件流 events,每条事件是 [quote_id, action],其中 action"ADD"(让该 quote_id 进入活跃集合)或 "REMOVE"(让该 quote_id 离开活跃集合;若该 id 当前并不活跃,则视为 no-op)。返回时间线上同时活跃的 quote_id 数量的峰值——即活跃集合大小所达到的最大值。

例:solution([["Q-1","ADD"],["Q-2","ADD"],["Q-3","ADD"],["Q-2","REMOVE"],["Q-4","ADD"]]) 返回 3。前三次 ADD 之后活跃集合为 {Q-1,Q-2,Q-3},大小为 3;REMOVE Q-2 之后降为 2,再 ADD Q-4 又升回 3。所有快照里的最大值就是 3。

需要明确的细节:空事件流返回 0;对已经活跃的 quote_id 再次 ADD 不会改变集合(同一 ID 不会在活跃集合里出现两次);任何 ADD 之前的 REMOVE、或对已经被移除的 quote_id 再次 REMOVE,都被静默忽略(幂等);同一 id 在 REMOVE 之后再次 ADD 允许的,并按一次新的激活计入。quote_id 按精确字符串身份比较(大小写、前后空白、纯数字字符串都视为不同)。

直接对每个前缀重算活跃集合是 O(N^2),在 N 接近 500000 的隐藏用例上会超时;用一个活跃 ID 的哈希集合加一个运行中的最大 size,即可在 O(N) 内完成扫描。

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

实践背景

做市商网关上的报价引擎维护着一张"活跃报价表"——交易所端目前挂着的全部 quote_id 集合。每个 ADD 把一条新报价推上去,每个 REMOVE / cancel 把它撤下来;在突发行情、批量撤单触发、会话重试等场景下,引擎瞬间持有的活跃报价数会显著高于稳态值。可靠性看板会追踪并发活跃报价数的峰值,把它作为交易所端报价表内存与撮合 message budget 的最坏情况负载,同时也是一项健康检查——引擎不应对同一 ID 出现重复挂单(重复 ADD 不能让计数膨胀)。把"对非活跃 id 的 REMOVE"视为 no-op 是有意的:在交易所已经 ack 上一次 cancel 之后,重发的 cancel 在生产里是常态,不应让账目逻辑崩掉。

约束条件

  • 0 <= N <= 500000,其中 N 为 solution(events) 的输入长度
  • 每个事件都是长度为 2 的列表 [quote_id, action],action 恰为 "ADD" 或 "REMOVE"
  • quote_id 为长度在 1 到 32 之间的 ASCII 字符串,区分大小写,不做归一化
  • 对当前非活跃(从未 ADD 或已被 REMOVE)的 quote_id 做 REMOVE 是 no-op
  • 输出为非负整数,使用精确比对;空事件流返回 0

样例

Case 1 · statement-example: peak before final REMOVE

输入: [[["Q-1","ADD"],["Q-2","ADD"],["Q-3","ADD"],["Q-2","REMOVE"],["Q-4","ADD"]]]

期望: 3

依次激活 Q-1,Q-2,Q-3 时 active 集合大小达到 3;随后 REMOVE Q-2 降到 2,再 ADD Q-4 升到 3,峰值仍为 3。

Case 2 · visible: REMOVE before any ADD is a no-op

输入: [[["q-x42","REMOVE"],["q-x42","ADD"],["q-y7","ADD"]]]

期望: 2

首个 REMOVE 在没有任何活跃 quote 时是 no-op;之后两次 ADD 让 active 集合大小达到 2。

Case 3 · visible: empty events returns 0

输入: [[]]

期望: 0

空事件流,峰值为 0。

Case 4 · visible: re-ADD after REMOVE is allowed

输入: [[["A","ADD"],["A","REMOVE"],["A","ADD"],["B","ADD"]]]

期望: 2

A 被 ADD、REMOVE 后再次 ADD 视为重新激活,配合 B 的 ADD 让峰值为 2。

最近提交

还没有提交记录。

编码区

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

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

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

Case 1 · statement-example: peak before final REMOVE

输入: [[["Q-1","ADD"],["Q-2","ADD"],["Q-3","ADD"],["Q-2","REMOVE"],["Q-4","ADD"]]]

期望: 3

依次激活 Q-1,Q-2,Q-3 时 active 集合大小达到 3;随后 REMOVE Q-2 降到 2,再 ADD Q-4 升到 3,峰值仍为 3。

Case 2 · visible: REMOVE before any ADD is a no-op

输入: [[["q-x42","REMOVE"],["q-x42","ADD"],["q-y7","ADD"]]]

期望: 2

首个 REMOVE 在没有任何活跃 quote 时是 no-op;之后两次 ADD 让 active 集合大小达到 2。

Case 3 · visible: empty events returns 0

输入: [[]]

期望: 0

空事件流,峰值为 0。

Case 4 · visible: re-ADD after REMOVE is allowed

输入: [[["A","ADD"],["A","REMOVE"],["A","ADD"],["B","ADD"]]]

期望: 2

A 被 ADD、REMOVE 后再次 ADD 视为重新激活,配合 B 的 ADD 让峰值为 2。