कोडिंग इंटरव्यू: आप Adaptive Radix Tree को कैसे लागू (implement) करेंगे?

प्रॉम्प्ट और संदर्भ

इंसर्शन, सटीक लुकअप, लॉन्गेस्ट-प्रीफ़िक्स मैचिंग और डिलीशन के साथ वेरिएबल-लेंथ बाइट कीज़ और वैल्यूज़ को स्टोर करने वाला एक ART लागू करें। नोड्स Node4, Node16, Node48 और Node256 के बीच अनुकूलित (adapt) होते हैं; पाथ कम्प्रेशन को की (key) के सिमेंटिक्स को बनाए रखना चाहिए। यह कंप्रेस्ड ट्रीज़, इंडेक्स और मेमोरी लेआउट के बारे में एक coding प्रश्न है।

इंटरव्यूअर क्या मूल्यांकन करता है

1. केवल करैक्टर के बजाय कंप्रेस्ड पाथ, की टर्मिनेशन और आर्बिट्रेरी बाइट्स को हैंडल करना।
2. सभी चार नोड प्रकारों के बीच अपग्रेड और डाउनग्रेड को बनाए रखना।
3. लॉन्गेस्ट-प्रीफ़िक्स मैचिंग को लागू करना और सटीक हिट्स को पूर्वज (ancestor) मानों से अलग करना।
4. यह साबित करना कि डिलीशन कम्प्रेशन इन्वेरिएंट्स को बनाए रखता है।
5. जटिलता (complexity), मेमोरी ट्रेड-ऑफ़ और कॉनकरेंसी की व्याख्या करना।

पूछे जाने वाले स्पष्टीकरण प्रश्न

• क्या कीज़ अपारदर्शी (opaque) बाइट स्ट्रिंग्स हैं और क्या उनमें शून्य बाइट्स (zero bytes) हो सकते हैं?
• क्या कोई इंटरनल नोड वैल्यू रख सकता है, या केवल लीव्स (leaves)?
• लॉन्गेस्ट-प्रीफ़िक्स लुकअप को कौन सी प्रीफ़िक्स लेंथ और शेष भाग लौटाना चाहिए?
• क्या डिलीशन पर तुरंत सिकुड़ना (shrink) आवश्यक है, या रिक्लेमेशन को टाला जा सकता है?
• क्या लॉक-फ्री रीडिंग या स्नैपशॉट पब्लिकेशन की आवश्यकता है?

एक 30-सेकंड का उत्तर

“मैं ओपेक बाइट्स की तुलना करता हूँ और इंटरनल नोड्स पर एक कंप्रेस्ड प्रीफ़िक्स के साथ टर्मिनेशन वैल्यू स्टोर करता हूँ। स्पार्स नोड्स Node4/16 का उपयोग करते हैं; डेंस नोड्स Node48/256 में अपग्रेड हो जाते हैं। डिलीशन डाउनग्रेड करता है और वैल्यू-रहित सिंगल-चाइल्ड पाथ को मर्ज करता है। सटीक लुकअप पूरी की (key) का उपयोग करता है; लॉन्गेस्ट-प्रीफ़िक्स लुकअप निकटतम वैल्यू वाले नोड को रिकॉर्ड करता है। मैं लॉक्स या इम्यूटिएबल स्नैपशॉट्स जोड़ने से पहले एक रेफरेंस मैप के मुकाबले सिंगल-थ्रेडेड इन्वेरिएंट्स को साबित करूँगा।”

गहन उत्तर

चरण 1: नोड्स और लीव्स को परिभाषित करें

एक इंटरनल नोड एक कंप्रेस्ड प्रीफ़िक्स, उसकी लंबाई, एक वैकल्पिक वैल्यू और अगले बाइट द्वारा इंडेक्स किए गए चिल्ड्रन को स्टोर करता है। एक लीफ पूरी की या एक यूनिक वैल्यू रेफरेंस को स्टोर करती है, जो एक की के दूसरी की का प्रीफ़िक्स होने की स्थिति को संभालता है।

Node { prefix, prefixLen, hasValue, value, children }
Leaf  { key, value }

