← 返回编程题库
coding-streaming-top-k-by-notional中等免费版2000ms未尝试

流式聚合:成交金额前 K 名股票

Streaming Top-K Tickers by Notional

开始编码

某交易终端的实时仪表盘要展示当日累计成交金额前 K 名股票的排行榜。交易作为事件流推过来,每条事件携带 tickerqtyprice。一条成交的金额是 qty * price;某只股票的「分数」是它全部成交的金额累加。请在吞下整段事件序列后,返回成交金额前 K 名的股票。

请实现 solution(events: list[dict], k: int) -> list[list]。每条事件是字典,键为 "ticker"(字符串)、"qty"(浮点)、"price"(浮点)。返回 [ticker, total_notional] 列表,长度为 min(k, 不同 ticker 数),按 total_notional 降序排列;金额相同时按 ticker 字典序升序破并。边界:k == 0events 为空时,返回 []k 超过实际不同代码数时,返回所有代码(按上述规则排序,不补齐)。

示例 1solution([{"ticker": "AAPL", "qty": 10.0, "price": 150.0}, {"ticker": "MSFT", "qty": 5.0, "price": 300.0}, {"ticker": "AAPL", "qty": 20.0, "price": 151.0}], 2) 返回 [["AAPL", 4520.0], ["MSFT", 1500.0]]。AAPL 累计 10*150 + 20*151 = 1500 + 3020 = 4520;MSFT 是 5*300 = 1500。两只都在 K=2 的容量内,按金额降序输出。

示例 2(K 比代码数小):solution([{"ticker": "A", "qty": 1.0, "price": 100.0}, {"ticker": "B", "qty": 2.0, "price": 100.0}, {"ticker": "C", "qty": 3.0, "price": 100.0}], 2) 返回 [["C", 300.0], ["B", 200.0]]。三只代码、K=2,最小的那只被淘汰。示例 3(金额并列):solution([{"ticker": "ZZ", "qty": 1.0, "price": 100.0}, {"ticker": "AA", "qty": 1.0, "price": 100.0}], 2) 返回 [["AA", 100.0], ["ZZ", 100.0]]——金额并列按字典序升序("AA" < "ZZ")。

这道题是经典的流式 top-K + 聚合:扫一遍事件流入 dict,然后视 K/u 的比例决定走全排还是堆。真实做市/经纪台每隔几秒就在订单流上跑一遍这种统计——它是市场微观结构里一个一行就能算出来的「热门」指标,告诉你今天的成交金额集中在哪些代码上。同样的「按某个分数维护 top-K」的堆模式,也出现在最大对手方敞口、当日涨跌幅前 K、订单簿最活跃 K 等所有「按 score 取头部」的场景里。

约束条件

  • 0 ≤ len(events) ≤ 100000
  • 0 ≤ k ≤ 1000
  • 每个事件形如 `{"ticker": str, "qty": float, "price": float}`
  • `ticker` 为字母数字字符串,长度 ≤ 16,区分大小写
  • `qty`、`price` 是有限非负浮点数(允许为 0,那笔单 notional 就是 0)
  • 返回 `[[ticker, total_notional], ...]`,长度为 `min(k, 不同 ticker 数)`
  • 按 `total_notional` 降序;金额相同则按 `ticker` 字典序升序破并
  • 返回浮点值容差:rel_tol=1e-9, abs_tol=1e-12

样例

Case 1 · two tickers fit inside K

输入: [[{"ticker":"AAPL","qty":10,"price":150},{"ticker":"MSFT","qty":5,"price":300},{"ticker":"AAPL","qty":20,"price":151}],2]

期望: [["AAPL",4520],["MSFT",1500]]

AAPL 累计 10*150 + 20*151 = 4520;MSFT = 5*300 = 1500。两只都在 K=2 内,按金额降序输出。

Case 2 · K caps the result, drop smallest

输入: [[{"ticker":"A","qty":1,"price":100},{"ticker":"B","qty":2,"price":100},{"ticker":"C","qty":3,"price":100}],2]

期望: [["C",300],["B",200]]

三只代码、K=2,最小金额的 A=100 被淘汰;输出 C=300、B=200。

Case 3 · tie on notional broken alphabetically

输入: [[{"ticker":"ZZ","qty":1,"price":100},{"ticker":"AA","qty":1,"price":100}],2]

期望: [["AA",100],["ZZ",100]]

金额并列 100,按字典序升序:AA 在前,ZZ 在后。

最近提交

还没有提交记录。

编码区

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

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

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

Case 1 · two tickers fit inside K

输入: [[{"ticker":"AAPL","qty":10,"price":150},{"ticker":"MSFT","qty":5,"price":300},{"ticker":"AAPL","qty":20,"price":151}],2]

期望: [["AAPL",4520],["MSFT",1500]]

AAPL 累计 10*150 + 20*151 = 4520;MSFT = 5*300 = 1500。两只都在 K=2 内,按金额降序输出。

Case 2 · K caps the result, drop smallest

输入: [[{"ticker":"A","qty":1,"price":100},{"ticker":"B","qty":2,"price":100},{"ticker":"C","qty":3,"price":100}],2]

期望: [["C",300],["B",200]]

三只代码、K=2,最小金额的 A=100 被淘汰;输出 C=300、B=200。

Case 3 · tie on notional broken alphabetically

输入: [[{"ticker":"ZZ","qty":1,"price":100},{"ticker":"AA","qty":1,"price":100}],2]

期望: [["AA",100],["ZZ",100]]

金额并列 100,按字典序升序:AA 在前,ZZ 在后。