Thiết kế cấu trúc dữ liệu kiểm soát tốc độ yêu cầu (rate limiting) cho người dùng trong Python

Xây dựng một cấu trúc dữ liệu được khởi tạo với thời gian hết hạn expire, hỗ trợ phương thức limit(uid, timestamp) kiểm tra xem yêu cầu của người dùng uid tại thời điểm timestamp có bị từ chối hay không. Yêu cầu bị từ chối (True) chỉ khi người dùng đã có một yêu cầu thành công cách đây ít hơn expire đơn vị thời gian.

Ví dụ: expire = 6, lần lượt gọi limit(0,10), limit(0,16), limit(0,17), limit(1,20) → kết quả: False, False, True, False.

Thuật toán

1. Sử dụng defaultdict(lambda: -1) lưu thời gian yêu cầu thành công gần nhất của mỗi uid (mặc định -1 nghĩa là chưa có yêu cầu).
2. Phương thức limit(uid, timestamp):
   • Lấy last = lastCall[uid].
   • Nếu last == -1 hoặc last + expire <= timestamp: cập nhật lastCall[uid] = timestamp và trả về False (cho phép).
   • Ngược lại: trả về True (từ chối).

Mã Python

from collections import defaultdict

class RateLimit:
    def __init__(self, expire):
        self.expire = expire
        self.lastCall = defaultdict(lambda: -1)

    def limit(self, uid, timestamp):
        last = self.lastCall[uid]
        if last == -1 or last + self.expire <= timestamp:
            self.lastCall[uid] = timestamp
            return False
        return True

expire = 6
obj = RateLimit(expire)
print(obj.limit(0, 10))  # False
print(obj.limit(0, 16))  # False
print(obj.limit(0, 17))  # True
print(obj.limit(1, 20))  # False

Đầu vào / Đầu ra

Input: RateLimit(6) + các lệnh gọi limit

Output: False False True False