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

Question

我最近提交了一份工作职位的代码挑战。它应该按如下方式在 REST 服务上发布事务:

POST/交易

{
   "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 个区间的统计信息。

但就大 O 而言，O(60) 和 O(1) 是一回事。换句话说，如果您处理了 1000 万个 POST 事务，而只保留 60 组统计信息，那么您就满足了 O(1) 空间和时间要求。也就是说，允许进行一些迭代，只要迭代次数不依赖于事务数即可。

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