Implement a thread-safe rate limiter

Design and implement a per-user API rate limiter.

Requirements:

• Method: boolean allow(String userId, long nowMillis) returns whether the request is allowed at time nowMillis.
• Policy: allow at most N requests per W milliseconds per user.
• Choose any standard algorithm (e.g., fixed window, sliding window, token bucket).

Follow-ups:

• How do you make it safe under concurrency (multiple threads calling allow for the same userId)?
• Discuss tradeoffs between using locks vs lock-free/low-lock approaches (e.g., ConcurrentHashMap, atomics) and performance implications.

Per-User Sliding-Window Rate Limiter

For each (user,time) request, allow at most limit requests per user in the previous window_ms interval.

Constraints

• requests are processed in arrival order

Examples

Example 1

Input: ([('u', 0), ('u', 10), ('u', 20)], 2, 100)
Output: [True, True, False]

Explanation: Third rejected.

Example 2

Input: ([('u', 0), ('v', 1), ('u', 100)], 2, 100)
Output: [True, True, True]

Explanation: Boundary evicts old request.

Hints

1. Use one deque of accepted timestamps per user.