कोडिंग इंटरव्यू: आप Search, Insert और Delete के साथ Skip List कैसे लागू करते हैं?

प्रांप्ट और कार्यक्षेत्र

search, insert, और delete के साथ पूर्णांक कुंजियों का एक ऑर्डर्ड सेट लागू करें। संरचना को अपेक्षित O(log n) ऑपरेशनों का उपयोग करना चाहिए और एक संतुलित ट्री (balanced tree) द्वारा आवश्यक रोटेशन से बचना चाहिए। बताएं कि डुप्लिकेट्स को अस्वीकार किया जाता है या गिना जाता है; यह लेख एक सेट चुनता है, इसलिए मौजूदा कुंजी को सम्मिलित करना एक no-op है।

यह प्रश्न सार्वजनिक साक्षात्कार रिपोर्टों और कार्यान्वयन चर्चाओं में दिखाई देता है, जिसमें एक Google साक्षात्कार प्रांप्ट और एक LeetCode साक्षात्कार पोस्ट शामिल हैं। कोडिंग सिग्नल कई फॉरवर्ड-पॉइंटर स्तरों को बनाए रखना और उनके इन्वेरिएंट्स को सिद्ध करना है, न कि किसी लाइब्रेरी क्लास को याद रखना।

साक्षात्कारकर्ता क्या मूल्यांकन करता है

• क्या आप लेवल शून्य को पूर्ण सॉर्ट की गई सूची के रूप में और प्रत्येक उच्च स्तर को इसके उप-अनुक्रम (subsequence) के रूप में रखते हैं।
• क्या प्रविष्टि और विलोपन बेस-लिस्ट लिंक को खोए बिना प्रत्येक पूर्ववर्ती (predecessor) स्तर को अपडेट करते हैं।
• क्या आप अपेक्षित O(log n) को एक दुर्भाग्यपूर्ण O(n) ऑपरेशन से अलग करते हैं और रैंडम-लेवल सीमाओं का परीक्षण करते हैं।

Redis एक सॉर्टेड-सेट एन्कोडिंग के लिए स्किप-लिस्ट प्रतिनिधित्व का उपयोग करता है, जबकि MIT के एल्गोरिदम नोट्स प्रोबेबिलिस्टिक विश्लेषण का वर्णन करते हैं। वे कार्यान्वयन और सैद्धांतिक प्रमाण हैं; उनका यह अर्थ नहीं है कि प्रत्येक वर्कलोड को ट्री के स्थान पर स्किप लिस्ट का उपयोग करना चाहिए।

उत्तर देने से पहले स्पष्टीकरण

1. सेट या मल्टीसेट? एक सेट डुप्लिकेट कुंजियों को अस्वीकार करता है; एक मल्टीसेट को गिनती या अद्वितीय नोड पहचान की आवश्यकता होती है।
2. क्या कॉलर्स को रैंक या रेंज प्रश्नों की आवश्यकता है? रैंक के लिए स्पैन या चौड़ाई मेटाडेटा की आवश्यकता होती है; आधार प्रश्न के लिए केवल सदस्यता (membership) की आवश्यकता होती है।
3. क्या डिटर्मिनिस्टिक रीप्ले की आवश्यकता है? परीक्षणों के लिए एक सीडेड रैंडम स्रोत इंजेक्ट करें, जबकि प्रोडक्शन एक निष्पक्ष जनरेटर का उपयोग करता है।
4. मेमोरी सीमा क्या है? प्रत्येक नोड में फॉरवर्ड पॉइंटर्स की एक परिवर्तनीय संख्या होती है, इसलिए स्तर की सीमा और प्रायिकता मेमोरी को प्रभावित करती है।

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

