Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình kiểm tra số lượng yêu cầu sẽ được xử lý với các điều kiện nhất định trong python

Giả sử chúng ta có một danh sách các yêu cầu trong đó mỗi danh sách chứa các phần tử như [uid, time_sec] (uid là id người dùng và time_sec là dấu thời gian). Điều này cho biết người dùng có id là uid đã yêu cầu một trang web tại dấu thời gian time_sec. Chúng tôi cũng có hai giá trị u và g trong đó u biểu thị số lượng yêu cầu tối đa được phép trong bất kỳ khung hình <60 giây nào đối với một uid nhất định và g là số lượng yêu cầu tối đa được phép trong bất kỳ khung hình <60 giây nào trên toàn cầu. Bây giờ nếu chúng ta muốn xử lý từng yêu cầu một và giới hạn tỷ lệ chúng. Và nếu có nhiều yêu cầu cùng lúc của nhiều người dùng, các yêu cầu có uid thấp hơn sẽ được xử lý trước, nếu không, yêu cầu đó sẽ bị loại bỏ. Chúng tôi phải tìm tổng số yêu cầu sẽ được xử lý thành công.

Vì vậy, nếu đầu vào giống như các yêu cầu =[[0, 1], [1, 2], [1,3]] u =1 g =5, thì đầu ra sẽ là 2, vì người dùng 0 và 1 có thể gửi lúc lần 1 và lần 2, nhưng yêu cầu thứ hai từ người dùng 1 sẽ không được xử lý vì một người dùng có thể gửi nhiều nhất 1 yêu cầu trong khung 60 giây.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • cuối cùng:=một bản đồ trống
  • tổng số:=hàng đợi kết thúc kép trống
  • thời gian cửa sổ:=60
  • sắp xếp các yêu cầu dựa trên thời gian, nếu chúng giống nhau thì sắp xếp dựa trên uid
  • số tiền:=0
  • đối với mỗi r trong các yêu cầu, hãy thực hiện
    • [uid, time]:=r
    • trong khi kích thước của tổng số> 0 và tổng số [0] + thời gian cửa sổ <=thời gian, thực hiện
      • xóa mục bên trái trong tổng số
    • while kích thước của [uid]> 0 cuối cùng và [uid, 0] + windowtime <=time vừa qua, thực hiện
      • xóa mục bên trái khỏi [uid] cuối cùng
    • nếu kích thước của tổng số
    • chèn thời gian vào cuối [uid] cuối cùng
    • chèn thời gian vào cuối tổng số
    • số tiền:=số tiền + 1
  • số tiền trả lại

    • Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

    Ví dụ 

    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