Design Hit Counter

陈年老题，用了一个几近暴力的方式解出来了，但是这个方法明显不好，我们可以用排序哈希表记录timestamp和hit次数，每次发起gethits query时只找附近300秒范围内的hit次数

class HitCounter(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.store = collections.OrderedDict()

    def hit(self, timestamp):
        """
        Record a hit.
        @param timestamp - The current timestamp (in seconds granularity).
        :type timestamp: int
        :rtype: void
        """
        if timestamp in self.store:
            self.store[timestamp] += 1
        else:
            self.store[timestamp] = 1

    def getHits(self, timestamp):
        """
        Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity).
        :type timestamp: int
        :rtype: int
        """
        result = 0
        for key in self.store.keys():
            if timestamp - 300 < key <= timestamp:
                result += self.store[key]
        return result

这么做有两个明显缺点

1. 如果很频繁的在各个时间点都有hit，哈希表的容量会急速膨胀
2. 长时间的运行后积累数据太多，gethits的速度线性下降

我们可以利用队列循环加上惰性删除避免空间膨胀和时间效率下降的问题

class HitCounter(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.circularArray = collections.deque()
        self.result = 0

    def hit(self, timestamp):
        """
        Record a hit.
        @param timestamp - The current timestamp (in seconds granularity).
        :type timestamp: int
        :rtype: void
        """
        if not self.circularArray or timestamp != self.circularArray[-1][0]:
            self.circularArray.append([timestamp, 1])
        else:
            self.circularArray[-1][1] += 1
        self.result += 1

    def getHits(self, timestamp):
        """
        Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity).
        :type timestamp: int
        :rtype: int
        """
        while self.circularArray and self.circularArray[0][0] <= timestamp - 300:
            self.result -= self.circularArray.popleft()[1]
        return self.result