“मैं प्रत्येक स्तर के लिए एक फॉरवर्ड पॉइंटर और एक सॉर्ट की गई लेवल-शून्य सूची के साथ एक सेंटिनल (sentinel) रखता हूँ। खोज उच्चतम स्तर से शुरू होती है और तब तक आगे बढ़ती है जब तक कि अगली कुंजी छोटी हो; यह प्रत्येक स्तर पर अंतिम पूर्ववर्ती को रिकॉर्ड करती है। इन्सर्ट एक यादृच्छिक ऊंचाई चुनता है, उन पूर्ववर्तियों के बाद नए नोड को जोड़ता है, और मौजूदा कुंजी के लिए कुछ नहीं करता है। डिलीट उसी पूर्ववर्ती सरणी का उपयोग करता है और लक्ष्य नोड को प्रत्येक स्तर पर अनलिंक करता है जहाँ वह दिखाई देता है, फिर शीर्ष सूचियों के खाली होने पर सक्रिय ऊंचाई को कम करता है। ज्यामितीय ऊंचाई प्रायिकता के साथ, खोज, प्रविष्टि और विलोपन अपेक्षित O(log n) हैं और स्थान अपेक्षित O(n) है; एक पैथोलॉजिकल रैंडम अनुक्रम अभी भी O(n) ले सकता है।”

चरण-दर-चरण विस्तृत उत्तर

चरण 1: इन्वेरिएंट को परिभाषित करें।

लेवल शून्य में प्रत्येक कुंजी सख्ती से बढ़ते क्रम में होती है। स्तर i + 1 स्तर i का एक उप-अनुक्रम है, और प्रत्येक नोड के फॉरवर्ड पॉइंटर्स कुंजी द्वारा क्रमित होते हैं। एक सेंटिनल में MAX_LEVEL पॉइंटर्स होते हैं और कोई यूजर कुंजी नहीं होती है। सक्रिय स्तर उच्चतम गैर-रिक्त सूची है।

चरण 2: पूर्ववर्तियों को एकत्र करते हुए खोजें।

सेंटिनल के उच्चतम सक्रिय स्तर से प्रारंभ करें। आगे बढ़ें जब तक कि अगला नोड मौजूद हो और उसकी कुंजी लक्ष्य से कम हो। एक स्तर नीचे जाएं और जारी रखें। देखे गए अंतिम नोड को update[i] में संग्रहीत करें; स्तर शून्य के बाद, update[0].next[0] या तो लक्ष्य है या इसकी प्रविष्टि स्थिति है।

चरण 3: एक यादृच्छिक ऊंचाई के साथ इन्सर्ट करें।

एक ज्यामितीय ऊंचाई प्राप्त करें, उदाहरण के लिए p = 1/2 प्रायिकता के साथ बार-बार प्रमोट करके, जो MAX_LEVEL पर सीमित हो। यदि स्तर शून्य पर उम्मीदवार के पास कुंजी है, तो false लौटाएं। नई ऊंचाई से नीचे के प्रत्येक स्तर के लिए, नए नोड के पॉइंटर को पूर्ववर्ती के अगले पॉइंटर पर सेट करें, फिर पूर्ववर्ती को नए नोड पर इंगित करें। यदि आवश्यक हो तो सक्रिय स्तर का विस्तार करें।

type Node = { key: number; next: Array<Node | null> };

class SkipSet {
  private readonly maxLevel = 16;
  private readonly head: Node = { key: Number.NEGATIVE_INFINITY, next: [] };
  private level = 1;

  constructor() {
    this.head.next = Array(this.maxLevel).fill(null);
  }

  private randomLevel(): number {
    let h = 1;
    while (h < this.maxLevel && Math.random() < 0.5) h += 1;
    return h;
  }

  search(key: number): boolean {
    let node = this.head;
    for (let i = this.level - 1; i >= 0; i -= 1) {
      while (node.next[i] && node.next[i]!.key < key) node = node.next[i]!;
    }
    return node.next[0]?.key === key;
  }

  insert(key: number): boolean {
    const update = Array<Node>(this.maxLevel);
    let node = this.head;
    for (let i = this.level - 1; i >= 0; i -= 1) {
      while (node.next[i] && node.next[i]!.key < key) node = node.next[i]!;
      update[i] = node;
    }
    if (update[0].next[0]?.key === key) return false;
    const height = this.randomLevel();
    if (height > this.level) {
      for (let i = this.level; i < height; i += 1) update[i] = this.head;
      this.level = height;
    }
    const fresh: Node = { key, next: Array(height).fill(null) };
    for (let i = 0; i < height; i += 1) {
      fresh.next[i] = update[i].next[i];
      update[i].next[i] = fresh;
    }
    return true;
  }

