Giới hạn tốc độ yêu cầu (Rate Limiter Sliding Window)

Rate Limiting là một cơ chế phòng thủ tối quan trọng trong các hệ thống Web và API để chống lại các cuộc tấn công Brute-force hoặc DDoS và bảo vệ tài nguyên máy chủ.

Cho một mảng các thời điểm gửi yêu cầu timestamps (đơn vị: giây, đã được sắp xếp tăng dần), số lượng yêu cầu tối đa cho phép maxRequests, và cửa sổ thời gian windowSeconds.

Hãy viết hàm xác định xem mỗi yêu cầu có được chấp thuận hay bị từ chối theo nguyên tắc Cửa sổ trượt (Sliding Window Log):

• Một yêu cầu tại thời điểm t chỉ được chấp thuận (true) nếu trong khoảng thời gian [t - windowSeconds + 1, t], số lượng các yêu cầu đã được chấp thuận trước đó nhỏ hơn maxRequests.
• Nếu đạt hoặc vượt quá maxRequests, yêu cầu bị từ chối (false) và không được tính vào danh sách các yêu cầu đã chấp thuận.

Ví dụ 1:

Input:
timestamps = [1, 1, 2, 3, 5, 8]
maxRequests = 3
windowSeconds = 3
Output: [true, true, true, false, true, true]
Giải thích:
- t=1: 1 req -> true
- t=1: 2 req -> true
- t=2: trong [0..2] có 3 req -> true
- t=3: trong [1..3] đã có 3 req (t=1, 1, 2) -> false (bị từ chối)
- t=5: trong [3..5] chỉ có t=5 (do t=3 bị từ chối) -> true
- t=8: trong [6..8] chỉ có 1 req -> true

Định Dạng Đầu Vào (Input)

Định Dạng Đầu Ra (Output)

Ràng Buộc (Constraints)

• 1 <= timestamps.length <= 10^5
• 1 <= maxRequests <= 1000
• 1 <= windowSeconds <= 3600

Ví Dụ Kiểm Thử Mẫu

[1, 1, 2, 3, 5, 8]
3
3

[true, true, true, false, true, true]

[1, 2, 3, 4]
2
5

[true, true, false, false]