प्रॉम्प्ट और दायरा
हाफ-ओपन इंटरवल्स [left, right) पर तीन ऑपरेशन्स लागू करें: कवरेज जोड़ना, यह जांचना कि क्या कोई क्वेरी पूरी तरह से कवर्ड है, और कवरेज हटाना। सार्वजनिक Range Module समस्या के अनुरूप 1 <= left < right <= 10^9 और अधिकतम 10^4 कॉल्स मान लें। यदि आपका API रक्षात्मक (defensive) इनपुट स्वीकार करता है, तो बताएं कि left >= right होने पर क्या होता है।
इंटरव्यूअर क्या टेस्ट कर रहा है
मुख्य टेस्ट यह है कि क्या आप इंटरवल्स के इंसर्ट, डिलीट और क्वेरी होने के दौरान एक डेटा-स्ट्रक्चर इनवेरिएंट को चुन सकते हैं और उसे बनाए रख सकते हैं। अपेक्षित प्रतिनिधित्व डिसजॉइंट इंटरवल्स का एक सॉर्टेड कैनोनिकल कलेक्शन है; LeetCode एक ऑर्डर्ड सेट और सेगमेंट ट्री को प्रासंगिक दृष्टिकोणों के रूप में सूचीबद्ध करता है। Magicsheet इस समस्या को कठिन (hard) लेबल करती है और ऑर्डर्ड सेट्स और सेगमेंट ट्रीज के रूप में टैग करती है। यह प्रश्न हाफ-ओपन बाउंड्री अनुशासन, इटरेटर सुरक्षा और कॉम्प्लेक्सिटी एकाउंटिंग को भी परखता है।
पूछे जाने वाले स्पष्टीकरण प्रश्न
- क्या एंडपॉइंट्स इनक्लूसिव हैं? यह उत्तर
[left, right)का उपयोग करता है। - क्या एक-दूसरे को छूने वाली रेंजेस जैसे
[1,3)और[3,5)को मर्ज किया जाना चाहिए? यह उत्तर उन्हें एक कैनोनिकल इंटरवल में मर्ज करता है। - क्या निष्पादन (execution) से पहले सभी एंडपॉइंट्स ज्ञात हैं? आधारभूत डिज़ाइन ऑनलाइन है, इसलिए वे ज्ञात नहीं हैं।
- अमान्य
left >= rightइनपुट को क्या करना चाहिए? स्थिति बदले बिना वापस लौटें, या इसे स्पष्ट रूप से अस्वीकार करें। - क्या डोमेन इतना बाउंडेड और स्थिर है कि सेगमेंट ट्री को उचित ठहराया जा सके? यह वैकल्पिक डिज़ाइन को प्रभावित करता है।
चरण-दर-चरण समाधान
1. प्रतिनिधित्व और इनवेरिएंट चुनें
इंटरवल स्टार्ट से एंड तक एक ऑर्डर्ड मैप का उपयोग करें। std::map कीज़ को सॉर्टेड रखता है और लॉगरिदमिक सर्च, इंसर्शन और रिमूवल प्रदान करता है; आरोही इटरेशन एल्गोरिदम को केवल नजदीकी इंटरवल्स को प्रोसेस करने की अनुमति देता है। टचिंग कवरेज को सामान्य (normalize) करें, ताकि प्रत्येक ऑपरेशन के बाद मैप में previousEnd >= nextStart वाला कोई युग्म न हो।
2. कवरेज जोड़ें
उस पहले इंटरवल से शुरू करें जिसका एंड कम से कम left हो (या पूर्ववर्ती के बाद का पहला इंटरवल)। जब तक वर्तमान स्टार्ट बढ़ते हुए right से अधिक न हो, तब तक उस इंटरवल को शामिल करने के लिए left और right का विस्तार करें, फिर उसे मिटाने के लिए चिह्नित करें। चिह्नित निरंतर रेंज को मिटाएं और मर्ज किए गए इंटरवल को इंसर्ट करें। रिक्त स्थिति और दोनों पड़ोसियों से अलग (disjoint) रेंज के लिए किसी विशेष संरचना की आवश्यकता नहीं होती है।
3. कवरेज हटाएं और कवरेज क्वेरी करें
हटाने के लिए, start < right और end > left वाले इंटरवल्स पर जाएं। प्रत्येक ओवरलैप के लिए, जब oldStart < left हो तो [oldStart,left) को बनाए रखें, और जब right < oldEnd हो तो [right,oldEnd) को बनाए रखें; अंशों (fragments) को इंसर्ट करने से पहले मूल को मिटा दें। एक क्वेरी के लिए, उस इंटरवल का निरीक्षण करें जिसका स्टार्ट left से अधिक न होने वाला सबसे बड़ा स्टार्ट हो; true केवल तभी लौटाएं जब वह मौजूद हो और उसका एंड कम से कम right हो। हाफ-ओपन एंडपॉइंट्स के साथ, [1,3), [3,4) को कवर नहीं करता है।
शुद्धता और जटिलता
इनवेरिएंट गणितीय आगमन (induction) द्वारा शुद्धता साबित करता है। जोड़ना नई रेंज से जुड़े प्रत्येक इंटरवल को उनके यूनियन से बदल देता है, इसलिए कोई भी कवर्ड पॉइंट नष्ट नहीं होता है और परिणाम कैनोनिकल होता है। हटाना प्रत्येक ओवरलैप को हटाई गई रेंज के बाहर के सटीक हिस्सों से बदल देता है। पूर्ववर्ती को क्वेरी करना पर्याप्त है क्योंकि सॉर्टेड डिसजॉइंट इंटरवल्स यह सुनिश्चित करते हैं कि कोई भी पिछला इंटरवल बाद में समाप्त न हो, और left से बड़े स्टार्ट वाला कोई भी बाद का इंटरवल left को शामिल नहीं कर सकता है।
मान लें कि n संग्रहीत इंटरवल्स की संख्या है और k एक अपडेट द्वारा प्रभावित होने वाले इंटरवल्स की संख्या है। एक क्वेरी O(log n) होती है। एक अपडेट O(log n) खोजों के साथ-साथ O(k) इटरेटर ट्रैवर्सल और रिमूवल करता है; जो कार्यान्वयन प्रत्येक की को फिर से खोजते हैं वे इसके बजाय O(k log n) हो सकते हैं। स्पेस O(n) है। एक सेगमेंट ट्री ज्ञात बाउंडेड कोऑर्डिनेट यूनिवर्स के लिए उचित है, जबकि कोऑर्डिनेट कम्प्रेशन के लिए सभी एंडपॉइंट्स का ऑफलाइन होना आवश्यक है और यह मनमाने ऑनलाइन कॉल्स के लिए अनुपयुक्त है।
मॉडल उत्तर
"मैं हाफ-ओपन, सॉर्टेड, डिसजॉइंट इंटरवल्स का एक नॉर्मलाइज्ड ऑर्डर्ड मैप लागू करूंगा। Add प्रत्येक ओवरलैपिंग या टचिंग इंटरवल को खोजता है और मर्ज करता है, remove ओवरलैप्स को डिलीट करता है और अधिकतम दो बाउंड्री अंशों को रखता है, और query अनुरोधित स्टार्ट के पूर्ववर्ती की जांच करता है। मुख्य प्रमाण दायित्व यह है कि प्रत्येक ऑपरेशन कैनोनिकल यूनियन को बनाए रखता है। Query की लागत O(log n) है; एक निरंतर इटरेटर रेंज को मिटाते समय एक अपडेट की लागत O(log n + k) होती है और यह O(n) स्पेस का उपयोग करता है। मैं इस ऑनलाइन मैप की तुलना सेगमेंट ट्री से केवल कोऑर्डिनेट डोमेन और सभी एंडपॉइंट्स ज्ञात हैं या नहीं, इसकी पुष्टि करने के बाद ही करूंगा।"
सामान्य गलतियाँ
- एंडपॉइंट्स को क्लोज्ड मानना → आसन्न रेंजेस गलत तरीके से ओवरलैप होती हुई प्रतीत होती हैं → पहले
[left,right)को परिभाषित करें। - टचिंग इंटरवल्स को अलग छोड़ना → बाद की क्वेरीज़ और अपडेट्स से बचा जा सकने वाले डुप्लिकेट्स का सामना करते हैं → आसन्नता को सामान्य (normalize) करें।
- अमान्य इटरेटर को बढ़ाते हुए हटाना → नोड्स छूट जाते हैं या मुक्त किए गए स्टोरेज तक पहुंच होती है → अगले इटरेटर को सहेजें या किसी ज्ञात रेंज को मिटाएं।
- दोनों पक्षों को बनाए रखे बिना विभाजित करना → एक सीमा पर कवरेज गायब हो जाता है → मध्य हटाने और पूर्ण समावेश का परीक्षण करें।
- यह दावा करना कि प्रत्येक अपडेट O(log n) है → एक ऑपरेशन कई इंटरवल्स को छू सकता है → बाउंड में
kको शामिल करें। - ऑनलाइन कोऑर्डिनेट कम्प्रेशन का उपयोग करना → अनदेखे एंडपॉइंट्स इंडेक्स को अमान्य कर देते हैं → एक ऑर्डर्ड संरचना का उपयोग करें या एक पूर्ण ऑफलाइन सेट से पुनर्निर्माण करें।
फॉलो-अप और विस्तार
किन बाउंड्री मामलों का परीक्षण किया जाना चाहिए?
एक खाली मॉड्यूल, बार-बार जोड़ना, बिल्कुल एक छोर पर क्वेरी, टचिंग जोड़ [1,3) फिर [3,5), मध्य भाग को हटाना, पूरे इंटरवल को कवर करने वाला निष्कासन, बिना ओवरलैप वाला निष्कासन, नेस्टेड रेंजेस, और जब API अनुमति देता है तब एंडपॉइंट्स 0 और 10^9 का परीक्षण करें।
आप इनवेरिएंट का परीक्षण कैसे करेंगे?
प्रत्येक रैंडमाइज्ड ऑपरेशन के बाद, सॉर्टेड स्टार्ट्स, end > start, और previousEnd < nextStart की पुष्टि (assert) करें। एक बहुत छोटे कोऑर्डिनेट डोमेन पर एक छोटे बूलियन ऐरे या ब्रूट-फोर्स यूनियन मॉडल के विरुद्ध क्वेरी परिणामों की तुलना करें। यह ऑफ-बाय-वन और अंश-हानि बग्स को पकड़ता है।
सेगमेंट ट्री कब बेहतर होगा?
सेगमेंट ट्री तब चुनें जब कोऑर्डिनेट यूनिवर्स बाउंडेड या कंप्रेसिबल हो और रेंज एग्रीगेशन या लेज़ी प्रोपेगेशन महत्वपूर्ण हो। यह अनुमानित लॉगरिदमिक ऑपरेशन्स देता है लेकिन नोड और लेज़ी-स्टेट जटिलता जोड़ता है; स्पार्स, ऑनलाइन इंटरवल्स के लिए ऑर्डर्ड मैप अधिक सरल है।