python hashtable, O(1) hit() O(s(300 here)) getHits()


  • 3
    S
    class HitCounter(object):
    
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.dic = collections.defaultdict(int)
    
        def hit(self, timestamp):
            """
            Record a hit.
            @param timestamp - The current timestamp (in seconds granularity).
            :type timestamp: int
            :rtype: void
            """
            self.dic[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
            """
            start = timestamp-300+1 if timestamp > 300 else 0
            summation = 0
            for i in range(start, timestamp+1):
                summation += self.dic[i]
            return summation
    
    
    # Your HitCounter object will be instantiated and called as such:
    # obj = HitCounter()
    # obj.hit(timestamp)
    # param_2 = obj.getHits(timestamp)
    

  • 1
    C

    not a good solution

    The size of your dict increases with time. You need to remove all the keys in dict with key < timestamp - 300


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.