পাইথনে প্রদত্ত শর্তগুলির সাথে প্রক্রিয়া করা হবে এমন অনুরোধের সংখ্যা পরীক্ষা করার জন্য প্রোগ্রাম

ধরুন আমাদের কাছে অনুরোধের একটি তালিকা রয়েছে যেখানে প্রতিটি তালিকায় [uid, time_sec] (uid হল ব্যবহারকারীর আইডি এবং time_sec হল টাইমস্ট্যাম্প)। এটি সেই ব্যবহারকারীকে নির্দেশ করে যার আইডি ইউআইডি টাইমস্ট্যাম্প time_sec এ একটি ওয়েবসাইটে অনুরোধ করেছে৷ আমাদের কাছে দুটি মানও রয়েছে u এবং g যেখানে u একটি প্রদত্ত uid-এর জন্য যে কোনও <60 সেকেন্ড ফ্রেমে অনুমোদিত সর্বাধিক সংখ্যক অনুরোধগুলিকে নির্দেশ করে এবং g হল বিশ্বব্যাপী যে কোনও <60 সেকেন্ড ফ্রেমে অনুমোদিত সর্বাধিক সংখ্যক অনুরোধ। এখন আমরা যদি প্রতিটি অনুরোধ এক এক করে প্রক্রিয়া করতে চাই এবং তাদের রেট সীমিত করতে চাই। এবং একই সময়ে একাধিক ব্যবহারকারীর অনুরোধ থাকলে, নিম্ন uid সহ অনুরোধগুলি প্রথমে প্রক্রিয়া করা হবে, অন্যথায় সেই অনুরোধটি বাদ দেওয়া হবে। আমাদের মোট অনুরোধের সংখ্যা খুঁজে বের করতে হবে যা সফলভাবে প্রক্রিয়া করা হবে।

সুতরাং, ইনপুট যদি অনুরোধের মত হয় =[[0, 1],[1, 2],[1,3]] u =1 g =5, তাহলে আউটপুট হবে 2, যেহেতু ব্যবহারকারী 0 এবং 1 পাঠাতে পারে সময় 1 এবং 2, কিন্তু ব্যবহারকারী 1 থেকে দ্বিতীয় অনুরোধটি প্রক্রিয়া করা হবে না কারণ একজন ব্যবহারকারী 60 সেকেন্ড ফ্রেমে সর্বাধিক 1টি অনুরোধ পাঠাতে পারেন৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• শেষ :=একটি খালি মানচিত্র
• মোট :=খালি ডবল শেষ সারি
• উইন্ডোটাইম :=60
• সময়ের ভিত্তিতে অনুরোধগুলি সাজান, যদি সেগুলি একই হয় তবে uid-এর উপর ভিত্তি করে সাজান
• অর্থ :=0
• প্রতিটি অনুরোধের জন্য, করুন
  • [uid, time] :=r
  • যখন মোটের আকার> 0 এবং মোট[0] + উইন্ডোটাইম <=সময়, কর
    • মোট বাম আইটেম মুছুন
  • যখন last[uid]> 0 এবং last[uid, 0] + windowtime <=time, do
    • শেষ[uid] থেকে বাম আইটেম মুছুন
  • যদি মোট
  • শেষ[uid] শেষে সময় সন্নিবেশ করুন
  • মোট শেষে সময় সন্নিবেশ করুন
  • অর্থ :=পরিমাণ + 1

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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))

ইনপুট

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

আউটপুট

2