दिए गए शर्तों के साथ प्रोसेस होने वाले रिक्वेस्ट की संख्या जांचने का Python प्रोग्राम

मान लीजिए हमारे पास रिक्वेस्ट की एक सूची है जहां प्रत्येक सूची में [uid, time_sec] जैसे तत्व होते हैं (uid यूजर आईडी है और time_sec टाइमस्टैम्प है)। यह इंगित करता है कि जिस यूजर की आईडी uid है, उसने टाइमस्टैम्प time_sec पर एक वेबसाइट पर रिक्वेस्ट की है। हमारे पास दो मान u और g भी हैं जहां u किसी दिए गए uid के लिए किसी भी < 60 सेकंड फ्रेम में अनुमत अधिकतम रिक्वेस्ट की संख्या को दर्शाता है और g विश्व स्तर पर किसी भी < 60 सेकंड फ्रेम में अनुमत अधिकतम रिक्वेस्ट की संख्या है। अब यदि हम प्रत्येक रिक्वेस्ट को एक-एक करके प्रोसेस करना चाहते हैं और उन्हें रेट लिमिट करना चाहते हैं। और यदि एक ही समय में कई यूजर्स द्वारा रिक्वेस्ट हैं, तो कम uid वाली रिक्वेस्ट पहले प्रोसेस की जाएगी, अन्यथा वह रिक्वेस्ट ड्रॉप हो जाएगी। हमें सफलतापूर्वक प्रोसेस होने वाली रिक्वेस्ट की कुल संख्या ढूंढनी है।

इसलिए, यदि इनपुट इस तरह है requests = [[0, 1],[1, 2],[1,3]] u = 1 g = 5, तो आउटपुट 2 होगा, क्योंकि यूजर 0 और 1 समय 1 और 2 पर भेज सकते हैं, लेकिन यूजर 1 का दूसरा रिक्वेस्ट प्रोसेस नहीं होगा क्योंकि एक यूजर 60 सेकंड फ्रेम में अधिकतम 1 रिक्वेस्ट भेज सकता है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

last := एक खाली मैप
total := खाली डबल-एंडेड क्यू
windowtime := 60
रिक्वेस्ट को समय के आधार पर सॉर्ट करें, यदि वे समान हैं तो uid के आधार पर सॉर्ट करें
amount := 0
प्रत्येक r के लिए requests में, करें
- [uid, time] := r
- जब तक total का आकार > 0 और total[0] + windowtime <= time, करें
  - total का बायां आइटम हटाएं
- जब तक last[uid] का आकार > 0 और last[uid, 0] + windowtime <= time, करें
  - last[uid] से बायां आइटम हटाएं
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