Design Hit Counter

题目

Design a hit counter which counts the number of hits received in the past 5 minutes.

Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (ie, the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1.

It is possible that several hits arrive roughly at the same time.

Example:

HitCounter counter = new HitCounter();

// hit at timestamp 1.
counter.hit(1);

// hit at timestamp 2.
counter.hit(2);

// hit at timestamp 3.
counter.hit(3);

// get hits at timestamp 4, should return 3.
counter.getHits(4);

// hit at timestamp 300.
counter.hit(300);

// get hits at timestamp 300, should return 4.
counter.getHits(300);

// get hits at timestamp 301, should return 3.
counter.getHits(301);

Follow up:
What if the number of hits per second could be very large? Does your design scale?

思路分析

本题可以使用dictionary来实现，也就是说把每一个timestamp作为key，这个timestamp来的hit数作为value，这样就可以得到5分钟内的hit数。但是这样做的缺点就是dictionary 记录了所有的timestamp，而题目只是要求5分钟内的结果，所以只需要存储5分钟的记录就行，当记录超过5分钟的时候，就可以把5分钟之前的数据删除。通过分析，我们可以用queue的数据结构来实现，queue的好处就是FIFO先到先出。同时呢我们可以把每一个timestamp的数放在queue中，也就是说每一个queue的item是一个list，此处不能是tuple，因为tuple中的item的值是不可以改变的，而list中的item值是可以改变的。list中一个element是timestamp，另外一个element就是这个timestamp的个数。queue与dictionary最大的不同是queue靠index来查找，而dictionary用key来查找

class HitCounter(object):

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

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

        self.counter += 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.queue and self.queue[0][0] <= timestamp-300:
            self.counter -= self.queue.popleft()[1]
        return self.counter