प्रॉम्प्ट और उपयोग के मामले
रेडिक्स हीप मोनोटोन प्रायोरिटी क्यू के लिए एक इंटीजर संरचना है, जो डिक्सट्रा (Dijkstra) जैसे एल्गोरिदम में उपयोगी है जहां निकाली गई कीज़ गैर-घटती (nondecreasing) होती हैं। यह अंतिम निकाली गई कुंजी को एक सीमा के रूप में उपयोग करता है और उच्चतम भिन्न बिट द्वारा बकेटिंग करता है।
इंटरव्यूअर क्या मूल्यांकन करता है
- क्या इंसर्ट की गई कीज़ अंतिम निकाली गई कुंजी द्वारा सीमित हैं।
- क्या उच्चतम भिन्न बिट और बकेट रेंज सही हैं।
- क्या सबसे छोटी गैर-खाली बकेट को नए बेस के साथ पुनर्वितरित (redistribute) किया जाता है।
- क्या बकेट और न्यूनतम-कुंजी इनवेरिएंट बने रहते हैं।
- क्या खाली क्यू, ओवरफ्लो और बैकवर्ड कीज़ को संभाला जाता है।
- क्या पुनर्वितरण और एमॉर्टाइज्ड जटिलता को ईमानदारी से समझाया गया है।
उत्तर देने से पहले स्पष्टीकरण
- क्या कीज़ निश्चित-चौड़ाई वाले अहस्ताक्षरित पूर्णांक (unsigned integers) हैं या मनमानी सटीकता (arbitrary precision) वाली?
- क्या इंसर्ट की गई कुंजी अंतिम निकाली गई कुंजी से छोटी हो सकती है?
- क्या समान-कुंजी वाले पेलोड स्थिर (stable) होने चाहिए?
- क्या केवल
pop-minआवश्यक है, या decrease-key और विलोपन भी? - खाली pop और ओवरफ्लो को क्या वापस लौटाना चाहिए?
- क्या स्पष्टता, कम स्थिर कारक (low constant factor), या स्पर्शोन्मुख सीमा (asymptotic bound) प्राथमिकता है?
30-सेकंड उत्तर ढांचा
"मैं last, जो सबसे हाल ही में निकाली गई कुंजी है, और W+1 बकेट्स बनाए रखता हूँ। last के बराबर की कुंजी बकेट 0 में जाती है; अन्यथा इसकी बकेट bit_length(key XOR last) होती है। यदि बकेट 0 खाली है, तो मैं सबसे छोटी गैर-खाली बकेट ढूंढता हूँ, इसकी न्यूनतम कुंजी को नए last के रूप में स्कैन करता हूँ, उस बकेट को पुनर्वितरित करता हूँ, और बकेट 0 से pop करता हूँ। last से नीचे की कुंजी को अस्वीकार कर दिया जाता है।"
चरण-दर-चरण गहन विश्लेषण
चरण 1: इनवेरिएंट बताएं। last कभी घटता नहीं है, प्रत्येक लंबित कुंजी key >= last को संतुष्ट करती है, और बकेट i में वे कीज़ होती हैं जिनका last से उच्चतम भिन्न बिट i है।
चरण 2: बकेट की गणना करें। जब key == last हो तो इंडेक्स 0 होता है; अन्यथा bit_length(key XOR last) का उपयोग करें। एक W-बिट कुंजी को W+1 बकेट्स की आवश्यकता होती है।
चरण 3: push लागू करें। गैर-ऋणात्मकता, चौड़ाई और key >= last की जाँच करें, फिर (key, value) को इसकी बकेट में रखें; समान कीज़ सह-अस्तित्व में रह सकती हैं।
चरण 4: pop लागू करें। गैर-खाली होने पर बकेट 0 से रिटर्न करें। अन्यथा सबसे निचली गैर-खाली बकेट खोजें, इसकी न्यूनतम कुंजी को स्कैन करें, और इसे last को असाइन करें।
चरण 5: पुनर्वितरण करें। उस बकेट को खाली करें और नए last के सापेक्ष प्रत्येक आइटम के इंडेक्स की पुनर्गणना करें; इंडेक्स घटते हैं और कम से कम एक आइटम बकेट 0 तक पहुंचता है।
चरण 6: सीमाओं को संभालें। परिभाषित खाली परिणाम लौटाएं; अपरिभाषित XOR और इंडेक्स व्यवहार से बचने के लिए चौड़ाई से बाहर या last से नीचे की कीज़ को अस्वीकार करें।
चरण 7: जटिलता बताएं। प्रत्येक आइटम को वर्ड साइज W द्वारा सीमित बार पुनर्वितरित किया जाता है; सामान्य एमॉर्टाइज्ड लागत O(W) है, स्पेस O(n + W) है, और यह सार्वभौमिक रूप से बाइनरी हीप से तेज़ नहीं है।
मॉडल उच्च-गुणवत्ता वाला उत्तर
"मैं 64-बिट अनसाइंड कीज़ और 65 बकेट्स का उपयोग करता हूँ। last शून्य से शुरू होता है; last से नीचे की कुंजी को अस्वीकार कर दिया जाता है, अन्यथा bit_length(key XOR last) इसकी बकेट का चयन करता है। pop बकेट 0 लेता है, या सबसे निचली गैर-खाली बकेट ढूंढता है, इसकी न्यूनतम कुंजी को last में स्कैन करता है, और पुनर्वितरित करता है। समान कीज़ अलग-अलग पेलोड रखती हैं। खाली pop एक खाली मान लौटाता है, और ओवरफ्लो या बैकवर्ड कीज़ विफल हो जाती हैं। प्रत्येक आइटम को केवल एक वर्ड-साइज-सीमित संख्या में पुनर्वितरित किया जाता है, जिसमें आइटम्स और बकेट्स के लिए स्पेस होता है।"
सामान्य गलतियाँ
- बैकवर्ड कीज़ की अनुमति देना → बकेट इनवेरिएंट विफल हो जाते हैं →
key < lastको अस्वीकार करें। - बकेट के लिए
log2(key)का उपयोग करना → वर्तमान बेस की अनदेखी होती है →key XOR lastका उपयोग करें। - पुनर्वितरण के बाद
lastको अपरिवर्तित रखना → निष्कर्षण गलत हो सकता है → पहले न्यूनतम को स्कैन करें। - बकेट में पहला आइटम लेना → यह न्यूनतम नहीं हो सकता है → न्यूनतम कुंजी के लिए स्कैन करें।
- दावा करना कि प्रत्येक ऑपरेशन O(1) है → वर्ड साइज और पुनर्वितरण गायब हो जाते हैं →
Wऔर एमॉर्टाइजेशन मान्यताओं को बताएं।
अनुवर्ती प्रश्न और उत्तर
अनुवर्ती 1: यह डिक्सट्रा (Dijkstra) के लिए उपयुक्त क्यों है?
निकाली गई दूरियां गैर-घटती हैं, और नई उम्मीदवार दूरियां वर्तमान न्यूनतम से कम नहीं हैं, जो मोनोटोन-कुंजी आवश्यकता को पूरा करती हैं।
अनुवर्ती 2: यदि मनमाना decrease-key आवश्यक हो तो क्या होगा?
एक रेडिक्स हीप बैकवर्ड कीज़ के लिए उपयुक्त नहीं है। बाइनरी या पेयरिंग हीप का उपयोग करें, या संस्करण रखें और पुरानी प्रविष्टियों को लेज़ी तरीके से त्यागें।
अनुवर्ती 3: बकेट 0 सीधे pop क्यों कर सकता है?
बकेट 0 में प्रत्येक कुंजी last के बराबर होती है, इसलिए सभी वर्तमान न्यूनतम कीज़ हैं।
अनुवर्ती 4: पुनर्वितरित इंडेक्स क्यों घटते हैं?
नया last बकेट का न्यूनतम है; प्रत्येक अन्य आइटम का उच्चतम भिन्न बिट पुराने बकेट इंडेक्स से बड़ा नहीं है, और कम से कम एक बकेट 0 तक पहुंचता है।
अनुवर्ती 5: आप समान कीज़ को स्थिर कैसे रखते हैं?
पेलोड में एक मोनोटोन अनुक्रम संख्या जोड़ें और बकेट 0 में (key, sequence) चुनें; अन्यथा स्थिरता वैकल्पिक है।
अनुवर्ती 6: ऋणात्मक कीज़ के बारे में क्या?
उन्हें एक अनसाइंड ऑर्डर किए गए स्पेस में मैप करें या केवल गैर-ऋणात्मक कीज़ निर्दिष्ट करें। ऑर्डरिंग परिभाषा के बिना हस्ताक्षरित XOR असुरक्षित है।
अनुवर्ती 7: बाइनरी हीप कब बेहतर होता है?
इसका उपयोग तब करें जब कीज़ मोनोटोन पूर्णांक न हों, वर्ड साइज बड़ा हो, अपडेट जटिल हों, या सरलता और व्यापकता विशिष्ट सीमा से अधिक मायने रखती हो।