Design a VIP-Aware Rate Limiter

Problem Description

In high-volume services, such as tax-filing or payroll systems during peak traffic, rate limiters protect downstream services from being overwhelmed. You are tasked with designing a windowed rate limiter with VIP priority handling.

Design a class VIPRateLimiter that enforces the following requirements:

1. Fixed Window Capacity: Each discrete time window allows up to capacity (default 5) requests to be admitted.
2. Immediate Admission vs. Queuing: If a request arrives and the current window still has available capacity, it is admitted immediately ("ADMITTED"). If the current window is full, the request is placed into a waiting queue ("QUEUED").
3. Priority & Starvation Prevention: At the start of a new window, waiting requests are dequeued and admitted up to the window's capacity:
   • VIP requests (is_vip=True) are prioritized over regular requests (is_vip=False).
   • Within the same priority level, requests must be served in FIFO order.
   • Anti-starvation: To prevent regular requests from starving indefinitely under sustained VIP traffic, at least min_regular_slots (default 1) must be allocated to waiting regular requests if any are present. If no regular requests are waiting, VIPs can use all available capacity (and vice versa).
4. Non-preemption: Once a request is admitted, it cannot be revoked or replaced by a later-arriving VIP request.
5. Idempotency: Submitting a request with an already-seen request_id must not consume extra capacity or duplicate queue entries; it should return the request's existing status ("ADMITTED" or "QUEUED").

Class Interface

class VIPRateLimiter:
    def __init__(self, window_size: int, capacity: int = 5, min_regular_slots: int = 1):
        """
        :param window_size: Duration of each time window in integer seconds/ticks.
        :param capacity: Max requests allowed per window (default 5).
        :param min_regular_slots: Guaranteed slots for regular users per window if waiting.
        """
        pass

    def submit_request(self, request_id: str, is_vip: bool, timestamp: int) -> str:
        """
        Processes an incoming request at the given timestamp.
        Advances windows if timestamp >= current_window_end.
        Returns "ADMITTED" if the request was admitted in the current window,
        or "QUEUED" if placed in (or already in) the waiting queue.
        """
        pass

    def get_admitted(self) -> list[str]:
        """
        Returns list of all admitted request_ids in the order they were admitted.
        """
        pass

Example

limiter = VIPRateLimiter(window_size=10, capacity=5, min_regular_slots=1)

# Window 0 [0, 10)
for i in range(5):
    limiter.submit_request(f"reg_{i}", is_vip=False, timestamp=1)  # All 5 return "ADMITTED"

# Capacity full for window 0; subsequent requests are queued
limiter.submit_request("reg_5", is_vip=False, timestamp=2)         # Returns "QUEUED"
limiter.submit_request("vip_1", is_vip=True, timestamp=3)          # Returns "QUEUED"
limiter.submit_request("vip_2", is_vip=True, timestamp=4)          # Returns "QUEUED"

# Idempotency check
limiter.submit_request("vip_1", is_vip=True, timestamp=5)          # Returns "QUEUED" (already queued)

# Window 1 begins at timestamp 10: capacity resets to 5
# Queued requests are drained: vip_1, vip_2, and reg_5 are admitted.
limiter.submit_request("reg_6", is_vip=False, timestamp=10)       # Triggers window roll; returns "ADMITTED"

Constraints

• 1 <= capacity <= 1000
• 1 <= window_size <= 86400
• 0 <= min_regular_slots < capacity
• timestamp values across consecutive calls are non-decreasing.