Problem: Storefront Log Rate Limiter

You are given a stream of log events. Each event contains at least:

• timestamp: arrival time (assume integer seconds or milliseconds)
• store_id: storefront identifier
• (optional) event_type / message

Implement a rate limiter that decides whether each log should be accepted and written downstream.

Requirements

1. Rate limit independently per store_id.
2. In any sliding time window of length window, allow at most limit logs per store_id; extra logs must be rejected.
3. Output an ALLOW/REJECT decision for every input event.

I/O (conceptual)

• Input: events (timestamp, store_id) in arrival order, plus window and limit.
• Output: ALLOW or REJECT per event.

Example

window = 10s, limit = 3

1. (1, A) -> ALLOW
2. (2, A) -> ALLOW
3. (3, A) -> ALLOW
4. (4, A) -> REJECT
5. (12, A) -> ALLOW

Constraints

• High-throughput stream processing.
• Aim for amortized ~O(1) per event.

 1 from collections import deque, defaultdict
 2 
 3 class StorefrontRateLimiter:
 4     def __init__(self, window, limit):
 5         self.window = window
 6         self.limit = limit
 7         # Automatically creates a new deque when a store_id is accessed for the first time
 8         self.store_history = defaultdict(deque)
 9 
10     def process_event(self, timestamp, store_id):
11         history = self.store_history[store_id]
12 
13         # Cleanup: Remove timestamps outside the sliding window
14         while history and history[0] <= timestamp - self.window:
15             history.popleft()
16 
17         # Rate Limit Logic
18         if len(history) < self.limit:
19             history.append(timestamp)
20             return "ALLOW"
21         
22         return "REJECT"