समस्या
observer पैटर्न ऑब्जेक्ट्स को किसी सब्जेक्ट को सब्सक्राइब करने और कुछ होने पर सूचना पाने देता है। यहाँ लोग टॉपिक सब्सक्राइब करते हैं और हर प्रकाशित इवेंट उसके टॉपिक के सभी सब्सक्राइबरों तक जाता है।
हर सब्सक्रिप्शन <person> <topic> के रूप में है। दोहराए गए सब्सक्रिप्शन का कोई अतिरिक्त असर नहीं होता। फिर events का हर इवेंट एक टॉपिक का नाम है: उस टॉपिक के हर सब्सक्राइबर को एक सूचना मिलती है। जिन टॉपिक को कोई फ़ॉलो नहीं करता, उनके इवेंट छोड़ दिए जाते हैं।
event_subscribers(subscriptions, events) लिखें।
इनपुट
subscriptions: "<person> <topic>" स्ट्रिंग (नामों में स्पेस नहीं होता)।
events: टॉपिक के नाम, प्रकाशन के क्रम में।
आउटपुट
कम से कम एक सब्सक्रिप्शन वाले हर व्यक्ति के लिए "<person>:<count>" लौटाएँ, नाम के अनुसार क्रमबद्ध (ordinal कैरेक्टर क्रम)।
सीमाएँ
1 ≤ सब्सक्रिप्शन की संख्या ≤ 10,000
0 ≤ इवेंट की संख्या ≤ 100,000
उदाहरण
इनपुट:
subscriptions = ["bob sports", "alice news", "alice sports"]
events = ["news", "sports", "weather"]
अपेक्षित आउटपुट:
expected = ["alice:2", "bob:1"]
इनपुट:
std::vector<std::string> subscriptions = {"bob sports", "alice news", "alice sports"};
std::vector<std::string> events = {"news", "sports", "weather"};
अपेक्षित आउटपुट:
std::vector<std::string> expected = {"alice:2", "bob:1"};
इनपुट:
string[] subscriptions = new string[] {"bob sports", "alice news", "alice sports"};
string[] events = new string[] {"news", "sports", "weather"};
अपेक्षित आउटपुट:
string[] expected = new string[] {"alice:2", "bob:1"};
व्याख्या
alice news और sports फ़ॉलो करती है, इसलिए उसे दोनों इवेंट मिलते हैं; bob को सिर्फ़ sports मिलता है; weather कोई फ़ॉलो नहीं करता: ["alice:2", "bob:1"]।
इनपुट:
subscriptions = ["zoe tech", "zoe tech"]
events = []
अपेक्षित आउटपुट:
expected = ["zoe:0"]
इनपुट:
std::vector<std::string> subscriptions = {"zoe tech", "zoe tech"};
std::vector<std::string> events = {};
अपेक्षित आउटपुट:
std::vector<std::string> expected = {"zoe:0"};
इनपुट:
string[] subscriptions = new string[] {"zoe tech", "zoe tech"};
string[] events = new string[] {};
अपेक्षित आउटपुट:
string[] expected = new string[] {"zoe:0"};
व्याख्या
दोहराया गया सब्सक्रिप्शन एक बार गिना जाता है और कोई इवेंट प्रकाशित नहीं हुआ: ["zoe:0"]।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
सब्सक्राइबरों को टॉपिक के हिसाब से समूह में रखें ताकि हर इवेंट जल्दी सही लोगों तक पहुँचे।
संकेत 2
हर टॉपिक के लिए set रखें ताकि दोहराया सब्सक्रिप्शन एक ही बार गिना जाए।
संकेत 3
जिसने भी सब्सक्राइब किया वह नतीजे में होगा, भले उसे 0 सूचनाएँ मिली हों।
अपेक्षित जटिलता
समय O(सब्सक्रिप्शन + इवेंट × हर टॉपिक के सब्सक्राइबर), अतिरिक्त स्थान O(सब्सक्रिप्शन)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।