प्रॉम्प्ट और उपयोग के मामले
इंटरवल ट्री डायनेमिक समय सीमाओं, बुकिंग और संसाधन अधिभोग के लिए उपयुक्त हैं। मुख्य विचार निचले एंडपॉइंट द्वारा व्यवस्थित एक बैलेंस्ड ट्री है, जिसे असंभव शाखाओं को छोड़ने के लिए प्रत्येक सबट्री के अधिकतम ऊपरी एंडपॉइंट के साथ ऑगमेंट किया जाता है।
इंटरव्यूअर क्या मूल्यांकन करता है
- क्या बंद-अंतराल की सीमाएँ और ओवरलैप सही हैं।
- क्या
maxEndको सटीक रूप से परिभाषित और बनाए रखा गया है। - क्या ऑग्मेंटेशन प्रत्येक नोड को स्कैन करने के बजाय काम को प्रून करता है।
- क्या इंसर्शन, विलोपन और रोटेशन ऑग्मेंटेशन को अपडेट करते हैं।
- क्या डुप्लिकेट, खाली ट्री और मौजूद न होने वाले विलोपन को संभाला जाता है।
- क्या जटिलता रिपोर्ट किए गए अंतरालों की संख्या का ध्यान रखती है।
उत्तर देने से पहले स्पष्टीकरण
- क्या अंतराल बंद, खुले या अर्ध-खुले हैं?
- क्या एंडपॉइंट पूर्णांक, फ्लोटिंग पॉइंट या टाइमस्टैम्प हैं?
- क्या डुप्लिकेट अंतराल की अनुमति है, और क्या विलोपन आईडी या एंडपॉइंट का उपयोग करता है?
- क्या एक क्वेरी को प्रत्येक ओवरलैप या केवल एक को वापस करना चाहिए?
- क्या ऑनलाइन इंसर्शन, विलोपन और सेल्फ-बैलेंसिंग आवश्यक हैं?
- क्या परिणाम निचले एंडपॉइंट द्वारा सॉर्ट किए जाने चाहिए?
30-सेकंड उत्तर ढांचा
“मैं एक बैलेंस्ड ट्री को निचले एंडपॉइंट द्वारा कुंजीबद्ध करूँगा और ऊपरी एंडपॉइंट के साथ-साथ सबट्री का अधिकतम maxEnd संग्रहीत करूँगा। एक क्वेरी वर्तमान ओवरलैप की रिपोर्ट करती है, बाएं सबट्री में केवल तभी प्रवेश करती है जब उसका maxEnd क्वेरी की निचली सीमा तक पहुंच सकता है, और दाईं ओर केवल तभी प्रवेश करती है जब वर्तमान निचला एंडपॉइंट क्वेरी की ऊपरी सीमा के भीतर हो। इंसर्ट और डिलीट बैलेंस्ड-ट्री ऑपरेशनों का उपयोग करते हैं और पथ के साथ maxEnd को अपडेट करते हैं, रोटेशन के बाद प्रभावित नोड्स की पुनर्गणना करते हैं।”
चरण-दर-चरण गहन विश्लेषण
चरण 1: ओवरलैप को परिभाषित करें। बंद [a,b] और [c,d] बिल्कुल तभी ओवरलैप होते हैं जब a <= d और c <= b; पहले a > b को अस्वीकार करें।
चरण 2: एक नोड को परिभाषित करें। low, high, एक अद्वितीय आईडी, चाइल्ड नोड्स और maxEnd संग्रहीत करें; (low, id) द्वारा क्रमबद्ध करें ताकि समान एंडपॉइंट अलग बने रहें।
चरण 3: प्रश्नों को प्रून करें। जब वर्तमान नोड ओवरलैप हो तो उसकी रिपोर्ट करें। केवल तभी बाईं ओर रिकर्स करें जब left.maxEnd >= query.low, और केवल तभी दाईं ओर रिकर्स करें जब वर्तमान low <= query.high।
चरण 4: ऑग्मेंटेशन बनाए रखें। maxEnd नोड के high और दोनों चाइल्ड मानों का अधिकतम है। अपडेट और रोटेशन के बाद केवल प्रभावित पथों की पुनर्गणना करें।
चरण 5: सुरक्षित रूप से हटाएं। आईडी द्वारा खोजें, बैलेंस्ड-ट्री विलोपन करें, और प्रतिस्थापन पथ से ऊपर की ओर maxEnd को अपडेट करें; अनुपलब्ध आईडी के लिए एक स्पष्ट परिणाम लौटाएं।
चरण 6: सीमाओं का परीक्षण करें। स्पर्श करने वाले एंडपॉइंट, समावेशन, डुप्लिकेट, ऋणात्मक मान, बिंदु अंतराल, एक खाली ट्री, और प्रत्येक अंतराल वाले आउटपुट को कवर करें।
चरण 7: जटिलता बताएं। एक बैलेंस्ड ट्री की ऊंचाई लघुगणकीय (logarithmic) होती है; एक क्वेरी k रिपोर्ट किए गए अंतरालों के लिए O(log n + k) है, एक अपडेट O(log n) है, और स्पेस O(n) है।
मॉडल उच्च-गुणवत्ता वाला उत्तर
“मैं (low, id) द्वारा क्रमबद्ध एक रेड-ब्लैक ट्री का उपयोग करूँगा, जिसमें प्रत्येक नोड high और सबट्री maxEnd संग्रहीत करेगा। [q1,q2] के लिए, तब रिपोर्ट करें जब low <= q2 और high >= q1; केवल तभी बाएं चाइल्ड में प्रवेश करें जब left.maxEnd >= q1, और दाएं चाइल्ड में केवल तभी जब वर्तमान low <= q2 हो। इंसर्ट और डिलीट पथ पर मैक्सिमा को अपडेट करते हैं, और रोटेशन रोटेट किए गए नोड्स और पैरेंट की पुनर्गणना करते हैं। आईडी डुप्लिकेट को अलग करती हैं। मैं बंद एंडपॉइंट और ऑल-हिट आउटपुट का परीक्षण करता हूँ। क्वेरी O(log n + k) है और अपडेट O(log n) है।”
सामान्य गलतियाँ
- ओवरलैप के लिए
low < q2का उपयोग करना → स्पर्श करने वाले एंडपॉइंट गायब हो जाते हैं → चुने गए अंतराल प्रकार का मिलान करें। - केवल प्रत्येक नोड का
highसंग्रहीत करना → प्रूनिंग असंभव हो जाती है → सबट्रीmaxEndबनाए रखें। - रोटेशन के बाद ऑग्मेंटेशन को छोड़ना → बाद की क्वेरी गलत हो जाती हैं → प्रभावित नोड्स की पुनर्गणना करें।
O(log n)क्वेरी का दावा करना → आउटपुट लागत छूट जाती है →O(log n + k)बताएं।- समान एंडपॉइंट्स को ओवरराइट करना → विलोपन और आउटपुट अस्थिर हो जाते हैं → एक अद्वितीय आईडी या समग्र कुंजी (composite key) का उपयोग करें।
फॉलो-अप प्रश्न और उत्तर
फॉलो-अप 1: क्या होगा यदि क्वेरी केवल बिंदु हैं?
[x,x] और समान maxEnd प्रूनिंग का उपयोग करें। यदि एंडपॉइंट छोटे पूर्णांक और स्थिर हैं, तो एक विशेष असतत (discrete) संरचना का मूल्यांकन करें।
फॉलो-अप 2: सूची को स्कैन क्यों नहीं करते?
कई अंतरालों और इंटरलीव्ड अपडेट के साथ, एक स्कैन सभी नोड्स को छूता है। ट्री खोज को एक लघुगणकीय पथ और रिपोर्ट किए गए आउटपुट तक सीमित करता है।
फॉलो-अप 3: रोटेशन maxEnd को क्यों संरक्षित करते हैं?
वे केवल स्थानीय सबट्री बदलते हैं; प्रभावित नोड्स की नीचे से ऊपर पुनर्गणना फ़ील्ड परिभाषा को पुनर्स्थापित करती है।
फॉलो-अप 4: आप डुप्लिकेट अंतराल कैसे हटाते हैं?
इंसर्शन पर एक आईडी असाइन करें, (low, ID) द्वारा कुंजीबद्ध करें, और आईडी द्वारा हटाएं ताकि अन्य समान-एंडपॉइंट अंतराल बने रहें।
फॉलो-अप 5: फ्लोटिंग-पॉइंट एंडपॉइंट के बारे में क्या?
NaN, सटीकता और समानता सिमेंटिक्स को परिभाषित करें। जब संभव हो, पूर्णांक टिक या समय इकाइयों में परिवर्तित करें।
फॉलो-अप 6: आप सॉर्ट किए गए आउटपुट की गारंटी कैसे देते हैं?
इन-ऑर्डर ट्रैवर्सल निचला-एंडपॉइंट क्रम प्रदान करता है; यदि प्रूनिंग विज़िट क्रम बदलती है, तो एकत्र करें और सॉर्ट करें, अतिरिक्त लागत बताते हुए।
फॉलो-अप 7: प्रूनिंग सुरक्षित क्यों है?
यदि बाएं सबट्री का अधिकतम एंडपॉइंट क्वेरी की निचली सीमा से नीचे है, तो वहां का प्रत्येक अंतराल ओवरलैप करने के लिए बहुत जल्दी समाप्त हो जाता है, इसलिए इसे छोड़ना सुरक्षित है।