Design an in-memory rate limiter (token bucket / sliding window)

Problem: Implement an in-memory rate limiter (token bucket / sliding window) Implement a thread-safe in-memory RateLimiter that decides whether a request for a given key should be allowed. Required API allow(key: str, now_ms: int) -> bool Called for each request; return whether it is allowed at time now_ms. One of the following policies (interviewer may choose): Fixed/sliding window: allow at most limit requests per window_ms. Token bucket: capacity capacity=limit, refill at rate=limit/window_ms tokens per ms; each request consumes 1 token. Constraints Support many keys (e.g., by userId or IP). Discuss memory eviction/cleanup for idle keys. If required, use locks (Lock/RLock) or other primitives to ensure thread-safety. Scale assumptions Up to 1e6 calls Up to 1e5 keys Example limit=3, window_ms=1000 At t=0ms, 3 consecutive calls return true At t=10ms, the 4th call returns false After t=1000ms, a new call returns true Implement it and provide tests. Example Input limit 3 window 1000 allow u1 0 allow u1 0 allow u1 0 allow u1 10 Output true true true false