← 返回编程题库
coding-cross-feed-tick-match-count中等免费版2000ms未尝试

跨源行情心跳容差匹配计数

Cross-Feed Tick Match Count Within Tolerance Window

开始编码

一位交易员同时跑两条同标的的市场数据 feed——一条是同机房主 feed、一条是异地灾备 feed,需要每天报一项运维健康指标:ts_primary 中有多少条心跳能在 tol_ms 毫秒容差内被 ts_secondary 印证。请实现 solution(ts_primary: list[int], ts_secondary: list[int], tol_ms: int) -> int,返回满足如下条件的下标 i 的个数:在 ts_secondary存在至少一个下标 j 使得 |ts_primary[i] - ts_secondary[j]| <= tol_ms。每个 i 至多计一次(存在性语义,而非多对多配对计数)。

ts_primaryts_secondary 都是非递减的整数毫秒时间戳数组。两路均已预排序,所以最优形状是双指针线性扫描:维护一个指向 ts_secondary 的指针 j,让它随 i 单调推进——因为 ts_primary[i] - tol_msi 上非递减,j 永不回退。

边界情形:

  • len(ts_primary) == 0 返回 0。
  • len(ts_secondary) == 0 返回 0。
  • tol_ms == 0 退化为两路 feed 之间的严格等值时间戳匹配;同一份代码仍然成立,因为窗口塌缩为一个点。

例如:

ts_primary   = [10, 20, 35, 50]
ts_secondary = [11, 22, 49, 200]
tol_ms       = 2

solution(ts_primary, ts_secondary, tol_ms) 返回 3。下标 0(ts=10)匹配 secondary 中的 11(|10-11|=1)。下标 1(ts=20)匹配 22(|20-22|=2)。下标 3(ts=50)匹配 49(|50-49|=1)。下标 2(ts=35)距 2249 都过远(差值 13、14),不计。

实践背景

当两条冗余 feed 并行跑时,跨 feed 匹配率是最干净的微观结构运维指标之一。匹配率持续偏低意味着某条 feed 在丢心跳、被网络延迟拖偏,或时钟漂移——这是值班的信号:把不健康那条 feed 摘掉、不让陈旧报价驱动一笔坏成交。指标按日聚合,对全天的两路心跳流跑一次。生产里心跳量动辄数十亿条,所以线性扫描的 O(N + M)(而非 O(N log M))才是把日报压到分钟级而不是小时级的关键。

约束条件

  • 0 ≤ N、M ≤ 5000,其中 N = len(ts_primary)、M = len(ts_secondary)。算法应保持 O(N + M) 复杂度,从而在更大规模输入上仍然能在时限内完成。
  • 0 ≤ ts_primary[i] ≤ 1e9 且 0 ≤ ts_secondary[j] ≤ 1e9;两个数组均非递减(升序排序,单条 feed 内允许重复值)。
  • 0 ≤ tol_ms ≤ 1e9。匹配窗口 `[ts_primary[i] - tol_ms, ts_primary[i] + tol_ms]` 两端均闭。
  • `ts_primary` 中每个下标 `i` 至多计 1 次——存在性语义而非多对多配对计数。输出是 `[0, N]` 范围内的单一整数。
  • `tol_ms == 0` 时退化为严格等值时间戳匹配(两条 feed 已排序,定义良好)。
  • `ts_primary` 为空时返回 0;`ts_secondary` 为空时返回 0;二者皆空时也返回 0。
  • 若任一输入未排序,行为未定义;调用方负责输入校验。

样例

Case 1 · statement-example: three matches with tol=2

输入: [[10,20,35,50],[11,22,49,200],2]

期望: 3

题面例题:tol=2 时 ts_primary 中 10(配 11)、20(配 22)、50(配 49)三条都能在 ts_secondary 找到容差内的对手;35 离最近的 22 与 49 都超出 2,不计。

Case 2 · typical: tol=0 reduces to exact-timestamp intersection

输入: [[1,3,5,7,9],[2,3,6,9,10],0]

期望: 2

tol=0 时退化为严格等值匹配;ts_primary 中只有 3 与 9 在 ts_secondary 出现,计数 2。

最近提交

还没有提交记录。

编码区

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

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

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

Case 1 · statement-example: three matches with tol=2

输入: [[10,20,35,50],[11,22,49,200],2]

期望: 3

题面例题:tol=2 时 ts_primary 中 10(配 11)、20(配 22)、50(配 49)三条都能在 ts_secondary 找到容差内的对手;35 离最近的 22 与 49 都超出 2,不计。

Case 2 · typical: tol=0 reduces to exact-timestamp intersection

输入: [[1,3,5,7,9],[2,3,6,9,10],0]

期望: 2

tol=0 时退化为严格等值匹配;ts_primary 中只有 3 与 9 在 ts_secondary 出现,计数 2。