1. समस्या और संदर्भ
एक डायनामिक ऑर्डर्ड सेट बनाए रखें जो खोज (search), इंसर्शन, डिलीशन, और आवश्यकता पड़ने पर कुंजी द्वारा विभाजन (split) के बाद विलय (merge) का समर्थन करता हो। एक treap लागू करें: प्रत्येक नोड key पर एक बाइनरी-सर्च-ट्री (BST) इनवेरिएंट और रैंडम priority पर एक मैक्स-हीप इनवेरिएंट को संतुष्ट करता है। पहले यूनीक कुंजियों को मानकर चलें, फिर डुप्लिकेट हैंडलिंग की व्याख्या करें।
2. इंटरव्यूअर क्या परख रहा है
- यह समझाना कि BST इनवेरिएंट और हीप इनवेरिएंट प्रत्येक क्या प्रदान करते हैं।
- केवल रोटेशन को याद रखने के बजाय
splitऔरmergeसे insert और erase को कंपोज़ करना। - यह स्पष्ट करना कि
O(log n)अपेक्षित (expected) है, और रैंडम गुणवत्ता व प्राथमिकता टकराव (collisions) आकार को प्रभावित करते हैं। - सही अपडेट क्रम और खाली-चाइल्ड हैंडलिंग के साथ सबट्री साइज़ या एग्रीगेट्स को बनाए रखना।
3. पहले स्पष्ट करने योग्य प्रश्न
- क्या कुंजियाँ यूनीक हैं? यदि डुप्लिकेट की अनुमति है, तो समान कुंजियों को लगातार एक तरफ रखें या कंपोज़िट कुंजी के रूप में
(key, id)का उपयोग करें। - क्या प्राथमिकताएँ कॉलर्स द्वारा दी जाती हैं या आंतरिक रूप से उत्पन्न होती हैं? आंतरिक जनरेशन के लिए एक रैंडम स्रोत, टकराव नीति और एक पुनरुत्पादक (reproducible) परीक्षण सीड की आवश्यकता होती है।
- क्या
splitसीमा कुंजी (boundary key) को बाईं ओर रखता है, या इसके लिए एक स्ट्रिक्ट लेस-दैन (less-than) विभाजन की आवश्यकता होती है? यह इंसर्शन और रेंज-क्वेरी कोड को बदल देता है। - क्या हमें k-वें ऑर्डर स्टैटिस्टिक्स, रेंज सम्स, या किसी अंतर्निहित अनुक्रम (implicit sequence) की आवश्यकता है? प्रत्येक बदलाव को तब सबट्री मेटाडेटा अपडेट करना होगा।
4. तीस-सेकंड का उत्तर ढांचा
"मैं कुंजी द्वारा BST क्रम और एक रैंडम प्राथमिकता द्वारा मैक्स-हीप क्रम बनाए रखता हूँ। इसके मुख्य ऑपरेशन्स split(T, key) हैं, जो सीमा तक की कुंजियों और उससे ऊपर की कुंजियों को लौटाता है, और merge(L, R), जो यह मानता है कि L की प्रत्येक कुंजी R की प्रत्येक कुंजी से अधिकतम बराबर या छोटी है और उच्च-प्राथमिकता वाले रूट को चुनता है। Insert नई कुंजी के चारों ओर विभाजित (split) करता है और इसे वापस मर्ज करता है; erase लक्ष्य के चिल्ड्रेन को मर्ज करता है। प्रत्येक रिकर्सिव रिटर्न साइज़ को अपडेट करता है। ऊँचाई और ऑपरेशन्स अपेक्षित O(log n) हैं, वर्स्ट-केस नहीं, इसलिए प्रोडक्शन कोड को रिप्रोड्यूस करने योग्य परीक्षणों, गहराई की निगरानी, या एक नियतात्मक सीमा (deterministic bound) वाले पेड़ की आवश्यकता होती है।"
5. चरण-दर-चरण तर्क
पहले इनवेरिएंट्स तय करें। प्रत्येक नोड के लिए, बाईं कुंजियाँ उसकी कुंजी से बड़ी नहीं हैं, दाईं कुंजियाँ बड़ी हैं, और उसकी प्राथमिकता दोनों चाइल्ड प्राथमिकताओं से कम से कम अधिक या बराबर है। यह लेख "समान कुंजियाँ बाईं ओर जाती हैं" का उपयोग करता है; एक कंपोज़िट (key, uniqueId) एक अन्य स्पष्ट नीति है।
दूसरा, split लागू करें। यदि रूट कुंजी अधिकतम सीमा तक है, तो रूट और बायाँ सबट्री बाएँ परिणाम के हैं, इसलिए दाएँ चाइल्ड में रिकर्स करें। अन्यथा दाएँ परिणाम के लिए बाएँ चाइल्ड में रिकर्स करें। लौटाए गए चाइल्ड को फिर से कनेक्ट करें और साइज़ अपडेट करें। केवल एक रूट-टू-लीफ पथ का दौरा किया जाता है।
तीसरा, merge लागू करें। पहले एक खाली पेड़ को संभालें। यदि बाएँ रूट की प्राथमिकता अधिक है, तो इसे रूट के रूप में रखें और इसके दाएँ चाइल्ड को दाएँ पेड़ के साथ मर्ज करें; अन्यथा दाएँ रूट को रखें और बाएँ पेड़ को इसके बाएँ चाइल्ड के साथ मर्ज करें। यह पूर्व शर्त कि प्रत्येक बाईं कुंजी प्रत्येक दाईं कुंजी से बड़ी नहीं है, BST क्रम को बनाए रखती है।
चौथा, ऑपरेशन्स को कंपोज़ करें। Insert के लिए, split(root, key) और फिर merge(merge(left, node), right)। Erase के लिए, लक्ष्य को merge(node.left, node.right) से बदलें। Search कुंजी द्वारा नीचे उतरता है और इसके लिए किसी स्प्लिट की आवश्यकता नहीं होती है। यदि साइज़ संग्रहीत है, तो प्रत्येक split, merge, insert, और erase के बाद size = 1 + size(left) + size(right) चलाएँ।
पाँचवाँ, जटिलता और विफलता पर चर्चा करें। रैंडम प्राथमिकताएँ आकार को रैंडम रूप से निर्मित BST के तुलनीय बनाती हैं, जिससे अपेक्षित O(log n) ऑपरेशन्स मिलते हैं; CP-Algorithms लॉगरिदमिक अपेक्षित split, merge, इंसर्शन और डिलीशन का दस्तावेजीकरण करता है। लगभग मोनोटोनिक प्राथमिकताएं अभी भी एक O(n) पेड़ बना सकती हैं, इसलिए परीक्षणों में फिक्स्ड सीड का उपयोग करें, ऊंचाई की निगरानी करें, या जब वर्स्ट-केस बाउंड अनिवार्य हो तो AVL या रेड-ब्लैक ट्री चुनें।
6. उच्च-गुणवत्ता वाला नमूना उत्तर
"मैं पहले डुप्लिकेट-कुंजी सिमेंटिक्स पर सहमति बनाऊंगा, फिर दो प्रिमिटिव्स लागू करूंगा। split एक सीमा के चारों ओर बाएँ और दाएँ पेड़ लौटाता है, एक चाइल्ड को रिकर्सिव रूप से विभाजित करता है, और रूट को फिर से जोड़ता है। merge मानता है कि सभी बाईं कुंजियाँ दाईं कुंजियों से बड़ी नहीं हैं और उच्च-प्राथमिकता वाले रूट को चुनता है। Insert स्प्लिट करता है और नए नोड को परिणामों के बीच रखता है; erase लक्ष्य के चिल्ड्रेन को मर्ज करता है। सबट्री साइज़ को अपडेट करने से k-वां चयन भी सक्षम होता है। रैंडम प्राथमिकताएँ अपेक्षित O(log n) ऊंचाई देती हैं, न कि वर्स्ट-केस गारंटी, इसलिए मैं खाली पेड़ों, डुप्लिकेट्स और लंबे ट्रेल्स में फिक्स्ड सीड्स के साथ परीक्षण करूंगा, गहराई की निगरानी करूंगा, और जब नियतात्मक सीमाएं मायने रखती हैं तो रेड-ब्लैक ट्री का चयन करूंगा।"
7. सामान्य गलतियाँ
- गलती → केवल BST क्रम बनाए रखना → सॉर्ट किए गए इंसर्ट अभी भी एक लिंक्ड लिस्ट बनाते हैं → प्राथमिकता हीप इनवेरिएंट को भी बनाए रखें।
- गलती → कुंजी सीमाओं की जांच किए बिना Merge करना → खोज गलत रास्ता चुनती है → दस्तावेजित करें कि बाईं कुंजियाँ दाईं कुंजियों से बड़ी नहीं हैं।
- गलती → Split के बाद सबट्री साइज़ को अपडेट करना भूल जाना → k-वें और रेंज स्टैटिस्टिक्स भटक जाते हैं → चिल्ड्रेन को फिर से कनेक्ट करने के तुरंत बाद मेटाडेटा खींचें/अपडेट करें।
- गलती → अपेक्षित
O(log n)को सबसे खराब स्थिति की गारंटी मानना → प्रतिकूल प्राथमिकताएं एक गहरा पेड़ बना सकती हैं → गहराई की निगरानी करें या AVL/रेड-ब्लैक ट्री का उपयोग करें। - गलती → search, erase, और split में असंगत डुप्लिकेट नीति → समान कुंजियाँ गलत सबट्री में चली जाती हैं → एक कंपोज़िट कुंजी या एक सीमा नियम का उपयोग करें।
8. अनुवर्ती प्रश्न
आप k-वें सबसे छोटे तत्व का समर्थन कैसे करते हैं?
प्रत्येक नोड पर सबट्री का साइज़ स्टोर करें। नीचे उतरते समय k की तुलना बाएँ साइज़ से करें; प्रत्येक split, merge, इंसर्शन और erase पर साइज़ अपडेट करें अन्यथा क्वेरी गलत हो जाएगी।
एक treap एक अंतर्निहित अनुक्रम (implicit sequence) का प्रतिनिधित्व कैसे कर सकता है?
स्पष्ट कुंजियों को स्टोर न करें। किसी नोड की स्थिति को उसके बाएँ-सबट्री साइज़ और पूर्वज योगदान से परिभाषित करें। इंसर्शन, डिलीशन और रेंज एग्रीगेट्स का समर्थन करने के लिए स्थिति के अनुसार split करें और वापस merge करें; लेज़ी फ़्लैग्स (lazy flags) रेंज रिवर्सल या जोड़ को संभाल सकते हैं।
आप treap से कब बचेंगे?
जब स्ट्रिक्ट वर्स्ट-केस O(log n), नियंत्रित रैंडमनेस, या एक परिपक्व समवर्ती कार्यान्वयन (concurrent implementation) की आवश्यकता हो, तो AVL, रेड-ब्लैक ट्री, या डेटाबेस इंडेक्स चुनें। Treaps छोटे कोड और लचीले split/merge कंपोज़िशन के बदले उस गारंटी का त्याग करते हैं।