← 返回编程题库
coding-merge-k-venue-trade-tapes中等免费版2000ms未尝试

将 K 路场所成交磁带合并为单一时间序流

Merge K Per-Venue Trade Tapes Into One Chronological Stream

开始编码

一位交易员从 K 个执行场所收到原始成交磁带。每个场所 k(即输入列表 tapes 中从 0 起的下标)落下一条按 timestamp 升序的事件流 tapes[k],其中每条事件是 [timestamp, price, size]。要做盘后分析——TCA、成交归因、合规对账——需要把所有场所的事件归并成 一条按时间序的统一流,并把 venue_id 作为额外一列写入每行,让下游管线能把每一笔成交追溯到来源场所。

请实现 solution(tapes: list[list[list[float]]]) -> list[list[float]]。输出是一段 4 元素列表 [timestamp, venue_id, price, size],按 timestamp 升序排列;当来自不同 venue 的事件 timestamp 相等时,venue_id 更小的先输出。同一 venue 内部的事件保持其在 tapes[k] 的原始顺序——不要重排同一 venue 内 timestamp 相等的事件。

边界情况:

  • tapes == [](即 K = 0)时返回 []
  • 某条 tapes[k] == [] 是合法的,静默跳过、不贡献任何输出。
  • 输出长度等于所有非空磁带的事件总数。

例如,3 条磁带:

tapes = [
  [[1.0, 100.5, 10], [3.0, 100.7, 5]],
  [[1.0, 200.1, 7], [2.0, 200.2, 3]],
  [[2.0, 300.0, 1]],
]

solution(tapes) 返回:

[[1.0, 0, 100.5, 10],
 [1.0, 1, 200.1, 7],
 [2.0, 1, 200.2, 3],
 [2.0, 2, 300.0, 1],
 [3.0, 0, 100.7, 5]]

timestamp = 1.0 时 venue 0 比 venue 1 先输出(venue_id 更小者赢);timestamp = 2.0 时 venue 1 比 venue 2 先输出,同样的规则。

实践背景

跨场所磁带对账是盘后分析的入口。交易员的 blotter、broker 的磁带、场所的 drop-copy 各自只能给出部分视图;把它们归并成一条按时间序、把 venue_id 写入每行的统一流,是让所有下游任务(TCA、成交归因、监控、合规事件报送)面向同一张表运行的最小一步。把并列时序的处理写对,才能避免一个逻辑订单的两笔同时间戳成交被错归到别的场所,污染下游报表。

约束条件

  • 0 ≤ len(tapes) ≤ 100;每条磁带长度 0 ≤ len ≤ 200;所有磁带事件总数 ≤ 500。算法仍应保持 O(N log K) 复杂度,从而在更大 N 下依旧能在时限内通过。
  • 每条磁带内部按 timestamp 升序预排序;磁带的 venue_id 即其在 `tapes` 中的下标(从 0 起)。
  • 每条事件是一个 3 元素列表 `[timestamp, price, size]`:`timestamp` 是非负浮点数,`price` 是正浮点数,`size` 是正整数。
  • 当来自不同 venue 的两条事件 timestamp 相等时,venue_id 更小的那条先输出。
  • 同一条磁带内部的相对顺序保持原样(不要重排同一 venue 内 timestamp 相等的事件——按输入顺序输出)。
  • 输出是一段按时间序的 4 元素列表 `[timestamp, venue_id, price, size]`;若 `tapes == []` 或所有磁带为空则结果为 `[]`。
  • 内层空磁带静默跳过、不贡献任何输出。

样例

Case 1 · statement-example: three venues with tied timestamps

输入: [[[[1,100.5,10],[3,100.7,5]],[[1,200.1,7],[2,200.2,3]],[[2,300,1]]]]

期望: [[1,0,100.5,10],[1,1,200.1,7],[2,1,200.2,3],[2,2,300,1],[3,0,100.7,5]]

题面例题:t=1.0 时 venue 0 比 venue 1 先输出,t=2.0 时 venue 1 比 venue 2 先输出;输出共 5 条按时间序排列。

Case 2 · typical: two venues, fully interleaved, no ties

输入: [[[[0.5,10,1],[1.5,11,2]],[[1,20,3],[2,21,4]]]]

期望: [[0.5,0,10,1],[1,1,20,3],[1.5,0,11,2],[2,1,21,4]]

两个 venue 完全交错且无并列时间戳,输出按 timestamp 严格升序排列,每行附上 venue_id。

最近提交

还没有提交记录。

编码区

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

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

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

Case 1 · statement-example: three venues with tied timestamps

输入: [[[[1,100.5,10],[3,100.7,5]],[[1,200.1,7],[2,200.2,3]],[[2,300,1]]]]

期望: [[1,0,100.5,10],[1,1,200.1,7],[2,1,200.2,3],[2,2,300,1],[3,0,100.7,5]]

题面例题:t=1.0 时 venue 0 比 venue 1 先输出,t=2.0 时 venue 1 比 venue 2 先输出;输出共 5 条按时间序排列。

Case 2 · typical: two venues, fully interleaved, no ties

输入: [[[[0.5,10,1],[1.5,11,2]],[[1,20,3],[2,21,4]]]]

期望: [[0.5,0,10,1],[1,1,20,3],[1.5,0,11,2],[2,1,21,4]]

两个 venue 完全交错且无并列时间戳,输出按 timestamp 严格升序排列,每行附上 venue_id。