Живая статистика в O (1) пространстве и времени

Question

Я недавно отправил кодовый запрос на вакансию. Предполагалось размещать транзакции на REST-сервисе следующим образом:

POST / транзакции

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

и GET / статистика с ответом следующим образом:

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

Ограничения - это то, что делает решение трудным, и они:

1.- Он не должен использовать SQL для хранения транзакций, поэтому он в основном находится в кеше транзакций в памяти.

2.- Он всегда должен работать в O (1) для времени и вспомогательного пространства

3.- Запланированной очистки недостаточно.

4.- Для статистики должны учитываться только транзакции, совершенные за последние 60 секунд с момента подачи запроса.

Мой первый подход состоял в том, чтобы сгенерировать оболочку для статистики с текущей минутой сервера в качестве идентификатора каждой транзакции или запроса, обновляющего кэш, но это не удается, поскольку он обрабатывает только текущие минутные транзакции, отклоняя транзакции в течение 60 секунд, но по сравнению с предыдущими минут.

Для всех других подходов, которые я придумал, требовалась какая-то итерация, которая со временем нарушала ограничение O (1), в конце меня отвергли, но я хочу узнать от сообщества, какой подход был бы лучшим.

Приветствия

Answer 1

Похоже, что метки времени имеют разрешение только 1 секунду, поэтому вы можете хранить статистику для каждого интервала в одну секунду. Когда GET-запрос обрабатывается, вам нужно объединить статистику из 60 интервалов.

Но O (60) и O (1) - это одно и то же, что касается big-O. Другими словами, если вы обработали 10 миллионов транзакций POST, сохранив только 60 наборов статистики, то вы выполнили требования к пространству и времени O (1). Это означает, что допускается некоторая итерация, если количество итераций не зависит от количества транзакций.

Отображение каждого часа-минуты-секунды на объект статистики позволяет обрабатывать запрос GET не более чем за 60 итераций независимо от количества полученных транзакций POST.