  delete(key: number): boolean {
    const update = Array<Node>(this.maxLevel);
    let node = this.head;
    for (let i = this.level - 1; i >= 0; i -= 1) {
      while (node.next[i] && node.next[i]!.key < key) node = node.next[i]!;
      update[i] = node;
    }
    const target = update[0].next[0];
    if (!target || target.key !== key) return false;
    for (let i = 0; i < this.level; i += 1) {
      if (update[i].next[i] !== target) break;
      update[i].next[i] = target.next[i] ?? null;
    }
    while (this.level > 1 && !this.head.next[this.level - 1]) this.level -= 1;
    return true;
  }
}

चरण 4: लक्षित नोड की प्रत्येक उपस्थिति को हटाएं।

पूर्ववर्ती सरणी प्रत्येक स्तर पर लक्ष्य के पूर्ववर्ती की पहचान करती है। केवल उन स्तरों को अनलिंक करें जहाँ update[i].next[i] वह लक्ष्य है; उच्च स्तरों में यह शामिल नहीं हो सकता है। बाद में, जब तक सेंटिनल का शीर्ष पॉइंटर खाली हो, सक्रिय स्तर को कम करें।

चरण 5: जटिलता और मेमोरी का विश्लेषण करें।

प्रमोशन प्रायिकता p के शून्य और एक के बीच सख्ती से होने पर, अपेक्षित ऊंचाई स्थिर होती है और अपेक्षित खोज पथ की लंबाई लघुगणकीय (logarithmic) होती है। खोज, प्रविष्टि और विलोपन अपेक्षित O(log n) हैं; एक खराब यादृच्छिक अनुक्रम में O(n) सबसे खराब स्थिति होती है। अपेक्षित पॉइंटर संख्या स्थिरांकों तक n/(1-p) है, इसलिए p = 1/2 छोटे पथों के लिए प्रति नोड लगभग दो पॉइंटर्स का व्यापार करता है।

चरण 6: संरचना, यादृच्छिकता और सीमाओं का परीक्षण करें।

परीक्षणों में एक सीडेड जनरेटर का उपयोग करें। खाली खोज/हटाने, पहली और आखिरी कुंजियों, डुप्लिकेट्स, एकमात्र नोड को हटाने, स्तरों के पार हटाने, नकारात्मक मानों और बार-बार प्रविष्टि/विलोपन चक्रों की जांच करें। प्रत्येक ऑपरेशन के बाद, स्तर शून्य को पार करें और एक संदर्भ Set के साथ तुलना करें; सत्यापित करें कि प्रत्येक उच्च स्तर सॉर्ट किया गया है और प्रत्येक नोड स्तर शून्य पर भी दिखाई देता है। ऊंचाई और पॉइंटर भ्रष्टाचार को पकड़ने के लिए कई बीजों (seeds) को चलाएं।

उच्च-गुणवत्ता वाला नमूना उत्तर

“मैं एक सेंटिनल और एक सॉर्ट की गई स्तर-शून्य श्रृंखला के साथ एक सेट का मॉडल तैयार करता हूँ। प्रत्येक उच्च स्तर स्तर शून्य का एक उप-अनुक्रम है। खोज उच्चतम सक्रिय स्तर से नीचे उतरती है और प्रत्येक स्तर पर पूर्ववर्ती को रिकॉर्ड करती है। प्रविष्टि एक मौजूदा कुंजी को अस्वीकार करती है, एक ज्यामितीय यादृच्छिक ऊंचाई चुनती है, और नोड को उन पूर्ववर्तियों के बाद जोड़ती है। विलोपन उसी पूर्ववर्ती सरणी को ढूंढता है, लक्ष्य को प्रत्येक स्तर से अनलिंक करता है जहाँ वह दिखाई देता है, और खाली शीर्ष स्तरों को छोटा करता है।

