What would be a clean design for an app that is to store transactions and return a overview of the ones received in the last 60 seconds, operating in constant time and memory (O(1))?

The app should expose two endpoints, one of them to POST a new transaction, and the other one to GET the statistics based of the transactions of the last 60 seconds. As said, both need to run in O(1).

A few weeks ago I was given this requirement as part of a code challenge, so let's assume a small app in a single machine. My approach was saving the transactions to both DB and a cache, and having a periodic task, triggered every 1ms, removing entries older than 60s from the cache. Then, fetching the statistics from it was simple. I think this results in O(1) for both endpoints, but there is obviously some serious problem with this approach because I got rejected straight away.

  • 1
    Was the "O(1) time" a prerequisite for the challenge? The reason your solution was rejected was because removing entries older than 60s from the cache involves checking each cache item one at a time. Put simply, if you're doing the same task an arbitrary number of times, it is no longer O(1). – Neil Aug 29 '17 at 12:23
  • It seems that you got one of the two difficult problems in software engineering: Cache Invalidation. – Machado Aug 29 '17 at 13:49
  • @Neil yes it was. You're totally right, but from my understanding the process doing that task an arbitrary number of times is independent from the one saving and fetching the data, which (I think) operates on O(1) – saralor Aug 29 '17 at 13:50

Well, it's fairly simple:

  1. Define the granularity of your reporting.
  2. Get an array for 60 seconds, storing the time and cumulative stats for that quantum.
  3. When you get a report, use the slot (now() / quantum) modulo (60 seconds / quantum):
    1. If the time is not now(), reset the record for now().
    2. Add the reports data.
  4. When you get a request, add all matching entries from the (60 seconds / quantum) ones in the array to get the final stats and return that.

Alternatively, if you get at least one report per quantum (you might be able to insert NULL-reports as needed), or can accept slight variability in processing-time for reports, you can optimize the return of stats:

  1. Define granularity of reporting.
  2. Get an array for 60 seconds plus one, storing cumulative stats for program-lifetime.
  3. When you get a report, set all records since the last you updated equal to the last you worked on. Then add the reports data to the current record.
  4. When you get a request, return the difference between the current record and the one from 60 seconds ago.
|improve this answer|||||
  • Hi, could you explain what you mean by the report/reporting and request ? – Muztaba Hasanat May 6 '18 at 18:25

Maybe this approach could work:

  stats_hashtable[current_time() + 1].calculate_and_append(transaction.data)
  stats_hashtable[current_time() + 2].calculate_and_append(transaction.data)
  //... and so on for each second until the next 60 seconds...
  stats_hashtable[current_time() + 59].calculate_and_append(transaction.data)
  stats_hashtable[current_time() + 60].calculate_and_append(transaction.data)

  overview_stats = stats_hashtable[current_time()]
  return overview_stats

EDIT: my above approach is tightly coupled to the "last 60 seconds" part. I suggest another approach, which vary according to the time interval using the "n" variable (n = number of seconds of the time interval to retrieve transaction consolidated data). This approach uses parallel processing:

n = 60  
repo = hashtable by time or DB with index on the date info

//only executed once, in order to configure the environment
  start n listeners for the PUT endpoint, 
  each endpoint is configured with a different offset, ranging from 0 to n-1

//main endpoint listener, offset = 0
  send broadcast with the same request in order that all other listeners process this same transaction

//additional instances, offset can vary from 1 to n-1
  get offset from configuration (env var, process argument, config file, etc)
  repo[current_time() + offset].calculate_and_append(transaction.data)

  overview_stats = repo[current_time()]
  return overview_stats
|improve this answer|||||

Not the answer you're looking for? Browse other questions tagged or ask your own question.