प्रीफ़िक्स की लंबाई स्पष्ट (explicit) है क्योंकि कीज़ आर्बिट्रेरी बाइट्स हैं, नल-टर्मिनेटेड स्ट्रिंग्स नहीं।

चरण 2: इंसर्ट और स्प्लिट करें

नोड प्रीफ़िक्स की तुलना शेष की (key) से करें। यदि यह मेल खाता है, तो जारी रखें या वैल्यू को अपडेट करें। यदि यह अलग होता है, तो कॉमन प्रीफ़िक्स वाला एक पैरेंट बनाएं और पुराने नोड तथा नई लीफ को उनके भिन्न बाइट्स के तहत जोड़ें। यदि नई की कॉमन प्रीफ़िक्स पर समाप्त होती है, तो पैरेंट के वैल्यू फ़्लैग को सेट करें।

चरण 3: एडेप्टिव लेआउट चुनें

Node4 और Node16 कॉम्पैक्ट की और पॉइंटर एरे बनाए रखते हैं; लुकअप उन्हें स्कैन कर सकता है या वेक्टर तुलना का उपयोग कर सकता है। Node48 सभी 256 संभावित बाइट्स को 48 पॉइंटर स्लॉट्स पर मैप करता है, जिससे 256 रेजिडेंट पॉइंटर्स से बचा जा सकता है। Node256 बाइट द्वारा सीधे इंडेक्स करता है। प्रीफ़िक्स या वैल्यू स्थिति को खोए बिना चिल्ड्रन को कॉपी करके अपग्रेड करें।

चरण 4: सटीक और लॉन्गेस्ट-प्रीफ़िक्स लुकअप

सटीक लुकअप को हर की बाइट का उपभोग करना चाहिए और hasValue या एक समान लीफ की को हिट करना चाहिए। लॉन्गेस्ट-प्रीफ़िक्स लुकअप जब भी किसी नोड में वैल्यू होती है तो एक उम्मीदवार को रिकॉर्ड करता है, फिर विफलता या समाप्ति तक अगले बाइट के माध्यम से जारी रहता है और अंतिम उम्मीदवार और उसकी लंबाई लौटाता है।

चरण 5: डिलीट और श्रिंक करें

वैल्यू डिलीट करने के बाद, बिना चिल्ड्रन वाले नोड को हटा दें। यदि बिना वैल्यू वाले नोड का एक चाइल्ड है, तो उसके प्रीफ़िक्स और एज बाइट को चाइल्ड में मर्ज कर दें। प्रलेखित चाइल्ड-काउंट थ्रेसहोल्ड पर Node256, Node48, Node16 और Node4 को डाउनग्रेड करें। मर्ज के दौरान लीफ की पूरी की (key) को सुरक्षित रखें।

चरण 6: इन्वेरिएंट्स और जटिलता

किसी भी रूट-टू-लीफ पाथ पर प्रीफ़िक्स, एज बाइट्स और एक लीफ को जोड़ने से मूल की (original key) का पुनर्निर्माण होना चाहिए। एक इंटरनल नोड में डुप्लिकेट एज बाइट्स नहीं हो सकते; hasValue का अर्थ है कि एक की ठीक वहीं समाप्त होती है। की लंबाई L के साथ, लुकअप O(L) है; एडेप्टिव लेआउट स्पार्स नोड्स के लिए 256 स्लॉट आवंटित करने से बचते हैं।

चरण 7: टेस्ट करें और कॉनकरेंसी जोड़ें

एक रेफरेंस मैप के साथ रैंडमाइज़्ड इंसर्ट, लुकअप, डिलीट और लॉन्गेस्ट-प्रीफ़िक्स ऑपरेशन्स की तुलना करें। इसमें खाली कीज़, ज़ीरो बाइट्स, प्रीफ़िक्स कीज़ और सभी 256 ब्रांचेस शामिल करें। रीड-राइट लॉक के साथ कॉनकरेंट वर्ज़न शुरू करें; केवल उसके बाद ही copy-on-write, epochs या RCU पर विचार करें, क्योंकि लॉक-फ्री पॉइंटर्स को उजागर करने से पहले रिक्लेमेशन सुरक्षित होना चाहिए।