ऑपरेशन्स अपेक्षित O(log n) के साथ O(n) अपेक्षित स्थान के हैं, लेकिन O(n) सबसे खराब स्थिति का समय अभी भी संभव है जब यादृच्छिक ऊंचाई दुर्भाग्यपूर्ण हो। मैं नियतात्मक (deterministic) परीक्षणों के लिए एक सीडेड रैंडम स्रोत का उपयोग करूंगा, प्रत्येक ऑपरेशन के बाद स्तर शून्य की तुलना एक संदर्भ सेट से करूंगा, और सभी ऊपरी स्तरों के लिए सॉर्टेडनेस और सबसीक्वेंस इन्वेरिएंट्स का दावा (assert) करूंगा।”

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

• केवल स्तर शून्य को अपडेट करना → उच्च-स्तरीय खोज कुंजी को छोड़ सकती है या बनाए रख सकती है → नोड वाले प्रत्येक स्तर को जोड़ें या अनलिंक करें।
• यादृच्छिक ऊंचाई को गारंटी के रूप में मानना → एक पैथोलॉजिकल अनुक्रम एक रैखिक पथ उत्पन्न कर सकता है → अपेक्षित और सबसे खराब स्थिति की सीमाओं को बताएं।
• अनजाने में डुप्लिकेट नोड्स की अनुमति देना → खोज और विलोपन सिमेंटिक्स अस्पष्ट हो जाते हैं → कोडिंग से पहले सेट या मल्टीसेट व्यवहार चुनें।
• खाली शीर्ष स्तरों को छोटा करने में विफल होना → खोजें बासी स्तरों का निरीक्षण करती हैं और बहीखाता भटक जाता है → विलोपन के बाद सक्रिय स्तर को कम करें।
• केवल अंतिम सदस्यता का परीक्षण करना → एक दूषित ऊपरी पॉइंटर छिपा रह सकता है → प्रत्येक ऑपरेशन के बाद क्रम और उप-अनुक्रम इन्वेरिएंट्स की जांच करें।

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

फॉलो-अप 1: आप डुप्लिकेट कुंजियों का समर्थन कैसे करेंगे?

एक अनुबंध चुनें। एक मल्टीसेट प्रत्येक कुंजी नोड में एक गिनती संग्रहीत कर सकता है, जिससे बार-बार प्रविष्टि और विलोपन गिनती को अपडेट करते हैं, या तुलना कुंजी में एक अद्वितीय अनुक्रम संख्या संग्रहीत कर सकते हैं। मेमोरी अनुमति देने पर नोड्स की गणना करें; किसी विशिष्ट घटना को हटाते समय अद्वितीय पहचान उपयोगी होती है।

फॉलो-अप 2: आप रैंक क्वेरी कैसे जोड़ते हैं?

प्रत्येक फॉरवर्ड पॉइंटर के पास एक स्पैन या चौड़ाई स्टोर करें। खोज के दौरान, जैसे-जैसे आप दाईं ओर बढ़ते हैं, स्पैन जमा करते जाएं; प्रविष्टि और विलोपन प्रत्येक स्तर पर प्रभावित स्पैन को अपडेट करते हैं। सरल सेट कार्यान्वयन में लघुगणकीय समय में रैंक का उत्तर देने के लिए पर्याप्त मेटाडेटा नहीं होता है।

फॉलो-अप 3: आप इसके बजाय एक संतुलित ट्री कब चुनेंगे?

एक संतुलित ट्री का उपयोग तब करें जब सबसे खराब स्थिति की सीमाएं, नियतात्मक पुनरावृत्ति आकार, या समृद्ध ऑर्डर्ड ऑपरेशन्स कार्यान्वयन की सादगी से अधिक मायने रखते हैं। एक स्किप लिस्ट तब उपयुक्त होती है जब अपेक्षित लघुगणकीय प्रदर्शन, आसान समवर्ती (concurrent) वेरिएंट, या पॉइंटर-आधारित ऑर्डर्ड इंडेक्स स्वीकार्य हो। यह दावा करने के बजाय कि एक संरचना सार्वभौमिक रूप से तेज़ है, मेमोरी ओवरहेड और वर्कलोड को मापें।