O(1) 空间和时间的实时统计

Question

我最近提交了一份工作职位的代码挑战。它应该在 REST 服务上发布事务，如下所示：

发布/交易

{
   "amout" : "10.12"
   "timestamp" : "2018-09-25T12:00:00
}

和 GET /statistics 响应如下：

{
  "count" : "3"
  "min" : "100.00"
  "max" : "200.00"
  "sum" : "450.00"
  "avg" : "150.00"
}

这些限制使得解决方案变得困难，它们是：

1.- 它不应该使用 SQL 来存储事务，因此它基本上是内存中的事务缓存。

2.- 对于时间和辅助空间，它应该始终以 O(1) 执行

3.- 定期清理是不够的。

4.- 统计数据中仅应考虑从发出请求后的最后 60 秒内提交的事务。

我的第一个方法是为统计数据生成一个包装器，以当前服务器分钟作为 ID，每个事务或查询都会更新缓存，但这会失败，因为它只处理当前分钟的事务，在 60 秒内但从前一分钟开始的事务被忽略。

我想出的所有其他方法都需要某种形式的迭代，这违反了时间复杂度 O(1) 约束，最终我被拒绝了，但我想从社区学习什么是最好的方法。

干杯

Answer 1

似乎时间戳只有 1 秒的分辨率，因此您可以以每一秒的间隔进行统计。当处理 GET 请求时，您需要合并 60 个时间间隔的统计信息。

但就 big-O 而言，O(60) 和 O(1) 是同一件事。换句话说，如果您处理了 1000 万个 POST 事务，同时仅保留 60 组统计数据，那么您就满足了 O(1) 空间和时间要求。也就是说，允许进行一些迭代，只要迭代次数不依赖于交易数量。

将每个小时-分钟-秒映射到统计对象允许最多 60 次迭代处理 GET 请求，而不管收到的 POST 事务数量如何。