报价引擎活跃集合:并发活跃报价的峰值数量
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 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
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。