Rate Limiter

You are given an array of timestamps representing API requests and need to implement a rate limiter that allows at most limit requests within a windowSize time period. The rate limiter should use a sliding window approach.

Function Signature

function rateLimiter(requests, limit, windowSize) {
  // Your code here
}

Parameters

• requests: An array of integers representing timestamps of API requests
• limit: The maximum number of requests allowed within the window
• windowSize: The time window size in seconds

Return Value

Return an array of indices representing which requests should be allowed (0-indexed).

Examples

Input: requests = [1, 2, 3, 4, 5], limit = 3, windowSize = 2
Output: [0, 1, 2]
Explanation: 
- At timestamp 1: Allow request 0
- At timestamp 2: Allow request 1  
- At timestamp 3: Allow request 2
- At timestamp 4: Request 0 expires (1 + 2 = 3), allow request 3
- At timestamp 5: Request 1 expires (2 + 2 = 4), allow request 4

Input: requests = [1, 2, 3, 4, 5], limit = 2, windowSize = 3
Output: [0, 1]
Explanation:
- At timestamp 1: Allow request 0
- At timestamp 2: Allow request 1
- At timestamp 3: No requests expire yet, reject request 2
- At timestamp 4: Request 0 expires (1 + 3 = 4), allow request 3
- At timestamp 5: Request 1 expires (2 + 3 = 5), allow request 4

Constraints

• 0 ≤ requests.length ≤ 1000
• 1 ≤ limit ≤ 100
• 1 ≤ windowSize ≤ 1000
• All timestamps are non-negative integers
• Timestamps are in ascending order

Algorithm

1. Use a queue to maintain the timestamps of allowed requests.
2. For each request timestamp:
   • Remove expired timestamps from the queue (timestamps ≤ currentTime - windowSize).
   • If the queue length is less than the limit, allow the request.
   • Add the current timestamp to the queue if allowed.

Test Cases

• Empty requests array
• Single request
• Multiple requests within a window
• Requests spanning multiple windows
• Edge cases with minimum/maximum values