प्रॉम्प्ट और संदर्भ
एक इवेंट शेड्यूलर के लिए एक meldable min-priority queue लागू करें जिसकी टास्क प्राथमिकताओं को घटाया जा सकता है। एक binary heap बुनियादी ऑपरेशनों को संभालता है, लेकिन meld और decrease-key लागत जोड़ते हैं। हैंडल्स, लिंकिंग, two-pass मर्जिंग, डिलीशन और एज केसेस के साथ एक pairing heap लागू करें।
Pairing heaps को 1986 में self-adjusting heaps के रूप में पेश किया गया था जिसका उद्देश्य सरल कार्यान्वयन को अच्छे व्यावहारिक प्रदर्शन के साथ जोड़ना था; मूल पेपर में केवल आंशिक जटिलता विश्लेषण दिया गया था। इंटरव्यू यह परीक्षण करता है कि क्या आप कोड की शुद्धता, अमॉर्टाइज़्ड तर्क और अप्रमाणित जटिलता दावों को अलग करते हैं।
इंटरव्यूअर क्या मूल्यांकन करता है
Min-heap इनवेरिएंट, कॉन्स्टेंट-टाइम meld, two-pass सिबलिंग पेयरिंग, पुराने (stale) हैंडल्स, cut-and-relink decrease-key, खाली और डुप्लिकेट कीज़, मेमोरी ओनरशिप, और binary तथा Fibonacci heaps के मुकाबले ट्रेड-ऑफ़ को कवर करें।
पूछने के लिए स्पष्टीकरण प्रश्न
- क्या decrease-key की आवश्यकता है, या केवल push/pop की, और ऑपरेशन मिक्स क्या है?
- क्या नोड हैंडल्स स्थिर रहने चाहिए, और पुराने (stale) हैंडल्स का पता कैसे लगाया जाता है?
- क्या रिकर्शन की अनुमति है, और अधिकतम हीप आकार तथा स्टैक बजट क्या हैं?
- क्या कम्पेरेटर एक्सेप्शन थ्रो कर सकता है या बदल सकता है, और क्या डुप्लिकेट प्राथमिकताएं समर्थित हैं?
- क्या लक्ष्य सिखाने की स्पष्टता है, कम-कॉन्स्टेंट वाली व्यावहारिक गति, या एक सख्त वर्स्ट-केस प्रमाण?
एक 30-सेकंड का उत्तर
“प्रत्येक नोड एक key, payload, parent, first child, और next sibling संग्रहीत करता है, जिसमें एक हैंडल नोड की ओर इंगित करता है। Link दो रूट्स की तुलना करता है और बड़े रूट को छोटे रूट का पहला चाइल्ड बनाता है। Delete-min रूट को अलग करता है, सिबलिंग्स को बाएं से दाएं जोड़ों में लिंक करता है, फिर दाएं से बाएं मर्ज करता है। Decrease-key एक नॉन-रूट को काटता है और इसे रूट के रूप में meld करता है। हैंडल की स्थिति को ट्रैक करें और अमॉर्टाइज़्ड तथा स्थापित विश्लेषण का उपयोग करके जटिलता का वर्णन करें।”
चरण-दर-चरण विस्तृत विश्लेषण
चरण 1: नोड्स और हैंडल्स को परिभाषित करें
प्रत्येक नोड में key, payload, parent, first child, और right sibling संग्रहीत करें। एक हैंडल नोड की ओर इंगित करता है और एक लाइव मार्कर या जनरेशन रखता है, जो डिलीशन के बाद decrease-key को रोकता है। एक रूट का कोई पैरेंट नहीं होता है और सिबलिंग-लिस्ट टेल नल होती है।
Node { key, value, parent, firstChild, nextSibling, alive }
Heap { root, size }कम्पेरेटर केवल मानों को क्रमबद्ध करता है और नोड्स को म्यूटेट नहीं करता है। समान कीज़ को अलग-अलग नोड्स के रूप में मानें और आवश्यक स्थिरता नीति लागू करें।
चरण 2: Link और meld लागू करें
link(a, b) दो रूट्स की तुलना करता है, बड़ी-की वाले रूट को छोटी-की वाले रूट का पहला चाइल्ड बनाता है, और पैरेंट तथा सिबलिंग पॉइंटर्स को अपडेट करता है। meld केवल दो रूट्स को लिंक करता है; एक खाली हीप दूसरे रूट को लौटाता है।
प्रत्येक पॉइंटर अपडेट के बाद, यह सुनिश्चित (assert) करें कि रूट का कोई पैरेंट नहीं है, प्रत्येक चाइल्ड वापस अपने पैरेंट को इंगित करता है, और आकार अपरिवर्तित है। एक डीबग बिल्ड चक्रों (cycles) के लिए संरचना को पार (traverse) कर सकता है, लेकिन प्रोडक्शन ऑपरेशनों को हर बार एक लीनियर जांच नहीं करनी चाहिए।
चरण 3: Insert और find-min लागू करें
insert एक सिंगलटन हीप बनाता है, इसे रूट के साथ meld करता है, और एक स्थिर हैंडल लौटाता है। find-min रूट को पढ़ता है; एक खाली हीप नल को डीरेफरेंस करने के बजाय API का खाली परिणाम या त्रुटि लौटाता है।
यदि कॉलर्स हैंडल्स को बनाए रखते हैं, तो हीप को स्थानांतरित करने या बढ़ाने से वे अमान्य नहीं होने चाहिए। नोड्स को स्वतंत्र रूप से आवंटित करें या एक स्थिर इनडायरेक्शन लेयर का उपयोग करें, और दस्तावेज करें कि हीप नोड्स का मालिक है या केवल पेलोड का।
चरण 4: Two-pass delete-min लागू करें
रूट को हटाने के बाद, इसकी चाइल्ड लिस्ट को एक रूट लिस्ट में अलग करें। पहले पास में, बाएं से दाएं आसन्न रूट्स को जोड़ों में लिंक करें; संख्या विषम होने पर अंतिम रूट को बनाए रखें। दूसरे पास में, परिणामों को दाएं से बाएं meld करें।
deleteMin(h):
children = detachChildren(h.root)
pairs = linkAdjacent(children)
newRoot = mergeRightToLeft(pairs)
invalidate(h.root)
h.root = newRoot
h.size -= 1मर्जिंग के दौरान पुराने पैरेंट और सिबलिंग पॉइंटर्स को साफ़ करें ताकि हटाया गया रूट बना न रहे। स्टैक ओवरफ्लो से बचने के लिए एक लंबी सिबलिंग चेन के लिए एक इटरेटिव सूची का उपयोग करें।
चरण 5: Decrease-key लागू करें
एक नई की को अस्वीकार करें जो छोटी नहीं है, या एक अलग increase-key ऑपरेशन परिभाषित करें। रूट के लिए, केवल की को अपडेट करें। एक नॉन-रूट के लिए, इसे इसके पैरेंट की चाइल्ड लिस्ट से काटें, सिबलिंग पॉइंटर्स की मरम्मत करें, और इसे एक स्वतंत्र रूट के रूप में meld करें।
काटने के लिए पिछले सिबलिंग की आवश्यकता होती है: पैरेंट लिस्ट को स्कैन करें, या एक prevSibling पॉइंटर जोड़ें और अतिरिक्त रखरखाव को स्वीकार करें। एक पुराने हैंडल, किसी अन्य हीप के नोड, या एक नष्ट किए गए हीप के लिए एक त्रुटि लौटाएं।
चरण 6: इनवेरिएंट्स और जटिलता का परीक्षण करें
एक मानक प्राथमिकता कतार (priority queue) के विरुद्ध यादृच्छिक विभेदक परीक्षणों (randomized differential tests) का उपयोग करें, जिसमें डुप्लिकेट कीज़, खाली हीप्स, बार-बार decrease-key, प्रत्येक नोड को हटाना और यादृच्छिक meld शामिल हों। प्रत्येक ऑपरेशन के बाद सत्यापित करें कि रूट न्यूनतम है, आकार लाइव नोड्स से मेल खाता है, और पैरेंट-चाइल्ड लिंक चक्रीय नहीं (acyclic) हैं।
प्रमाणित सीमाओं, अमॉर्टाइज़्ड अंतर्ज्ञान और मापों को अलग करें। Pairing-heap insert और meld में छोटे कॉन्स्टेंट होते हैं, लेकिन delete-min और decrease-key के लिए सख्त विश्लेषण यह दावा करने का लाइसेंस नहीं हैं कि प्रत्येक ऑपरेशन वर्स्ट-केस O(log n) है। मान्यताओं को बताएं और binary तथा Fibonacci heaps की तुलना करें।
एक मजबूत नमूना उत्तर
मैं link, meld, two-pass delete-min, और decrease-key के लिए parent, first-child, next-sibling पॉइंटर्स और स्थिर हैंडल्स का उपयोग करूंगा। एक नॉन-रूट decrease-key को एक नए रूट के रूप में meld करने से पहले उसकी सिबलिंग लिस्ट से काटा जाता है; delete-min बाएं से दाएं पेयर करता है और दाएं से बाएं मर्ज करता है। मैं एक मानक प्राथमिकता कतार के विरुद्ध विभेदक-परीक्षण करूंगा, अचक्रीयता (acyclicity) और आकार इनवेरिएंट्स की जांच करूंगा, और अमॉर्टाइज़्ड विश्लेषण, वर्स्ट-केस सीमाओं और व्यावहारिक बेंचमार्क में अंतर करूंगा।
सामान्य गलतियाँ
- केवल की बदलना → हीप ऑर्डर और पैरेंट लिंक टूट जाते हैं → प्रत्येक नॉन-रूट decrease-key को काटें और meld करें।
- दोनों पासों को उलटना → संरचना और परिणाम गलत हो जाते हैं → बाएं से दाएं पेयर करें, फिर दाएं से बाएं मर्ज करें।
- हटाए गए हैंडल का उपयोग करना → use-after-free या क्रॉस-हीप म्यूटेशन → अमान्य करें और स्वामित्व सत्यापित करें।
- दावा करना कि प्रत्येक ऑपरेशन वर्स्ट-केस O(log n) है → जटिलता का कोई समर्थन नहीं है → अमॉर्टाइज़्ड, आंशिक विश्लेषण और माप को अलग करें।
- एक लंबी सिबलिंग सूची के माध्यम से रिकर्शन करना → स्टैक ओवरफ्लो → एक इटरेटिव सूची का उपयोग करें।
अनुवर्ती प्रश्न और उत्तर
अनुवर्ती 1: सीधे binary heap का उपयोग क्यों न करें?
Binary heaps में सरल ऐरे लेआउट और स्थिर सीमाएं होती हैं; pairing heaps में meld और लगातार decrease-key के साथ छोटे कॉन्स्टेंट हो सकते हैं। ऑपरेशन मिक्स, मेमोरी लोकैलिटी और प्रमाण आवश्यकताओं का उपयोग करके चुनें।
अनुवर्ती 2: Decrease-key सिबलिंग्स को स्कैन करने से कैसे बच सकता है?
एक prevSibling पॉइंटर या चाइल्ड-सेट इंडेक्स जोड़ें, लेकिन प्रत्येक link और cut पर अधिक पॉइंटर्स बनाए रखें। उस स्थान और रखरखाव लागत की तुलना स्कैनिंग से करें।
अनुवर्ती 3: आप एक मनमाने हैंडल को कैसे हटाते हैं?
इसकी की को नकारात्मक अनंत तक कम करें, decrease-key को कॉल करें, और फिर delete-min को कॉल करें। सुनिश्चित करें कि कम्पेरेटर और सेंटिनल सुरक्षित हैं, और हैंडल को सही ढंग से अमान्य करें।
अनुवर्ती 4: आप Fibonacci heap कब चुनेंगे?
इस पर तब विचार करें जब कार्यान्वयन की जटिलता की तुलना में सैद्धांतिक decrease-key अमॉर्टाइज़्ड बाउंड और एल्गोरिथम प्रमाण अधिक मायने रखते हों। इंजीनियरिंग कोड को अभी भी लोकैलिटी, मेमोरी और वास्तविक वर्कलोड के मापों की आवश्यकता होती है।