โปรแกรมนับจำนวน Request ที่ประมวลผลได้ภายใต้เงื่อนไข Rate Limiting ใน Python

ปัญหา: กำหนด Request Logs = `[[uid, time_sec], ...]` ต้องประมวลผล Request ตามเงื่อนไข Rate Limiting:

• u: Max Requests ต่อ User ในช่วง 60 วินาที (Sliding Window)
• g: Max Requests ทั้งระบบ (Global) ในช่วง 60 วินาที
• Request ที่มีเวลาเท่ากัน: เรียงตาม UID น้อยไปมาก (Priority ให้ UID ต่ำ)
• Request ที่เกิน Limit จะถูก Drop

อัลกอริทึม (Sliding Window + Two Queues)

1. เรียง Requests ตาม Time แล้ว UID
2. Maintain 2 Queues:
   • total: Deque ของ Timestamps ทั้งหมด (Global Window)
   • last[uid]: Dict of Deques - Timestamps ต่อ User
3. สำหรับแต่ละ Request:
   • ลบ Timestamps เก่าที่เกิน 60 วินาทีออกจากทั้ง 2 Queues
   • ถ้า `len(total) < g` และ `len(last[uid]) < u` → Accept, เพิ่ม Timestamp ในทั้ง 2 Queues
   • Else → Drop

การติดตั้ง

from collections import defaultdict, deque

class Solution:
    def solve(self, requests, u, g):
        last = defaultdict(deque)   # uid -> deque of timestamps
        total = deque()             # Global timestamps
        window = 60
        
        # Sort by time, then uid
        requests.sort(key=lambda x: (x[1], x[0]))
        
        count = 0
        for uid, time in requests:
            # Clean expired global timestamps
            while total and total[0] + window <= time:
                total.popleft()
            
            # Clean expired user timestamps
            while last[uid] and last[uid][0] + window <= time:
                last[uid].popleft()
            
            # Check limits
            if len(total) < g and len(last[uid]) < u:
                last[uid].append(time)
                total.append(time)
                count += 1
        
        return count

# Test
ob = Solution()
requests = [[0, 1], [1, 2], [1, 3]]
u = 1
g = 5
print(ob.solve(requests, u, g))  # Output: 2

คำอธิบาย

• Sliding Window: ใช้ Deque เก็บ Timestamps ลบค่าที่เก่ากว่า `current_time - 60` ทิ้งไป

• Per-User Limit: `last[uid]` ติดตาม Requests ของแต่ละ User

• Global Limit: `total` ติดตาม Requests ทั้งระบบ

• Sorting: เรียง Time ก่อน แล้ว UID เพื่อ Priority

• Complexity: O(N log N) จาก Sort + O(N) Processing (แต่ละ Timestamp เข้า/ออก Deque สูงสุด 1 ครั้ง)

ตัวอย่างการทำงาน

Requests: [[0,1], [1,2], [1,3]]
u=1, g=5, window=60

Step 1: [0,1] - total=[], last[0]=[] → Accept (total=[1], last[0]=[1], count=1)
Step 2: [1,2] - total=[1], last[1]=[] → Accept (total=[1,2], last[1]=[2], count=2)
Step 3: [1,3] - total=[1,2], last[1]=[2] → last[1] มี 1 อยู่แล้ว (u=1) → REJECT
Result: 2

ขยายความสามารถ

# Variable Window Size
def solve(self, requests, u, g, window=60):
    ...

# Return Accepted Requests แทน Count
def solve(self, requests, u, g):
    accepted = []
    ...
    if ...:
        accepted.append([uid, time])
    return accepted

# Multiple Time Windows (e.g., 1min, 1hr, 1day)
# ต้องใช้ Multiple Deques ต่อ User/Global

ประยุกต์ใช้: API Rate Limiting, DDoS Protection, Resource Quota Management