Log Rate Limiter

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.

from collections import deque, defaultdict

class StorefrontRateLimiter:
    def __init__(self, window, limit):
        self.window = window
        self.limit = limit
        # Automatically creates a new deque when a store_id is accessed for the first time
        self.store_history = defaultdict(deque)

    def process_event(self, timestamp, store_id):
        history = self.store_history[store_id]

        # Cleanup: Remove timestamps outside the sliding window
        while history and history[0] <= timestamp - self.window:
            history.popleft()

        # Rate Limit Logic
        if len(history) < self.limit:
            history.append(timestamp)
            return "ALLOW"
        
        return "REJECT"