प्रॉम्प्ट और संदर्भ
आपको /api, /api/users और /api/users/admin जैसी स्ट्रिंग कुंजियाँ (keys) दी गई हैं। एक रेडिक्स ट्री लागू करें जिसमें प्रत्येक एज एक गैर-खाली स्ट्रिंग संग्रहीत करता हो और प्रत्येक नोड एक मान रख सके। insert(key, value), get(key), longestPrefix(key) और delete(key) का समर्थन करें। खाली कुंजियों की अनुमति केवल रूट मान के रूप में है। इंटरव्यूअर डेटा संरचना और उसके पीछे का तर्क चाहता है, न कि कोई लाइब्रेरी कॉल।
इंटरव्यूअर क्या मूल्यांकन कर रहा है
- क्या आप इस इनवेरिएंट को बनाए रखते हैं कि प्रत्येक नॉन-रूट एज लेबल गैर-खाली हो और सहोदरों (siblings) के पहले वर्ण भिन्न हों?
- क्या आप किसी भी सब-ट्री या मान को खोए बिना पहले बेमेल (mismatch) पर एक एज को विभाजित कर सकते हैं?
- क्या आप सटीक लुकअप और लॉन्गेस्ट-प्रीफिक्स लुकअप में अंतर कर सकते हैं?
- क्या आप डिलीट करने के बाद यूनरी नॉन-वैल्यू नोड्स को कम्प्रेस करते हैं और की (key) की लंबाई के आधार पर वास्तविक जटिलता बताते हैं?
पूछे जाने वाले स्पष्टीकरण प्रश्न
पूछें कि क्या कुंजियाँ बाइट्स हैं या यूनिकोड कोड पॉइंट्स, क्या मिलान केस-सेंसिटिव है, क्या डुप्लिकेट इन्सर्ट मानों को बदल देते हैं, और क्या समवर्ती पहुँच (concurrent access) की आवश्यकता है। पूछें कि क्या longestPrefix मिलान की गई कुंजी, मान या दोनों लौटाता है। बाइट-उन्मुख कार्यान्वयन सबसे सरल है और जटिलता को बाइट्स पर निर्भर बनाता है; जब तक स्पष्ट रूप से आवश्यक न हो, यूनिकोड सामान्यीकरण (normalization) ट्री के बाहर होना चाहिए। यदि समवर्तीता की आवश्यकता है, तो एल्गोरिदम के थ्रेड-सेफ होने का मूक दावा करने के बजाय संरचना के चारों ओर सिंक्रोनाइज़ेशन जोड़ें।
30-सेकंड उत्तर ढांचा
प्रत्येक नोड एक एज लेबल, एक वैकल्पिक मान, और उनके पहले बाइट द्वारा अनुक्रमित (indexed) चाइल्ड नोड्स संग्रहीत करता है। इन्सर्ट के दौरान, शेष कुंजी की तुलना चाइल्ड लेबल से करें। यदि वे पूरी तरह मेल खाते हैं, तो नीचे उतरें; यदि वे आंशिक रूप से मेल खाते हैं, तो चाइल्ड को एक कॉमन-प्रीफिक्स नोड और दो सफ़िक्स नोड्स में विभाजित करें। सटीक लुकअप केवल तभी सफल होता है जब पूरी कुंजी किसी मान वाले नोड पर समाप्त होती है। लॉन्गेस्ट-प्रीफिक्स लुकअप नीचे उतरते समय देखे गए सबसे गहरे मान को याद रखता है। विलोपन (deletion) एक मान को साफ़ करता है और जब नोड में कोई मान नहीं होता है तो उसे उसके एकमात्र चाइल्ड के साथ मर्ज कर देता है।
चरण-दर-चरण गहन विश्लेषण
- इनवेरिएंट बताएं। रूट का कोई एज लेबल नहीं होता है। हर दूसरे नोड का एक गैर-खाली लेबल होता है। एक ही नोड के किन्हीं दो चिल्ड्रेन का पहला बाइट समान नहीं हो सकता। कोई नोड तब भी मान संग्रहीत कर सकता है जब उसके बच्चे भी हों, इसलिए
/apiऔर/api/usersसह-अस्तित्व में रह सकते हैं। - लॉन्गेस्ट कॉमन प्रीफिक्स द्वारा इन्सर्ट करें। शेष कुंजी और चाइल्ड लेबल के बीच सामान्य प्रीफिक्स को
pमान लें। यदिpखाली है, तो कोई दूसरा चाइल्ड चुनें। यदिpचाइल्ड लेबल के बराबर है, तो इसे कंस्यूम करें और पुनरावृत्ति (recurse) करें। यदिpछोटा है, तोpलेबल वाला एक नया पैरेंट बनाएं, पुराने चाइल्ड को उसके सफ़िक्स के नीचे ले जाएं, फिर नई कुंजी का सफ़िक्स संलग्न करें या जब कुंजी विभाजन पर समाप्त होती है तो मान को बदलें। - लुकअप। सटीक लुकअप एक समय में एक एज को पार करता है और बेमेल या अनुपलब्ध चाइल्ड होने पर विफल हो जाता है। लॉन्गेस्ट-प्रीफिक्स लुकअप के लिए, पहले रूट मान रिकॉर्ड करें, फिर कुंजी समाप्त होने से पहले पहुंचे प्रत्येक मान नोड को रिकॉर्ड करें; अंतिम रिकॉर्ड लौटाएँ।
- डिलीट और कम्प्रेस करें। लक्ष्य पर मान साफ़ करें। यदि नोड का कोई मान नहीं है और एक चाइल्ड है, तो दोनों लेबलों को संयोजित (concatenate) करें और चाइल्ड के बच्चों को बढ़ावा दें। यदि इसके कई बच्चे हैं या अभी भी कोई मान है, तो नोड को बनाए रखें। यह सिबलिंग इनवेरिएंट को सुरक्षित रखता है।
- जटिलता। हैश मैप द्वारा चाइल्ड चयन के साथ, प्रत्येक ऑपरेशन अधिकतम इनपुट कुंजी बाइट्स की तुलना करता है, इसलिए समय O(k) प्लस हैश-मैप ओवरहेड है और स्पेस O(कुल संग्रहीत कुंजी बाइट्स) है। पाथ कम्प्रेशन विरल यूनरी नोड्स को कम करता है; यह किसी लंबी कुंजी को कॉन्स्टेंट-टाइम नहीं बनाता है।
- प्रतिकूल मामलों (adversarial cases) का परीक्षण करें। खाली और एकल-वर्ण कुंजियों, किसी मौजूदा कुंजी के प्रीफिक्स वाली कुंजी को इन्सर्ट करना, किसी मौजूदा कुंजी का विस्तार करने वाली कुंजी को इन्सर्ट करना, एज के बीच में विभाजन, डुप्लिकेट रिप्लेसमेंट, लीफ नोड को डिलीट करना, प्रीफिक्स मान को डिलीट करना, एकमात्र कुंजी को डिलीट करना, और बिना मिलान वाले लॉन्गेस्ट-प्रीफिक्स प्रश्नों का परीक्षण करें।
उच्च गुणवत्ता वाला नमूना उत्तर
मैं एक एज को गैर-खाली बाइट स्ट्रिंग के रूप में दर्शाऊंगा और बच्चों को उनके पहले बाइट द्वारा रखूंगा। एकमात्र गैर-तुच्छ (nontrivial) ऑपरेशन इन्सर्ट है: शेष कुंजी के साथ चाइल्ड लेबल की तुलना करें, और पहले बेमेल पर विभाजित करें। वह विभाजन एक कॉमन-प्रीफिक्स नोड बनाता है, पुराने सफ़िक्स और सब-ट्री को बनाए रखता है, और नया सफ़िक्स जोड़ता है। लुकअप पूरे लेबलों का अनुसरण करता है; लॉन्गेस्ट-प्रीफिक्स लुकअप सबसे गहरे नोड को याद रखता है जिसके पास मान है। विलोपन मान को साफ़ करता है और बिना मान वाले नोड को उसके एकमात्र चाइल्ड के साथ मर्ज कर देता है। यहाँ Go-जैसे स्यूडोकोड में मुख्य स्प्लिट आकार दिया गया है:
type node struct {
label string
value any
hasValue bool
child map[byte]*node
}
// When common is shorter than child.label:
parent := &node{label: common, child: map[byte]*node{}}
oldSuffix := child.label[len(common):]
child.label = oldSuffix
parent.child[oldSuffix[0]] = child
parent.child[newSuffix[0]] = &node{label: newSuffix, value: v, hasValue: true}प्रोडक्शन कोड में, मैं newSuffix के खाली होने की स्थिति को मान को parent पर संग्रहीत करके संभालूंगा, और विलोपन के समय केवल तभी मर्ज करूंगा जब hasValue फॉल्स हो और ठीक एक चाइल्ड हो। मैं केवल यह दावा करने के बजाय कि उदाहरण लुकअप सफल होते हैं, प्रत्येक म्यूटेशन के बाद इनवेरिएंट का परीक्षण करूंगा।
सामान्य गलतियाँ
- रेडिक्स ट्री को एक-वर्ण वाले ट्राई नोड्स के रूप में मानना → पाथ कम्प्रेशन खो जाता है → गैर-खाली एज लेबल संग्रहीत करें और पूरे लेबल की तुलना करें।
- एक एज को विभाजित करना लेकिन उसके पुराने मान या बच्चों को छोड़ देना → मौजूदा कुंजियाँ गायब हो जाती हैं → नया सफ़िक्स जोड़ने से पहले पुराने नोड को उसके सफ़िक्स के नीचे ले जाएं।
- लॉन्गेस्ट-प्रीफिक्स लुकअप के लिए पहले मेल खाने वाले मान को लौटाना → अधिक विशिष्ट रूट छूट जाता है → प्रत्येक मान नोड पर उम्मीदवार को अपडेट करते रहें।
- ऐसे नोड को मर्ज करना जिसके पास अभी भी कोई मान है → एक छोटी कुंजी गलती से हट जाती है → केवल मान-रहित यूनरी नोड्स को मर्ज करें।
- O(1) लुकअप का दावा करना → कुंजी की तुलना अभी भी की जानी चाहिए → कुंजी की लंबाई में O(k) बताएं और चाइल्ड-मैप लागतों की व्याख्या करें।
फॉलो-अप प्रश्न और उत्तर
यदि कुंजियाँ केस-इनसेंसिटिव हों तो क्या बदलता है?
एक प्रलेखित नियम, जैसे ASCII लोअरकेस, का उपयोग करके इन्सर्ट और लुकअप से पहले कुंजियों को सामान्यीकृत करें। केवल लुकअप के दौरान सामान्यीकरण न करें; अन्यथा दो वर्तनी असंगत पथों पर कब्जा कर सकती हैं। यूनिकोड केस फोल्डिंग और सामान्यीकरण एक अलग, निर्दिष्ट नीति होनी चाहिए।
आप वाइल्डकार्ड रूट सेगमेंट्स का समर्थन कैसे करेंगे?
एक स्पष्ट प्राथमिकता नियम जोड़ें, उदाहरण के लिए स्थिर एज (static edge) पैरामीटर एज से पहले और पैरामीटर एज कैच-ऑल एज से पहले। रेडिक्स इनवेरिएंट अभी भी लिटरल प्रीफिक्स को संभालता है, लेकिन मिलान एज के प्रकारों पर एक खोज बन जाता है, इसलिए वाइल्डकार्ड शाखाओं की अधिकतम संख्या बताएं और अस्पष्ट मार्गों का परीक्षण करें।
क्या ट्री को समवर्ती रीड और राइट के लिए सुरक्षित बनाया जा सकता है?
रीड-राइट लॉक या कॉपी-ऑन-राइट स्नैपशॉट का उपयोग करें। लॉक-फ्री दावे के लिए मेमोरी-रिक्लेमेशन डिज़ाइन की आवश्यकता होती है; केवल एक एटॉमिक रूट का उपयोग करने से इन-प्लेस स्प्लिट्स और मर्ज सुरक्षित नहीं हो जाते। एल्गोरिथम इनवेरिएंट और सिंक्रोनाइज़ेशन नीति को अलग रखें।