Rate Limiter Algorithm Correctness Verification

[
  {
    "key": "sms:+15555550101",
    "timestamp": 0,
    "expected": "admit"
  },
  {
    "key": "sms:+15555550101",
    "timestamp": 0,
    "expected": "admit"
  },
  {
    "key": "sms:+15555550101",
    "timestamp": 0,
    "expected": "admit"
  },
  {
    "key": "sms:+15555550101",
    "timestamp": 0,
    "expected": "reject"
  },
  {
    "key": "sms:+15555550101",
    "timestamp": 3,
    "expected": "admit"
  }
]

{
  "capacity": 3,
  "refill_rate": 1
}

class RateLimiter:
    def __init__(self):
        self.capacity = 3
        self.refill_rate = 1
        self.state = {}

    def check(self, key, timestamp):
        st = self.state.get(key)
        if st is None:
            st = {"tokens": self.capacity, "last_time": timestamp}
            self.state[key] = st
        else:
            elapsed = timestamp - st["last_time"]
            st["tokens"] = min(self.capacity, st["tokens"] + elapsed * self.refill_rate)
            st["last_time"] = timestamp
        if st["tokens"] >= 1:
            st["tokens"] -= 1
            return True
        return False

Token bucket: capacity 3 tokens, refilling continuously at 1 token(s) per second since the key's own last request; the bucket starts completely full, and a request is admitted only while at least one whole token is available.