*359. Logger Rate Limiter

https://leetcode.com/problems/logger-rate-limiter/description/

solution

# hashmap 做一个类似 inverted index 功能

class Logger:
    def __init__(self):
        self.messageQueue = collections.deque()
        self.messageSet = set()
    
    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        while self.messageQueue:
            headTimestamp, headMessage = self.messageQueue[0]
            if timestamp < headTimestamp + 10:
                break
            # 大于10秒的去掉
            self.messageQueue.popleft()
            self.messageSet.remove(headMessage)
        
        if message in self.messageSet:
            return False
        self.messageQueue.append((timestamp, message))
        self.messageSet.add(message)
        return True

时间复杂度：O(n) 空间复杂度：O(n)

follow up

给定一个公共API，限制每个用户每秒只能调用1000次，如何实现？

• counter

• Token Bucket

• Leak Bucket

• https://zhuanlan.zhihu.com/p/20872901