← 返回编程题库
coding-cross-feed-unmatched-ticks-each-side中等免费版2000ms未尝试

跨源行情两侧各自未匹配心跳计数

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 in stream_a:在 stream_b不存在 b 使得 |stream_a[i] - b| <= tolerance}
  • count_unmatched_b = #{j in stream_b:在 stream_a不存在 a 使得 |stream_b[j] - a| <= tolerance}

stream_astream_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_astream_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 = 2

solution(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 可见样例;服务端提交会运行可见样例和隐藏测试。

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

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

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。