मॉडल उत्तर

“मैं कीज़ को ओपेक बाइट स्ट्रिंग्स के रूप में मानता हूँ। नोड्स कंप्रेस्ड प्रीफ़िक्स, वैकल्पिक टर्मिनेशन वैल्यूज़ और चिल्ड्रन रखते हैं। आंशिक मिलान एक कॉमन-प्रीफ़िक्स पैरेंट को विभाजित करते हैं; चाइल्ड काउंट Node4, 16, 48 और 256 को अपग्रेड करते हैं, जबकि डिलीशन डाउनग्रेड करता है और सिंगल-चाइल्ड पाथ्स को मर्ज करता है। सटीक लुकअप पूरी की का उपयोग करता है; लॉन्गेस्ट-प्रीफ़िक्स लुकअप निकटतम वैल्यू वाले नोड को याद रखता है।

प्रत्येक पाथ को मूल की का पुनर्निर्माण करना चाहिए। रैंडमाइज़्ड टेस्ट एक मैप के खिलाफ तुलना करते हैं और ज़ीरो बाइट्स, खाली कीज़, प्रीफ़िक्स कीज़ और डेंस ब्रांचेस को कवर करते हैं। सिंगल-थ्रेडेड शुद्धता के बाद, एक लॉक का उपयोग करें; copy-on-write या लॉक-फ्री डिज़ाइन को epoch या समकक्ष सुरक्षित रिक्लेमेशन की भी आवश्यकता होती है।”

सामान्य गलतियाँ

• कीज़ को कैरेक्टर के रूप में मानना → बाइनरी कीज़ और ज़ीरो बाइट्स विफल हो जाते हैं → बाइट लंबाई और मानों की तुलना करें।
• इंटरनल वैल्यूज़ को भूल जाना → प्रीफ़िक्स कीज़ मैच नहीं हो सकतीं → hasValue बनाए रखें।
• Node48 को 256 पॉइंटर्स देना → स्पार्स-मेमोरी की बचत खो जाती है → एक इंडेक्स मैप का उपयोग करें।
• मर्ज किए बिना वैल्यूज़ को साफ़ करना → खाली पाथ्स छूट जाते हैं → थ्रेसहोल्ड पर श्रिंक करें।
• पूर्वज उम्मीदवारों की अनदेखी करना → लॉन्गेस्ट-प्रीफ़िक्स लुकअप मैचों को मिस कर देता है → अंतिम वैल्यू वाले नोड को याद रखें।
• सुरक्षित रिक्लेमेशन के बिना रॉ पॉइंटर्स को पब्लिश करना → रीडर्स मुक्त (freed) मेमोरी का उपयोग करते हैं → लॉक्स से शुरू करें, फिर epochs/RCU।

फॉलो-अप प्रश्न और उत्तर

फॉलो-अप 1: हमेशा Node256 का उपयोग क्यों नहीं करते?

अधिकांश नोड्स स्पार्स होते हैं, इसलिए 256 स्लॉट्स मेमोरी बर्बाद करते हैं। एडेप्टिव लेआउट स्पार्स और डेंस क्षेत्रों को संतुलित करते हैं।

फॉलो-अप 2: क्या होगा यदि एक की दूसरी की का प्रीफ़िक्स हो?

छोटी की की वैल्यू को इंटरनल नोड पर स्टोर करें और लंबी की के लिए चिल्ड्रन को बनाए रखें।

फॉलो-अप 3: डिलीशन के बाद आप कब मर्ज करते हैं?

एक चाइल्ड वाले वैल्यू-रहित नोड को उसके प्रीफ़िक्स और एज बाइट को जोड़कर मर्ज करें, जिससे लीफ की सुरक्षित रहे।

फॉलो-अप 4: आप कॉनकरेंट स्नैपशॉट कैसे पब्लिश करेंगे?

एक नए इम्यूटिएबल रूट के लिए copy-on-write का उपयोग करें और epochs या रेफरेंस काउंटिंग के साथ पुराने ट्रीज़ को पुनः प्राप्त (reclaim) करें।