प्रॉम्प्ट और संदर्भ
आपको n उपयोगकर्ता और q टाइमस्टैम्प्ड ऑपरेशन्स प्राप्त होते हैं। add id u v एक ID के साथ एक अनडायरेक्टेड रिलेशनशिप जोड़ता है, remove id इसे हटाता है, और ask u v पूछता है कि क्या उस समय दो उपयोगकर्ता जुड़े हुए हैं। प्रत्येक रिलेशनशिप को अधिकतम एक बार जोड़ा और हटाया जाता है, और उत्तर उत्पन्न होने से पहले सभी ऑपरेशन्स ज्ञात होते हैं।
प्रत्येक ask के लिए एक बूलियन उत्तर लौटाएं। समझाएं कि सामान्य डिसजॉइंट-सेट यूनियन (DSU) सुरक्षित रूप से विलोपन को प्रोसेस क्यों नहीं कर सकता है, रिलेशनशिप के लाइफटाइम को टाइमलाइन पर कैसे मैप किया जाए, स्थिति को कैसे पुनर्स्थापित किया जाए, और कौन सी सीमाएं और जटिलता मायने रखती हैं। लक्ष्य ऑफलाइन डायनेमिक कनेक्टिविटी है, न कि मनमाना ऑनलाइन अपडेट।
इंटरव्यूअर क्या जांच रहा है
- क्या आप पहचानते हैं कि एज गायब होने पर मोनोटोनिक यूनियन-फाइंड इनवेरिएंट टूट जाता है।
- क्या आप प्रत्येक एज को अर्ध-खुले (half-open) लाइफटाइम अंतराल
[add time, remove time)के रूप में दर्शा सकते हैं। - क्या आप एक अंतराल को
O(log q)सेगमेंट-ट्री नोड्स में विघटित कर सकते हैं। - क्या आप पाथ कम्प्रेशन के बिना और यूनियन बाय साइज के साथ रोलबैक DSU लागू कर सकते हैं।
- क्या आप स्नैपशॉट, रिकर्शन रिटर्न और क्वेरी की शुद्धता को जोड़ सकते हैं।
पहले स्पष्ट करने योग्य प्रश्न
- क्या सभी ऑपरेशन्स पहले से ज्ञात हैं? यदि उत्तर ऑनलाइन देने होंगे, तो टाइमलाइन दृष्टिकोण लागू नहीं होगा।
- क्या प्रत्येक रिलेशनशिप की एक विशिष्ट ID है? इसके बिना, डुप्लिकेट एज का विलोपन अस्पष्ट होता है।
- क्या ग्राफ़ अनडायरेक्टेड है? डायरेक्टेड ग्राफ़ को एक अलग रीचेबिलिटी संरचना की आवश्यकता होती है।
- क्या हटाने के बाद किसी ID को दोबारा जोड़ा जा सकता है? यदि हां, तो प्रत्येक लाइफटाइम को अपने स्वयं के अंतराल की आवश्यकता होगी।
- क्या क्वेरी केवल कनेक्टिविटी के लिए हैं, या कॉम्पोनेंट साइज, सबसे छोटे रास्ते (shortest paths), या वास्तविक रास्तों के लिए भी हैं?
30-सेकंड उत्तर ढांचा
सामान्य DSU कॉम्पोनेंट्स को मर्ज कर सकता है लेकिन यह जाने बिना कि किस संरचना को विभाजित किया जाना चाहिए, एज को हटा नहीं सकता है। मैं ऑपरेशन्स को स्कैन करूंगा, प्रत्येक एज के लिए [add, remove) बनाऊंगा, और बिना विलोपन वाली एज को q तक विस्तारित करूंगा। मैं प्रत्येक अंतराल को समय के आधार पर एक सेगमेंट ट्री में रखूंगा। DFS के दौरान, नोड की एजेस लागू करें, पत्तियों (leaves) पर प्रश्नों के उत्तर दें, और नोड से बाहर निकलते समय एंट्री स्नैपशॉट पर रोलबैक करें। रोलबैक DSU पाथ कम्प्रेशन से बचता है और यूनियन बाय साइज का उपयोग करता है, इसलिए प्रत्येक परिवर्तन रिकॉर्ड किया जाता है और कुल लागत O(n + q log q) स्पेस के साथ O(q log q log n) होती है।
चरण-दर-चरण गहन विश्लेषण
चरण 1: पहचानें कि सामान्य DSU क्यों विफल होता है
सामान्य DSU अब तक देखे गए सभी मर्जों का परिणाम संग्रहीत करता है। एक एज को हटाने से कोई कॉम्पोनेंट दूसरी एज के माध्यम से जुड़ा रह सकता है या किसी ट्री को विभाजित करने की आवश्यकता हो सकती है; केवल पैरेंट पॉइंटर्स प्रभावित कट को प्रकट नहीं करते हैं। कोई सुरक्षित "रिवर्स यूनियन" नहीं है।
चरण 2: एज लाइफटाइम अंतराल बनाएं
प्रत्येक add समय रिकॉर्ड करें। जब इसका remove दिखाई दे, तो [add, remove) को बंद करें; अर्ध-खुला रूप एज को हटाने वाले टाइमस्टैम्प से बाहर रखता है। अंत में भी खुला रहने वाला एज [add, q) बन जाता है।
चरण 3: सेगमेंट ट्री के साथ अंतरालों को कवर करें
अंतराल को उन सेगमेंट-ट्री नोड्स में स्टोर करें जो इसे पूरी तरह से कवर करते हैं। एक अंतराल अधिकतम O(log q) नोड्स घेरता है। किसी नोड पर संग्रहीत प्रत्येक एज नोड की संपूर्ण समय सीमा के लिए मान्य होती है, इसलिए इसे प्रत्येक लीफ के बजाय केवल एक बार मर्ज किया जाता है।
चरण 4: रोलबैक DSU डिज़ाइन करें
parent और size बनाए रखें। find बिना पाथ कम्प्रेशन के पैरेंट्स का अनुसरण करता है। union छोटे रूट को बड़े रूट से जोड़ता है और बदले हुए चाइल्ड, रूट और पुराने आकार को इतिहास स्टैक (history stack) पर पुश करता है। यूनियन बाय साइज ट्री की ऊंचाई को O(log n) तक सीमित करता है।
चरण 5: स्नैपशॉट और पुनर्स्थापन के साथ DFS
एंट्री पर इतिहास की लंबाई सेव करें, नोड की एजेस लागू करें, और एक लीफ पर ask का उत्तर दें। दोनों संतानों (children) के समाप्त होने के बाद, सेव की गई लंबाई तक वापस पॉप करें। पैरेंट एजेस अगले चाइल्ड के लिए सक्रिय रहती हैं, जबकि केवल चाइल्ड-विशिष्ट एजेस सिबलिंग्स में लीक नहीं हो सकती हैं।
चरण 6: कार्यान्वयन का स्वरूप
कार्यान्वयन के चार चरण हैं: अर्ध-खुले अंतराल बनाना, प्रत्येक अंतराल को टाइम सेगमेंट ट्री में जोड़ना, रोलबैक DSU के साथ ट्रैवर्सल करना, और लीव्स पर उत्तर देना। महत्वपूर्ण विवरण हैं: कोई पाथ कम्प्रेशन नहीं, पुराने कॉम्पोनेंट साइज को रिकॉर्ड करना, और बिल्कुल स्नैपशॉट पर पुनर्स्थापित करना।
चरण 7: इनवेरिएंट और जटिलता को साबित करें
सेगमेंट-ट्री नोड में प्रवेश करने पर, DSU में ठीक वही एजेस होती हैं जो उस नोड की सीमा के दौरान सक्रिय होती हैं और साथ ही पूर्वजों द्वारा लागू की गई एजेस होती हैं। चाइल्ड एजेस केवल चाइल्ड सबट्री में मौजूद होती हैं और लौटने पर हटा दी जाती हैं, इसलिए एक लीफ बिल्कुल सक्रिय-एज यूनियन को देखती है। प्रत्येक एज को O(log q) नोड्स में संग्रहीत किया जाता है और यूनियन बाय साइज के साथ प्रत्येक यूनियन की लागत O(log n) होती है, जिससे O(q log q log n) समय और O(n + q log q) स्टोरेज मिलता है।
चरण 8: विकल्पों और विफलता के मामलों की तुलना करें
यदि केवल एजेस जुड़ती हैं और कनेक्टिविटी पर सवाल उठाया जाता है, तो सामान्य DSU लगभग-स्थिर परिशोधित (amortized) ऑपरेशन्स के साथ सरल है। वास्तविक ऑनलाइन विलोपन के लिए एक डायनेमिक-कनेक्टिविटी संरचना की आवश्यकता होती है; टाइमलाइन ट्री भविष्य के किसी अज्ञात विलोपन को नहीं जान सकता है। DSU सबसे छोटे रास्तों का उत्तर भी नहीं दे सकता है, जिसके लिए BFS, Dijkstra, या किसी अन्य पाथ संरचना की आवश्यकता होती है।
उच्च-गुणवत्ता वाला नमूना उत्तर
मैं पहले पुष्टि करूंगा कि प्रत्येक ऑपरेशन ज्ञात है और प्रत्येक रिलेशनशिप की एक स्थिर ID है। सामान्य DSU केवल मर्ज करता है, और विलोपन इसके कॉम्पोनेंट इनवेरिएंट को तोड़ता है, इसलिए मैं ऑपरेशन्स को अर्ध-खुले एज लाइफटाइम में स्कैन करूंगा और अभी भी खुली एजेस को अंत तक विस्तारित करूंगा। मैं उन अंतरालों को समय के आधार पर सेगमेंट ट्री में रखूंगा, DFS के दौरान नोड एजेस को मर्ज करूंगा, लीव्स पर कनेक्टिविटी का उत्तर दूंगा, और लौटने पर एंट्री हिस्ट्री की लंबाई पर रोलबैक करूंगा। रोलबैक DSU पाथ कम्प्रेशन से बचता है, यूनियन बाय साइज का उपयोग करता है, और पैरेंट और साइज परिवर्तनों को रिकॉर्ड करता है, जिससे ट्री की ऊंचाई O(log n) मिलती है। प्रत्येक एज O(log q) नोड्स में दिखाई देती है, इसलिए समय O(q log q log n) और स्पेस O(n + q log q) है। केवल जोड़ने के लिए मैं सामान्य DSU का उपयोग करूंगा; ऑनलाइन विलोपन या सबसे छोटे रास्तों के लिए मैं एक मजबूत डायनेमिक संरचना चुनूंगा।
सामान्य गलतियाँ
- विलोपन के लिए यूनियन को उलटना → मर्ज उलटने योग्य नहीं हैं → लाइफटाइम अंतराल और रोलबैक का उपयोग करें।
- रोलबैक DSU में पाथ कम्प्रेशन का उपयोग करना → कई पैरेंट राइट्स लॉग नहीं होते हैं → कम्प्रेशन के बिना यूनियन बाय साइज का उपयोग करें।
- लाइफटाइम को बंद
[add, remove]मानना → विलोपन के समय भी एज सक्रिय रहती है →[add, remove)का उपयोग करें। - प्रत्येक लीफ पर प्रत्येक एज को दोबारा मर्ज करना → जटिलता सेगमेंट-ट्री का लाभ खो देती है → कवरिंग नोड्स पर मर्ज करें।
- केवल पैरेंट पॉइंटर को पुनर्स्थापित करना → बाद के यूनियन-बाय-साइज विकल्प दूषित हो जाते हैं → पुराने आकार को भी पुनर्स्थापित करें।
- ऑनलाइन अपडेट के लिए ऑफ़लाइन विधि का वादा करना → भविष्य के अंतराल अज्ञात हैं → पहले इंटरैक्शन मॉडल की पुष्टि करें।
फॉलो-अप प्रश्न और उत्तर
क्या होगा यदि हटाने के बाद वही रिलेशनशिप ID दोबारा जोड़ी जाए?
प्रत्येक add के लिए एक नया खुला रिकॉर्ड बनाएं, और remove को केवल वर्तमान में खुले लाइफटाइम को बंद करने दें। तब वही ID पुराने वाले को ओवरराइट करने के बजाय कई असंयुक्त (disjoint) अंतराल उत्पन्न करती है।
क्या यही डिज़ाइन वर्तमान कॉम्पोनेंट साइज का उत्तर दे सकता है?
हाँ। रूट size बनाए रखें, find से रूट लौटाएं, और रोलबैक के दौरान पुराने आकारों को पुनर्स्थापित करें। अतिरिक्त कॉम्पोनेंट एग्रीगेट्स को भी इतिहास स्टैक पर पुराने मानों और प्रतिवर्ती अपडेट की आवश्यकता होती है।
क्या होगा यदि q इतना बड़ा है कि रिकर्शन या मेमोरी बाधा (bottleneck) बन जाए?
पहले जांचें कि क्या O(q log q) अंतराल स्टोरेज उपयुक्त है। फिर पुनरावर्ती DFS को एक स्पष्ट स्टैक से बदलें, कॉम्पैक्ट एज स्टोरेज का उपयोग करें, या समय ब्लॉकों को प्रोसेस करें। पाथ कम्प्रेशन को सक्षम न करें क्योंकि यह रोलबैक की शुद्धता को प्रभावित कर देगा।
टाइमलाइन विधि को आसानी से ऑनलाइन विलोपन में क्यों नहीं बदला जा सकता है?
प्रत्येक अंतराल बनाने के लिए विधि को हटाने वाले टाइमस्टैम्प की आवश्यकता होती है। ऑनलाइन इनपुट उस भविष्य के टाइमस्टैम्प को प्रकट नहीं करता है, इसलिए प्रीप्रोसेसिंग ट्री में एज को नहीं रख सकती है। ऑनलाइन डायनेमिक कनेक्टिविटी के लिए डिज़ाइन की गई संरचना का उपयोग करें और इसकी विलंबता और कार्यान्वयन लागत का पुनर्मूल्यांकन करें।