跨源行情心跳容差匹配计数
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_primary 与 ts_secondary 都是非递减的整数毫秒时间戳数组。两路均已预排序,所以最优形状是双指针线性扫描:维护一个指向 ts_secondary 的指针 j,让它随 i 单调推进——因为 ts_primary[i] - tol_ms 在 i 上非递减,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 = 2solution(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)距 22 与 49 都过远(差值 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 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
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。