संकेत और संदर्भ
आप एक टास्क शेड्यूलर के लिए एक मेल्डेबल मिन-प्रायोरिटी कतार लागू कर रहे हैं। कॉलर अक्सर दो कतारों को जोड़ते हैं, फिर काम जोड़ते हैं और सबसे छोटी प्राथमिकता को हटाते हैं। meld, insert, find-min, और extract-min लागू करें, और यादृच्छिकीकरण, खाली हीप्स, डुप्लिकेट कुंजियों और नोड ओनरशिप के लिए अपने विकल्पों को बताएं।
एक रैंडमाइज्ड मेल्डेबल हीप, लेफ़्टिस्ट रैंक जैसे रैंक मेटाडेटा के बिना एक बाइनरी ट्री के रूप में हीप ऑर्डर का प्रतिनिधित्व करता है। प्रत्येक मर्ज पर, यह बेतरतीब ढंग से बाईं या दाईं रिकर्सिव शाखा चुनता है। इंटरव्यू इनवेरिएंट्स, प्रायिकता मान्यताओं और परीक्षण योग्यता का परीक्षण करता है।
इंटरव्यूअर क्या मूल्यांकन करता है
न्यूनतम-रूट इनवेरिएंट, meld के विनिमय और उपभोग सेमांटिक्स, रैंडम-बिट सीमाओं, डुप्लिकेट कुंजियों, ओनरशिप, रिकर्शन गहराई, विनाश, और अपेक्षित व सबसे खराब स्थिति की सीमाओं के बीच अंतर को कवर करें। वर्कलोड के अनुसार बाइनरी, लेफ़्टिस्ट और पेयरिंग हीप्स की तुलना करें।
स्पष्टीकरण के लिए पूछे जाने वाले प्रश्न
- क्या
meldअपने इनपुट हीप्स का उपभोग करता है, या दोनों मूल हीप्स का उपयोग योग्य रहना आवश्यक है? - क्या रैंडम स्रोत को इंजेक्ट किया जा सकता है ताकि विफलताओं को दोहराया जा सके?
- नोड सीमा और रिकर्शन-स्टैक बजट क्या हैं?
- क्या स्थिर हैंडल, मनमाने ढंग से डिलीट करना या
decrease-keyआवश्यक हैं? - क्या लक्ष्य एक शिक्षण कार्यान्वयन, प्रोडक्शन थ्रूपुट, या एक सख्त सबसे खराब स्थिति की सीमा है?
30-सेकंड उत्तर ढांचा
“प्रत्येक नोड एक कुंजी, मान और दो चाइल्ड पॉइंटर्स संग्रहीत करता है। meld(a,b) खाली पेड़ों को संभालता है, छोटे रूट को रखता है, फिर दूसरे पेड़ को बेतरतीब ढंग से बाएं या दाएं चाइल्ड में मर्ज करता है। insert रूट के साथ एक सिंगलटन को मेल्ड करता है, और extract-min हटाए गए रूट के बच्चों को मेल्ड करता है। रूट न्यूनतम रहता है और संचालन आमतौर पर अपेक्षित लॉगरिदमिक समय के होते हैं, लेकिन रिकर्शन गहराई और रैंडम बीजों के लिए स्पष्ट परीक्षणों और सीमाओं की आवश्यकता होती है।”
चरण-दर-चरण विस्तृत उत्तर
चरण 1: नोड्स और ओनरशिप को परिभाषित करें
प्रत्येक नोड में key, value, left, और right संग्रहीत करें। हीप अपने रूट और नोड काउंट को संग्रहीत करता है। एक म्यूटेबल कार्यान्वयन के साथ, meld इनपुट रूट्स को फिर से जोड़ता है, इसलिए एपीआई को बताना चाहिए कि इनपुट का उपभोग किया गया है या नहीं। एक पर्सिस्टेंट कार्यान्वयन पथ की प्रतिलिपि बनाता है और इसलिए समय और स्थान की लागत को बदलता है।
meld(a, b):
if a is empty: return b
if b is empty: return a
if b.key < a.key: swap(a, b)
if randomBit() == 0:
a.left = meld(a.left, b)
else:
a.right = meld(a.right, b)
return aचरण 2: मेल्ड इनवेरिएंट को बनाए रखें
पहले रूट्स की तुलना करें और छोटी कुंजी को रूट के रूप में रखें। समान कुंजियाँ एक निश्चित टाई नियम या एक यादृच्छिक नियम का उपयोग कर सकती हैं, लेकिन हीप ऑर्डर वैध रहना चाहिए। रिकर्शन वापस आने के बाद, मर्ज किए गए चाइल्ड की प्रत्येक कुंजी कम से कम वर्तमान रूट के बराबर होती है, इसलिए पूरे पथ पर इनवेरिएंट बना रहता है।
एक नोड को दो पैरेंट्स से न जोड़ें। एक म्यूटेबल meld को ओनरशिप को ट्रैक करना चाहिए; एक डिबग बिल्ड काउंट्स और साइकिल की जांच कर सकता है। एक पर्सिस्टेंट कार्यान्वयन साझा सबट्री को म्यूटेट नहीं कर सकता है।
चरण 3: Insert और Find-Min लागू करें
insert एक सिंगलटन बनाता है और इसे वर्तमान रूट के साथ मेल्ड करता है, फिर काउंट बढ़ाता है। find-min रूट को पढ़ता है; एक खाली हीप खाली परिणाम या त्रुटि लौटाकर इंटरफ़ेस अनुबंध का पालन करता है। डुप्लिकेट कुंजियाँ अलग-अलग प्रविष्टियों के रूप में रहती हैं।
एक ग्लोबल रैंडम स्रोत परीक्षणों को दोहराना कठिन बनाता है। एक रैंडम स्रोत इंजेक्ट करें और परीक्षणों में एक निश्चित बीज का उपयोग करें; प्रोडक्शन को अभी भी एक निष्पक्ष, स्वतंत्र रैंडम-बिट कार्यान्वयन की आवश्यकता होती है।
चरण 4: Extract-Min लागू करें
रूट को हटाने के बाद, नया रूट बनाने के लिए इसके बाएं और दाएं सबट्री को मेल्ड करें। काउंट घटाने से पहले दोनों पॉइंटर्स को अलग करें; यदि हीप मेमोरी का मालिक है, तो पुराने रूट को अंत में रिलीज़ करें। जब इनपुट का उपभोग किया जाता है, तो हटाए गए रूट के हैंडल को अमान्य कर दें।
यदि पुराने संस्करणों का उपयोग योग्य रहना आवश्यक है, तो साझा नोड्स को म्यूटेट करने के बजाय पर्सिस्टेंट पाथ कॉपिंग का उपयोग करें। इंटरफ़ेस सीमा पर इसे स्पष्ट रूप से बताएं क्योंकि अलियासिंग अन्यथा डेटा को चुपचाप दूषित कर सकती है।
चरण 5: जटिलता सीमाओं को बताएं
एक रैंडमाइज्ड मेल्डेबल हीप के लिए, meld, insert, और extract-min का आमतौर पर बताए गए रैंडम मॉडल के तहत अपेक्षित-लॉगरिदमिक या उच्च-प्रायिकता लॉगरिदमिक के रूप में विश्लेषण किया जाता है। find-min निरंतर समय है, और स्थान नोड्स की संख्या में रैखिक है।
अपेक्षित सीमा को प्रति-ऑपरेशन सबसे खराब स्थिति के दावे में न बदलें। एक दुर्भाग्यपूर्ण यादृच्छिक अनुक्रम एक गहरा पेड़ उत्पन्न कर सकता है। प्रोडक्शन कोड को रिकर्शन को सीमित करना चाहिए, आवश्यकता पड़ने पर एक स्पष्ट स्टैक का उपयोग करना चाहिए, और बेंचमार्क और यादृच्छिक परीक्षणों के साथ वितरण को मान्य करना चाहिए।
चरण 6: एक संदर्भ के विरुद्ध परीक्षण करें
खाली हीप्स, डुप्लिकेट कुंजियों, बारी-बारी से मेल्ड, बार-बार निष्कर्षण, निश्चित बीजों और गहराई के चरम सीमाओं के साथ एक मानक प्राथमिकता कतार के खिलाफ अंतर-परीक्षण (differential-test) करें। प्रत्येक ऑपरेशन के बाद न्यूनतम रूट, नोड काउंट, एसाइक्लिसिटी और ओनरशिप नियमों की जांच करें।
पेयरिंग हीप के विपरीत, यह डिज़ाइन एक बाइनरी ट्री और यादृच्छिक शाखाओं का उपयोग करता है, इसलिए इसे सिबलिंग सूचियों, दो-पास संयोजन या हैंडल कटौती की आवश्यकता नहीं होती है। लेफ़्टिस्ट हीप के विपरीत, यह रैंक मेटाडेटा को छोड़ देता है और प्रायिकता विश्लेषण का उपयोग करता है। कैश लोकैलिटी, म्यूटेशन और प्रमाण आवश्यकताओं पर एक साथ चर्चा करें।
उच्च गुणवत्ता वाला नमूना उत्तर
मैं सबसे छोटी कुंजी को रूट पर रखता हूं। meld गैर-रिक्त पेड़ लौटाता है, रूट्स को स्वैप करता है ताकि a छोटा हो, और बेतरतीब ढंग से b को a.left या a.right में मर्ज करता है। insert और extract-min दोनों meld का पुन: उपयोग करते हैं, जबकि find-min रूट को पढ़ता है। मैं पहले स्पष्ट करता हूं कि क्या मेल्ड इनपुट का उपभोग करता है; फिर मैं अंतर परीक्षणों के लिए एक नियतात्मक रैंडम स्रोत इंजेक्ट करता हूं, साइकिल, काउंट, ओनरशिप और रूट ऑर्डर की जांच करता हूं। मैं रैंडम मॉडल के तहत अपेक्षित या उच्च-प्रायिकता लॉगरिदमिक सीमाओं का वर्णन करता हूं और रिकर्शन गहराई को अलग से संभालता हूं।
सामान्य गलतियाँ
- रूट्स की तुलना करने से पहले यादृच्छिकीकरण करना → परिणामी रूट बहुत बड़ा हो सकता है → पहले रूट्स को स्वैप करें, फिर एक चाइल्ड चुनें।
- मेल्ड के बाद पुराने म्यूटेबल हीप का पुन: उपयोग करना → एक नोड को दो पैरेंट्स मिल जाते हैं → उपभोग बताएं या पर्सिस्टेंस लागू करें।
- अपेक्षित सीमा को सबसे खराब स्थिति O(log n) कहना → प्रायिकता की धारणा समाप्त हो जाती है → रैंडम मॉडल और उच्च-प्रायिकता क्वालीफायर का नाम बताएं।
- एक गैर-इंजेक्टेबल रैंडम स्रोत का उपयोग करना → विफलताओं को दोहराया नहीं जा सकता है → इसे इंजेक्ट करें और परीक्षणों में बीज को ठीक करें।
- रिकर्शन गहराई को अनदेखा करना → एक अत्यधिक असंतुलित पेड़ कॉल स्टैक को समाप्त कर सकता है → एक स्पष्ट स्टैक का उपयोग करें, गहराई की निगरानी करें, या सीमाओं का दस्तावेजीकरण करें।
फॉलो-अप प्रश्न और उत्तर
फॉलो-अप 1: आप परीक्षणों को नियतात्मक (deterministic) कैसे बनाते हैं?
रैंडम-बिट जनरेटर को हीप की निर्भरता (dependency) बनाएं। परीक्षण एक निश्चित अनुक्रम या बीज प्रदान करते हैं, जबकि प्रोडक्शन एक स्वतंत्र उदाहरण का उपयोग करता है ताकि वैश्विक रैंडम स्थिति परीक्षण मामलों को युग्मित (couple) न कर सके।
फॉलो-अप 2: क्या होगा यदि मेल्ड को दोनों इनपुट संरक्षित करने होंगे?
पाथ कॉपिंग और अप्रभावित सबट्री को साझा करने के साथ एक पर्सिस्टेंट कार्यान्वयन का उपयोग करें। स्पेस बाउंड और मेमोरी-रिक्लेमेशन योजना को अपडेट करें; इन-प्लेस मर्ज के लिए निरंतर अतिरिक्त स्थान का दावा न करें।
फॉलो-अप 3: क्या होगा यदि दोनों हीप एक ही नोड को संदर्भित करते हैं?
एक म्यूटेबल एपीआई को क्रॉस-हीप शेयरिंग को अस्वीकार करना चाहिए और डिबग बिल्ड में ओनरशिप रिकॉर्ड करनी चाहिए। एक पर्सिस्टेंट एपीआई संरचना को केवल तभी साझा कर सकता है जब नोड्स इम्यूटिएबल हों। अलियास को चुपचाप ठीक करने के बजाय एक ओनरशिप त्रुटि लौटाएं।
फॉलो-अप 4: पेयरिंग हीप का उपयोग क्यों न करें?
एक पेयरिंग हीप decrease-key की आवश्यकता वाले वर्कलोड के लिए उपयुक्त है, लेकिन यह मल्टीवे चाइल्ड सूचियों और विलोपन पुनर्गठन को बनाए रखता है। एक रैंडमाइज्ड मेल्डेबल हीप में उन वर्कलोड के लिए एक छोटा बाइनरी meld होता है, जिन्हें संभाव्य गारंटी स्वीकार करते हुए मर्ज, इंसर्ट और न्यूनतम हटाने की आवश्यकता होती है।