Chương trình kiểm tra số yêu cầu được xử lý với điều kiện cho trước trong Python

Giả sử có danh sách yêu cầu, mỗi phần tử dạng [uid, time_sec] (uid là ID người dùng, time_sec là timestamp). Điều này chỉ ra người dùng uid đã yêu cầu đến trang web tại thời điểm time_sec. Cũng có 2 giá trị u và g: u là số yêu cầu tối đa cho phép trong khung <60 giây cho một uid; g là số yêu cầu tối đa cho phép trong khung <60 giây toàn cục (globally). Muốn xử lý từng yêu cầu và rate limit (giới hạn tốc độ). Nếu có yêu cầu cùng lúc từ nhiều người dùng, yêu cầu uid thấp hơn được xử lý trước, ngược lại yêu cầu bị loại. Cần tìm tổng số yêu cầu xử lý thành công.

Ví dụ: requests = [[0, 1],[1, 2],[1,3]], u = 1, g = 5 → output = 2. User 0 và 1 gửi lúc 1 và 2, nhưng yêu cầu thứ 2 của user 1 không xử lý vì 1 user tối đa 1 request/60s.

Thuật toán:

• last := map rỗng (lưu timestamp gần nhất mỗi user)
• total := deque rỗng (lưu timestamp tất cả request đã xử lý)
• windowtime := 60
• Sắp xếp requests theo time, nếu cùng time thì theo uid
• amount := 0
• Duyệt từng request r:
  • [uid, time] := r
  • Xóa khỏi total các request cũ (> 60s)
  • Xóa khỏi last[uid] các request cũ của user (> 60s)
  • Nếu len(total) < g và len(last[uid]) < u: thêm time vào cả 2, amount += 1
• Trả về amount

Triển khai

from collections import defaultdict, deque

class Solution:
    def solve(self, requests, u, g):
        last = defaultdict(deque)
        total = deque()
        windowtime = 60
        requests.sort(key=lambda x: [x[1], x[0]])
        amount = 0
        for r in requests:
            uid, time = r
            while len(total) > 0 and total[0] + windowtime <= time:
                total.popleft()
            while len(last[uid]) > 0 and last[uid][0] + windowtime <= time:
                last[uid].popleft()
            if len(total) < g and len(last[uid]) < u:
                last[uid].append(time)
                total.append(time)
                amount += 1
        return amount

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

Đầu vào

[[0, 1], [1, 2], [1, 3]], 1, 5

Đầu ra

2

Giải thích thuật toán: Sử dụng sliding window (cửa sổ trượt) 60 giây. deque cho phép O(1) thêm/xóa 2 đầu. defaultdict(deque) tự tạo deque cho user mới. Sắp xếp trước đảm bảo xử lý theo thứ tự thời gian, ưu tiên uid thấp khi cùng thời điểm.