1. प्रश्न
आपको एक ऐसे क्रमित डिक्शनरी की आवश्यकता है जो कुंजी लुकअप, इंसर्शन, विलोपन और रेंज स्कैन का समर्थन करती हो। डेटा सेट गतिशील रूप से बढ़ता है, और साक्षात्कारकर्ता AVL या रेड-ब्लैक ट्री की आवश्यकता के बिना O(log N) के करीब औसत संचालन चाहता है। एक स्किप लिस्ट डिज़ाइन करें और यादृच्छिकता (randomness), सीमाओं और मेमोरी लेआउट का विश्लेषण करें।
2. बाधाएं और स्पष्टीकरण
- तय करें कि क्या कुंजियाँ अद्वितीय (unique) हैं; यदि नहीं, तो ओवरराइट, गिनती या स्थिर क्रमबद्धता को परिभाषित करें।
- एक अधिकतम स्तर और पदोन्नति प्रायिकता (promotion probability)
pचुनें; नीचे की लिंक्ड लिस्ट से ऊपर की ओर इंडेक्स बनाएं। - खोज, इंसर्शन और विलोपन प्रत्येक स्तर के लिए एक पूर्ववर्ती (predecessor) बनाए रखते हैं; रेंज पुनरावृत्ति सबसे नीचे की लिस्ट का अनुसरण करती है।
- पहले सिंगल-थ्रेडेड संरचना पर चर्चा करें। समवर्तीता (concurrency) के लिए अतिरिक्त लॉकिंग, संस्करण नियंत्रण (versioning), या लॉक-मुक्त एल्गोरिदम के प्रमाण की आवश्यकता होती है।
3. मुख्य विचार
प्रत्येक नोड में फॉरवर्ड पॉइंटर्स का एक यादृच्छिक आकार का ऐरे होता है। खोज उच्चतम स्तर के शीर्ष (head) से शुरू होती है: जब तक अगली कुंजी लक्ष्य से कम हो, आगे बढ़ें; अन्यथा एक स्तर नीचे उतरें। इंसर्शन पूर्ववर्तियों को रिकॉर्ड करता है, एक यादृच्छिक ऊंचाई चुनता है, और नोड को प्रत्येक स्तर में जोड़ता है। विलोपन इसे अनलिंक करने के लिए उसी पूर्ववर्ती ऐरे का उपयोग करता है। विरल (sparse) ऊपरी स्तर O(N) अपेक्षित पॉइंटर्स और O(log N) अपेक्षित खोज, इंसर्शन और विलोपन प्रदान करते हैं।
4. संदर्भ कार्यान्वयन
randomLevel(rng, p, maxLevel):
level = 1
while level < maxLevel and rng.uniform01() < p:
level += 1
return level
findPredecessors(key):
update = array(maxLevel)
node = head
for level from maxLevel - 1 down to 0:
while node.forward[level] != nil and node.forward[level].key < key:
node = node.forward[level]
update[level] = node
return update
insert(key, value):
update = findPredecessors(key)
if update[0].forward[0].key == key:
update[0].forward[0].value = value
return
node = Node(key, value, randomLevel(rng, p, maxLevel))
for level in 0 .. node.height - 1:
node.forward[level] = update[level].forward[level]
update[level].forward[level] = nodeकुंजी पढ़ने से पहले nil की जाँच करें और सुनिश्चित करें कि नई ऊंचाई कभी भी maxLevel से अधिक न हो। विलोपन लक्ष्य की ओर इशारा करने वाले प्रत्येक स्तर को उसके उत्तराधिकारी (successor) के साथ फिर से जोड़ता है। यदि उच्चतम स्तर खाली हो जाता है, तो नोड्स को स्थानांतरित किए बिना सक्रिय स्तर की संख्या को कम करें।
5. जटिलता और सबसे खराब मामला
एक निश्चित पदोन्नति प्रायिकता और स्वतंत्र यादृच्छिक स्रोत के साथ, स्तर और पथ की लंबाई अपेक्षा में लघुगणकीय (logarithmic) होती है और अपेक्षित स्थान O(N) होता है। यदि यादृच्छिकता विफल हो जाती है या कोई प्रतिकूल (adversary) स्तरों की भविष्यवाणी कर सकता है, तो संरचना एक लिंक्ड लिस्ट में बदल सकती है और संचालन O(N) हो जाते हैं। उच्च-गुणवत्ता वाले यादृच्छिक स्रोत का उपयोग करें, ऊंचाई को सीमित करें, समय-समय पर पुनर्निर्माण करें, या प्रतिकूल वर्कलोड के लिए नियतात्मक संतुलित ट्री (deterministic balanced tree) चुनें।
6. सत्यापन और समवर्ती ट्रेड-ऑफ
- लुकअप, अपडेट, विलोपन और रेंज पुनरावृत्ति के लिए क्रमित, डुप्लिकेट, खाली और चरम कुंजियों का परीक्षण करें।
- कई N मानों में ऊंचाई वितरण, औसत पथ लंबाई और पॉइंटर गणना को मापें।
- एक संदर्भ क्रमित मैप के विरुद्ध यादृच्छिक संचालन अनुक्रमों को दोबारा चलाएं और सामग्री तथा क्रम की तुलना करें।
- समवर्तीता के लिए, लॉक ग्रैन्युलैरिटी, तार्किक विलोपन (logical deletion), मेमोरी रिक्लेमेशन, और ABA जोखिम की व्याख्या करें; पॉइंटर राइट्स को एक लॉक में लपेटना लॉक-मुक्त डिज़ाइन नहीं है।
7. सामान्य गलतियाँ
- पूर्ववर्ती ऐरे के बिना खोज को लागू करना, जिससे इंसर्शन या विलोपन को लिस्ट को फिर से स्कैन करने के लिए मजबूर होना पड़ता है।
- डुप्लिकेट-कुंजी नीति की अनदेखी करना और अस्थिर रेंज क्रम उत्पन्न करना।
- यादृच्छिकता और प्रतिकूल इनपुट पर चर्चा किए बिना अपेक्षित
O(log N)को सबसे खराब स्थिति की गारंटी के रूप में मानना। - एक निश्चित ऊंचाई वाले ऐरे का उपयोग करना जो मेमोरी बर्बाद करता है या असीमित ऊंचाइयों की अनुमति देना जो ऐरे को ओवरफ्लो कर देता है।
8. साक्षात्कार स्कोरिंग बिंदु
उच्च स्तरों से नीचे की ओर खोज करता है
उम्मीदवार प्रत्येक स्तर की आगे बढ़ने की स्थिति, कब नीचे उतरना है, और सबसे निचली सूची में प्रत्येक तत्व क्यों शामिल है, इसकी व्याख्या करता है।
पूर्ववर्तियों को सही ढंग से बनाए रखता है
उम्मीदवार प्रत्येक स्तर के लिए एक अपडेट ऐरे संग्रहीत करता है और ओवरराइट, निल (nil) पॉइंटर्स, और उच्चतम सक्रिय स्तर को छोटा करने का प्रबंधन करता है।
संभाव्य जटिलता की व्याख्या करता है
उम्मीदवार अपेक्षित O(log N) समय, अपेक्षित O(N) स्थान, और O(N) डिजनरेशन का कारण बनने वाली स्थितियों का उल्लेख करता है।
समवर्ती सीमाओं की पहचान करता है
उम्मीदवार सिंगल-थ्रेडेड कोड को समवर्ती मानने के बजाय लॉक, संस्करण, तार्किक विलोपन, मेमोरी रिक्लेमेशन और ABA पर चर्चा करता है।