跨源行情两侧各自未匹配心跳计数
Cross-Feed Unmatched Tick Counts Per Side Within Tolerance
开始编码一位交易员同时跑两条同标的的市场数据 feed——feed A 与 feed B,需要每天报一项运维不对称性指标:每条 feed 上有多少条心跳无法在 tolerance 毫秒容差内被另一条 feed 印证。请实现 solution(stream_a: list[int], stream_b: list[int], tolerance: int) -> list[int],返回长度为 2 的列表 [count_unmatched_a, count_unmatched_b]:
count_unmatched_a= #{i instream_a:在stream_b中不存在b使得|stream_a[i] - b| <= tolerance}count_unmatched_b= #{j instream_b:在stream_a中不存在a使得|stream_b[j] - a| <= tolerance}
stream_a 与 stream_b 都是严格升序的整数毫秒时间戳数组。两侧均按"存在性语义"独立计数——一侧的某条心跳可以同时印证另一侧任意多条查询。两次对称的线性扫描各用一个指针,总工作量 O(N + M)。
算法
A 侧扫描:维护指向 stream_b 的指针 j。让 i 顺序遍历 stream_a,对每个 i 持续推进 j,直到 stream_b[j] >= stream_a[i] - tolerance。内层循环结束后,若 j 仍在范围内,stream_b[j] 就是不小于下界的最小辅 feed 时间戳——也就是闭区间窗口里的唯一候选——一次 stream_b[j] <= stream_a[i] + tolerance 判断即可裁定是否存在。判断不通过则 i 计入 count_unmatched_a 一次。stream_a 严格升序保证下界非递减,j 永不回退。
B 侧扫描是镜像版本:交换 stream_a 和 stream_b 的角色,把指针重置回 0(目标数组换了,A 侧的单调性对 B 侧毫无意义),跑同样的循环、累计 count_unmatched_b。
边界情形:
- 若
len(stream_a) == 0返回[0, len(stream_b)](A 侧没有元素;B 侧每个 b 都没有 a 可以印证,全部 unmatched)。 - 若
len(stream_b) == 0返回[len(stream_a), 0](对称)。 - 两者皆空返回
[0, 0]。 tolerance == 0退化为两条 feed 之间的严格等值时间戳匹配;同一份代码仍然成立,因为窗口塌缩为一个点。
例如:
stream_a = [10, 20, 35, 50]
stream_b = [11, 22, 49, 200]
tolerance = 2solution(stream_a, stream_b, tolerance) 返回 [1, 1]。A 侧:10 配 11(差 1)、20 配 22(差 2)、35 在 stream_b 里找不到容差内的对手(最近的 22 和 49 都超出 2)、50 配 49(差 1),所以 count_unmatched_a = 1。B 侧:11 配 10、22 配 20、49 配 50、200 在 stream_a 里找不到容差内的对手,所以 count_unmatched_b = 1。
实践背景
当两条冗余 feed 并行跑时,跨 feed 两侧各自的"未匹配数"刻画的是单一匹配率指标无法捕捉的 feed 不对称性。若某条 feed 在悄悄丢心跳或重复推送,整体匹配率看起来还可以,但两侧的未匹配数会发生分裂——可以反推出是哪条 feed 在掉链子。这对 (count_a_only, count_b_only) 正是值班决定把哪条 feed 摘出交易链路、避免陈旧报价驱动坏成交所依赖的信号。指标按日聚合,对全天的两路心跳流跑一次。生产里心跳量动辄数十亿条,所以线性扫描的 O(N + M)(而非 O(N log M))才是把日报压到分钟级而不是小时级的关键。
约束条件
- 0 ≤ N、M ≤ 1500,其中 N = len(stream_a)、M = len(stream_b)。算法应保持 O(N + M) 复杂度,从而在更大规模输入上仍然能在时限内完成。
- 0 ≤ stream_a[i] ≤ 1e9 且 0 ≤ stream_b[j] ≤ 1e9;两个数组都严格升序(单条 feed 内部不允许重复)。
- 0 ≤ tolerance ≤ 1e9。匹配窗口 `[x - tolerance, x + tolerance]` 两端均闭;恰好落在 `x ± tolerance` 处的候选也算命中。
- 两侧均按"存在性语义"独立计数——一侧的某个元素可以同时印证另一侧任意多个元素,这不是二分图一一配对。
- `tolerance == 0` 时退化为严格等值时间戳匹配(两条 feed 已严格升序,定义良好)。
- `stream_a` 为空时返回 `[0, M]`;`stream_b` 为空时返回 `[N, 0]`;二者皆空返回 `[0, 0]`。
- 输出为 `list[int]`,定长 2,顺序为 `[count_unmatched_a, count_unmatched_b]`。两个分量都落在 `[0, max(N, M)]` 内。
- 若任一输入未排序或单条内部存在重复,行为未定义;调用方负责输入校验。
样例
Case 1 · statement-example: tol=2, both sides one unmatched
输入: [[10,20,35,50],[11,22,49,200],2]
期望: [1,1]
题面例题:tol=2 时 A 侧 35 找不到容差内的 b(最近的 22 与 49 都过远),B 侧 200 找不到容差内的 a,其余双向印证。
Case 2 · typical: tol=0 reduces to set-difference counts
输入: [[1,3,5,7,9],[2,3,6,9,10],0]
期望: [3,3]
tol=0 时退化为严格等值匹配:A∩B={3,9};A 侧 unmatched 是 {1,5,7} 计 3;B 侧 unmatched 是 {2,6,10} 计 3。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · statement-example: tol=2, both sides one unmatched
输入: [[10,20,35,50],[11,22,49,200],2]
期望: [1,1]
题面例题:tol=2 时 A 侧 35 找不到容差内的 b(最近的 22 与 49 都过远),B 侧 200 找不到容差内的 a,其余双向印证。
Case 2 · typical: tol=0 reduces to set-difference counts
输入: [[1,3,5,7,9],[2,3,6,9,10],0]
期望: [3,3]
tol=0 时退化为严格等值匹配:A∩B={3,9};A 侧 unmatched 是 {1,5,7} 计 3;B 侧 unmatched 是 {2,6,10} 计 3。