O(1) Hit and O(1) GetHit in Python using Hash


  • 0
    U

    As size of hash and queue will not go beyond 300 (5 minutes) so Loops in both of the following methods will still cost O(1)

    class HitCounter(object):
    
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.hash = {}
            self.queue = []
            
    
        def hit(self, timestamp):
            """
            Record a hit.
            @param timestamp - The current timestamp (in seconds granularity).
            :type timestamp: int
            :rtype: void
            """
            if timestamp not in self.hash:
                self.queue.append(timestamp)
                self.hash[timestamp] = 1
                while timestamp - self.queue[0] >= 300:
                    del self.hash[self.queue[0]]
                    self.queue.pop(0)
            else:
                self.hash[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
            """
            sum = 0
            timestamp -= 299
            for index, element in enumerate(self.queue):
                if element >= timestamp:
                    sum += self.hash[element]
            
            return sum
            
    
    
    # Your HitCounter object will be instantiated and called as such:
    # obj = HitCounter()
    # obj.hit(timestamp)
    # param_2 = obj.getHits(timestamp)
    

Log in to reply
 

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