Stock statistics calculation with O(1) time and space complexity

user_9088011 0
Viewed 388

I have to design a rest API in Java which :-

  1. Accepts a POST request with the below json :-

    { "instrument": "ABC", "price": "200.90", "timestamp" : "2018-09-25T12:00:00" }

these records would be saved in an in memory collection and not any kind of database.

  1. There would be a GET API which returns the statistics of the specific instrument records received in the last 60 seconds. The GET request would be :- /statistics/{instrumentName} Ex :- /statistics/ABC . The response looks as mentioned below :-

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

  2. There would be another GET request /statistics which returns the statistics of all the instruments that was received in the last 60 seconds ( Not specific to particular instrument like #2 )

What makes this algorithm complex to implement is that the GET call should be executed - O(1) time and space complexity.

The approach which I have thought for 3# is to have a collection which will have 60 buckets ( since we have to calculate for past 60 secs so sampling per 1 sec). Every time the transaction comes in it will go to specific bucket depending on the key i.e. hour-min-sec ( it would be a map with this key and the statistics for that sec ) .

But what I am not able to understand is how to address the problem 2# where we have to get the statistics of specific instrument /statistics/ABC for last 60 sec in O(1) time and space complexity.

What could be the best strategy to clean up records which are older than 60 secs?

Any help with the algorithm will be appreciated.

data-structures time-complexity multithreading algorithm java
1 Answers

Store the data in a Map<String, Instrument>, and have the class look like this:

class Instrument {
    private String name;
    private SortedMap<LocalDateTime, BigDecimal> prices;
    private BigDecimal minPrice;
    private BigDecimal maxPrice;
    private BigDecimal sumPrice;

    // Internal helper method
    private void cleanup() {
        LocalDateTime expireTime = LocalDateTime.now().minusSeconds(60);
        Map<LocalDateTime, BigDecimal> expiredPrices = this.prices.headMap(expireTime);
        for (BigDecimal expiredPrice : expiredPrices.values()) {
            if (this.minPrice.compareTo(expiredPrice) == 0)
                this.minPrice = null;
            if (this.maxPrice.compareTo(expiredPrice) == 0)
                this.maxPrice = null;
            this.sumPrice = this.sumPrice.subtract(expiredPrice);
        }
        expiredPrices.clear(); // Removes expired prices from this.prices
        if (this.minPrice == null && ! this.prices.isEmpty())
            this.minPrice = this.prices.values().stream().min(Comparator.naturalOrder()).get();
        if (this.maxPrice == null && ! this.prices.isEmpty())
            this.maxPrice = this.prices.values().stream().max(Comparator.naturalOrder()).get();
    }

    // other code
}

All the public methods of Instrument must be synchronized and must start with a call to cleanup(), since time has elapsed since any previous call. The addPrice(LocalDateTime, BigDecimal) method must of course update the 3 statistics fields.

To ensure statistics are in sync, it would be appropriate to have a Statistics class that can be used as return value, so all 4 main statistics values (incl. count obtained from this.prices.size()) represent the same set of prices.

user_52211490
Related