Live Statistics In O(1) space and time

user_9306454 0
Viewed 628

I recently submitted a code challenge for a job position. It was supposed to post Transactions on a REST service as follows:

POST /transactions

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

and GET /statistics with a response as follows:

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

The constrains are what make the solution hard, and they are:

1.- It should not use SQL to store the transactions, so it's basically an in memory transactions cache.

2.- It should always perform in O(1) for both time and aux space

3.- Scheduled cleanup is not enough.

4.- Only Transactions committed in the last 60 seconds from when the request is made should be taken into consideration for the statistics.

My first approach was to generate a wrapper for the statistics with the current server minute as an ID an every transaction or query updated the cache, but this fails cause it only process current minute transactions, dismissing transactions within 60 secs but from previous minute.

All other approaches I came up with required some sort of iteration which violated the O(1) constraint in time, at the end I got rejected, but I want to learn from the community what would've been the best approach.

Cheers

statistics caching rest algorithm
1 Answers

Seems like the time stamps only have 1 second resolution, so you can keep statistics for each one second interval. When a GET request is processed, you need to combine the statistics from 60 intervals.

But O(60) and O(1) are the same thing as far as big-O is concerned. In other words, if you processed 10 million POST transactions while keeping only 60 sets of statistics, then you've met the O(1) space and time requirements. Which is to say that some iteration is allowed, as long as the number of iterations doesn't depend on the number of transactions.

Mapping each hour-minute-second to a statistics object allows the GET request to be processed with at most 60 iterations, regardless of the number of POST transactions that were received.

user_33861090
Related