পাইথনে দেওয়া শর্ত অনুযায়ী প্রসেস হওয়া রিকোয়েস্টের সংখ্যা বের করার প্রোগ্রাম

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

তাই, ইনপুট যদি requests = [[0, 1],[1, 2],[1,3]], u = 1, g = 5 হয়, তবে আউটপুট হবে ২, কারণ ইউজার ০ এবং ১ টাইম ১ ও ২-এ রিকোয়েস্ট করতে পারে, কিন্তু ইউজার ১-এর দ্বিতীয় রিকোয়েস্ট প্রসেস হবে না কারণ এক ইউজার ৬০ সেকেন্ডের ফ্রেমে সর্বোচ্চ ১ রিকোয়েস্ট পাঠাতে পারে।

সমাধানের ধাপগুলো:

last := একটি খালি ম্যাপ
total := খালি ডবল-এন্ডেড কিউ
windowtime := ৬০
রিকোয়েস্টগুলো টাইম অনুযায়ী সর্ট করা, যদি টাইম সমান হয় তবে uid অনুযায়ী সর্ট করা
amount := ০
প্রতিটি r ইন requests এর জন্য, করুন
- [uid, time] := r
- যখন total এর সাইজ > ০ এবং total[0] + windowtime <= time, করুন
  - total-এর বামে থাকা আইটেম ডিলিট করুন
- যখন last[uid] এর সাইজ > ০ এবং last[uid][0] + windowtime <= time, করুন
  - last[uid]-এর বামে থাকা আইটেম ডিলিট করুন
- যদি total এর সাইজ < g এবং last[uid] এর সাইজ < u, তবে
  - time কে last[uid]-এর শেষে ইনসার্ট করুন
  - time কে total-এর শেষে ইনসার্ট করুন
  - amount := amount + 1
amount রিটার্ন করুন

বেটার বুঝতে নিচের বাস্তবায়নটি দেখুন:

উদাহরণ

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