कोडिंग इंटरव्यू: एक Snapshot Array इम्प्लीमेंट करें

समस्या और प्रासंगिक संदर्भ

एक निश्चित लंबाई वाला ऐरे इम्प्लीमेंट करें जो प्रत्येक इंडेक्स पर शून्य से शुरू होता है और तीन ऑपरेशन्स का समर्थन करता है:

• set(index, value) वर्तमान, अभी तक स्नैपशॉट न किए गए वर्ज़न में एक एलिमेंट को बदलता है।
• snap() वर्तमान वर्ज़न को सहेजता है और उसकी ID लौटाता है। IDs 0 से शुरू होती हैं और एक-एक करके बढ़ती हैं।
• get(index, snapId) वह मान लौटाता है जो इंडेक्स index पर तब था जब स्नैपशॉट snapId लिया गया था।

मान लें कि 1 <= length <= 50,000, 0 <= value <= 10^9, इंडेक्स और स्नैपशॉट IDs मान्य हैं, और सभी ऑपरेशन्स को मिलाकर अधिकतम 50,000 कॉल्स की जाती हैं। समाधान में API के व्यवहार और यह दोनों समझाना चाहिए कि इसका संग्रहीत स्टेट प्रत्येक ऐतिहासिक क्वेरी के लिए पर्याप्त क्यों है।

यह कोडिंग और डेटा-स्ट्रक्चर से संबंधित प्रश्न है। यह सार्वजनिक प्रॉम्प्ट वर्तमान इंटरव्यू-अभ्यास संग्रहों में दिखाई देता है, और उपयोगी संकेत यह है कि क्या उम्मीदवार पूरे स्नैपशॉट की प्रतियां बनाने के बजाय इम्यूटबल चेंज रिकॉर्ड्स का उपयोग कर सकता है, और फिर प्रिडिसेसर क्वेरी के साथ सही ऐतिहासिक रिकॉर्ड ढूंढ सकता है।

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

पहला संकेत लागत मॉडलिंग (cost modeling) है। प्रत्येक snap पर सभी length मानों की प्रतिलिपि बनाना समझना आसान है, लेकिन इसमें केवल एक इंडेक्स बदलने पर भी प्रति स्नैपशॉट O(length) टाइम और स्पेस लगता है। 50,000 एलिमेंट्स और 50,000 ऑपरेशन्स के साथ, यह वर्स्ट-केस दिशा अनावश्यक रूप से बड़ी है।

दूसरा संकेत क्वेरी से मेल खाने वाले इंडेक्स का चयन करना है। get हमेशा एक ऐरे इंडेक्स प्रदान करता है, इसलिए प्रति इंडेक्स एक सॉर्टेड परिवर्तन इतिहास (change history) स्टोर करें। इतिहास की प्रविष्टि [s, v] का अर्थ है कि मान v स्नैपशॉट ID s से प्रभावी हुआ। उत्तर सबसे बड़े s <= snapId वाली प्रविष्टि है, जो कि एक मानक प्रिडिसेसर सर्च है।

तीसरा संकेत स्नैपशॉट सिमेंटिक्स है। अगले snap से पहले समान इंडेक्स पर कई set कॉल्स एक ही वर्ज़न से संबंधित होती हैं; केवल अंतिम मान ही शेष रहना चाहिए। समान स्नैपशॉट ID के साथ डुप्लीकेट प्रविष्टियां जोड़ने से स्पेस बर्बाद होता है और इतिहास के इनवेरिएंट (invariant) को स्पष्ट करना कठिन हो सकता है। उन्हें संयोजित (coalesce) करने से IDs कड़ाई से बढ़ती रहती हैं।

अंत में, एक मजबूत उत्तर एक इनवेरिएंट बताता है, बाइनरी सर्च को सिद्ध करता है, और समय की सीमाओं का परीक्षण करता है: प्रारंभिक शून्य, स्नैपशॉट से पहले कई राइट्स, स्नैपशॉट के बाद राइट्स, अछूते इंडेक्स, और विरल (sparse) परिवर्तनों के बीच क्वेरीज़।

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

• क्या snap() ID को आगे बढ़ाने से पहले या बाद में लौटाता है? यह वर्तमान ID लौटाता है, फिर अगले वर्किंग वर्ज़न पर आगे बढ़ता है।
• क्या snap से पहले set को कई बार कॉल किया जा सकता है? हाँ। उस वर्ज़न में किसी इंडेक्स पर किया गया अंतिम राइट मान्य होता है।
• क्या get वर्तमान अनस्नैप किए गए स्टेट को पढ़ सकता है? नहीं। यह पहले के snap() द्वारा लौटाई गई एक मान्य ID प्राप्त करता है।
• क्या लंबाई और इंडेक्स रेंज निश्चित हैं? हाँ। इसमें कोई इंसर्शन, डिलीशन या रीसाइज़िंग नहीं है।
• क्या स्नैपशॉट IDs को स्किप किया जा सकता है? कई लगातार स्नैपशॉट्स में किसी इंडेक्स में कोई बदलाव नहीं हो सकता है, यद्यपि वैश्विक IDs क्रमिक रहती हैं।
• क्या हमें थ्रेड सुरक्षा (thread safety) की आवश्यकता है? इस इन-मेमोरी इंटरव्यू अनुबंध के लिए नहीं। समवर्ती म्यूटेशन (concurrent mutation) के लिए set और snap के चारों ओर बाहरी सिंक्रोनाइज़ेशन की आवश्यकता होगी।
• एक अछूते इंडेक्स को क्या लौटाना चाहिए? प्रत्येक स्नैपशॉट के लिए शून्य।
• क्या प्रोसेस रीस्टार्ट के दौरान पर्सिस्टेंस (स्थायित्व) आवश्यक है? नहीं। वह इस डेटा-स्ट्रक्चर समस्या के बाहर सीरियलाइज़ेशन और ड्यूरेबिलिटी आवश्यकताओं को जोड़ देगा।

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

“मैं पूरे ऐरे की प्रतिलिपि बनाने के बजाय प्रत्येक ऐरे इंडेक्स के लिए एक सॉर्टेड इतिहास रखूंगा। प्रत्येक इतिहास को [0, 0] के साथ इनिशियलाइज़ करें। वर्तमान स्नैपशॉट ID शून्य से शुरू होती है। set पर, अंतिम प्रविष्टि को अधिलेखित (overwrite) करें यदि यह पहले से ही वर्तमान ID से संबंधित है; अन्यथा [currentId, value] अपेंड करें। snap पर, currentId लौटाएं और इसे बढ़ाएं। get पर, उस इंडेक्स के इतिहास में उस पहली प्रविष्टि के लिए बाइनरी-सर्च करें जिसकी ID snapId से बड़ी है, फिर पूर्ववर्ती (preceding) मान लौटाएं। इतिहास में कड़ाई से बढ़ती हुई IDs होती हैं, और सेंटिनल एक प्रिडिसेसर की गारंटी देता है। निर्माण O(length) है, set और snap अमॉर्टाइज़्ड O(1) हैं, get O(log h) है, और u बनाए रखे गए परिवर्तनों के लिए स्पेस O(length + u) है।”

चरण-दर-चरण गहन विश्लेषण

चरण 1: पूर्ण प्रतियों (full copies) को परिमाणित करने के बाद उन्हें अस्वीकार करें।

एक सीधा इम्प्लीमेंटेशन एक म्यूटेबल ऐरे रखता है और प्रत्येक snap पर इसे पूरी तरह से एक सूची में कॉपी करता है। यह set और get के लिए O(1) देता है, लेकिन snap की लागत O(length) होती है और प्रत्येक स्नैपशॉट length मान संग्रहीत करता है। यह अपरिवर्तित इंडेक्स के लिए अनावश्यक लागत चुकाता है।

एक एकल वैश्विक इवेंट लॉग प्रतियों से बचाता है, लेकिन get(index, snapId) असंबंधित इंडेक्स के अपडेट्स के माध्यम से पीछे की ओर स्कैन कर सकता है। क्वेरी पहले से ही एक इंडेक्स का नाम देती है, इसलिए इतिहास को इंडेक्स के अनुसार विभाजित करने से अप्रासंगिक इवेंट्स हट जाते हैं।

चरण 2: परिभाषित करें कि एक इतिहास प्रविष्टि का क्या अर्थ है।

एक इंडेक्स के लिए, मान लें कि इसका बनाए रखा गया इतिहास है:

[[0, 0], [2, 7], [5, 4]]

मान स्नैपशॉट 0 और 1 के लिए 0 है, स्नैपशॉट 2 से 4 के लिए 7 है, और स्नैपशॉट 5 के बाद से 4 है। प्रत्येक प्रविष्टि एक परिवर्तन बिंदु है, न कि एक स्नैपशॉट के लिए एक प्रतिलिपि। इसलिए स्नैपशॉट t के लिए वांछित रिकॉर्ड सबसे दाहिना (rightmost) रिकॉर्ड है जिसकी ID अधिकतम t है।

प्रत्येक इंडेक्स को [0, 0] के साथ इनिशियलाइज़ करें। यह सेंटिनल प्रारंभिक मान को व्यक्त करता है और गारंटी देता है कि प्रत्येक मान्य स्नैपशॉट क्वेरी का एक प्रिडिसेसर हो, इसलिए get को खाली-इतिहास वाली ब्रांच की आवश्यकता नहीं होती है।

चरण 3: वर्तमान वर्ज़न के अंदर राइट्स को संयोजित (coalesce) करें।

पहले snap से पहले, वर्तमान ID 0 है। यदि set(3, 5) के बाद set(3, 8) आता है, तो स्नैपशॉट 0 में 8 होना चाहिए। दूसरा कॉल [0, 5] को [0, 8] से अधिलेखित करता है। snap() द्वारा वर्तमान ID को आगे बढ़ाने के बाद, अगला राइट एक नया रिकॉर्ड जोड़ता है।

यह इस इनवेरिएंट को बनाए रखता है कि प्रत्येक इतिहास में स्नैपशॉट IDs कड़ाई से बढ़ रही हैं और प्रत्येक इतिहास में किसी भी ID के लिए अधिकतम एक रिकॉर्ड होता है। बनाए रखे गए परिवर्तनों की संख्या set कॉल्स की संख्या से अधिक नहीं होती है।

चरण 4: अपर-बाउंड प्रिडिसेसर सर्च इम्प्लीमेंट करें।

type Version = [snapId: number, value: number];

class SnapshotArray {
  private readonly histories: Version[][];
  private currentSnapId = 0;

  constructor(length: number) {
    this.histories = Array.from({ length }, () => [[0, 0]]);
  }

  set(index: number, value: number): void {
    const history = this.histories[index];
    const latest = history[history.length - 1];

    if (latest[0] === this.currentSnapId) {
      latest[1] = value;
    } else {
      history.push([this.currentSnapId, value]);
    }
  }

  snap(): number {
    return this.currentSnapId++;
  }

  get(index: number, snapId: number): number {
    const history = this.histories[index];
    let left = 0;
    let right = history.length;

    while (left < right) {
      const middle = left + Math.floor((right - left) / 2);
      if (history[middle][0] <= snapId) {
        left = middle + 1;
      } else {
        right = middle;
      }
    }

    return history[left - 1][1];
  }
}

सर्च हाफ-ओपन इंटरवल [left, right) का उपयोग करता है। समाप्ति पर, left snapId से बड़ी ID वाली पहली स्थिति है। इसका प्रिडिसेसर अधिकतम snapId ID वाली सबसे दाहिनी प्रविष्टि है। यह वही अपर-बाउंड पार्टीशन है जो मानक बाईसेक्शन लाइब्रेरीज़ द्वारा प्रलेखित है।

चरण 5: इनवेरिएंट से शुद्धता सिद्ध करें।

प्रत्येक इंडेक्स के लिए, रिकॉर्ड्स में कड़ाई से बढ़ती हुई IDs होती हैं। एक रिकॉर्ड [s, v] स्नैपशॉट s लिए जाने से पहले बनाया या अंतिम रूप दिया जाता है और उस इंडेक्स के लिए अगले रिकॉर्ड तक प्रभावी मान बना रहता है। इसलिए, उन रिकॉर्ड्स में से जिनकी IDs किसी अनुरोधित स्नैपशॉट से अधिक नहीं हैं, सबसे बड़ी ID वाला रिकॉर्ड ठीक वही अंतिम राइट है जो उस स्नैपशॉट के लिए दृश्यमान है।

बाइनरी सर्च उस पात्र प्रीफिक्स के बाद पहला रिकॉर्ड लौटाता है, इसलिए left - 1 इसकी सबसे बड़ी ID का चयन करता है। सेंटिनल [0, 0] प्रत्येक मान्य स्नैपशॉट ID के लिए पात्र प्रीफिक्स को गैर-खाली बनाता है। इस प्रकार get आवश्यक मान लौटाता है।

चरण 6: जटिलता का विश्लेषण करें और सीमाओं को सत्यापित करें।

इतिहास बनाने में O(length) समय और स्पेस लगता है। set एक इतिहास के टेल (tail) को अमॉर्टाइज़्ड O(1) समय में पढ़ता या जोड़ता है। snap O(1) है। यदि किसी इंडेक्स में h बनाए रखे गए रिकॉर्ड हैं, तो get की लागत O(log h) होती है। पूरे ऑब्जेक्ट में, स्पेस O(length + u) है, जहां u बनाए रखे गए गैर-सेंटिनल परिवर्तन रिकॉर्ड्स की संख्या है और u अधिकतम set कॉल्स की संख्या है।

कम से कम, इनका परीक्षण करें:

एक यादृच्छिक विभेदक परीक्षण (randomized differential test) इस संरचना की तुलना पूर्ण-प्रतिलिपि बेसलाइन से कर सकता है। बेसलाइन उत्पादन बाधाओं के लिए बहुत महंगी है लेकिन एक सरल और भरोसेमंद परीक्षण ऑरेकल (test oracle) है।

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

“मुख्य क्वेरी एक ज्ञात इंडेक्स के लिए ऐतिहासिक लुकअप है, इसलिए मैं प्रति इंडेक्स एक क्रमित परिवर्तन इतिहास रखूंगा। प्रत्येक इतिहास [0, 0] से शुरू होता है; एक युग्म [s, v] का अर्थ है कि v स्नैपशॉट s से अगले युग्म तक प्रभावी है।

वर्तमान ID शून्य से शुरू होती है। set केवल अंतिम युग्म को देखता है। यदि वह युग्म पहले से ही वर्तमान ID का उपयोग करता है, तो यह मान को बदल देता है क्योंकि स्नैपशॉट से पहले का अंतिम राइट मान्य होता है। अन्यथा यह एक नया युग्म जोड़ता है। snap वर्तमान ID लौटाता है और इसे बढ़ाता है।

get(index, snapId) के लिए, मैं उस इंडेक्स के इतिहास पर एक अपर-बाउंड सर्च चलाता हूँ: अनुरोधित ID से बड़ी ID वाला पहला युग्म ढूंढें और पिछले युग्म का मान लौटाएं। प्रति-इंडेक्स IDs कड़ाई से बढ़ रही हैं, और प्रारंभिक सेंटिनल गारंटी देता है कि प्रिडिसेसर मौजूद है। यह प्रिडिसेसर ठीक वही अंतिम मान है जो अनुरोधित स्नैपशॉट से पहले लिखा गया था।

निर्माण की लागत O(length) है। set और snap अमॉर्टाइज़्ड O(1) हैं, उस इंडेक्स के h परिवर्तन रिकॉर्ड्स के लिए get O(log h) है, और कुल स्पेस O(length + u) है। मैं प्रारंभिक शून्यों, एक स्नैपशॉट से पहले बार-बार किए गए sets, कई स्नैपशॉट्स में विरल परिवर्तनों, बाद के राइट्स के बाद पिछले रीड्स, अछूते इंडेक्स और पूर्ण-प्रतिलिपि ऑरेकल के विरुद्ध यादृच्छिक ट्रेसेज़ का परीक्षण करूंगा।”

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

• प्रत्येक स्नैपशॉट पर पूरे ऐरे की प्रतिलिपि बनाना → समय और स्पेस सभी इंडेक्स के साथ बढ़ते हैं, जिनमें अपरिवर्तित भी शामिल हैं → केवल प्रति-इंडेक्स परिवर्तन बिंदु स्टोर करें।
• एक वैश्विक अपडेट लॉग रखना → एक रीड असंबंधित इंडेक्स को स्कैन कर सकता है → प्रत्येक क्वेरी में दिए गए इंडेक्स द्वारा इतिहास को विभाजित करें।
• प्रत्येक set को अपेंड करना → एक वर्ज़न में बार-बार राइट्स करने से डुप्लीकेट IDs और व्यर्थ रिकॉर्ड्स बनते हैं → जब टेल में वर्तमान ID हो तो उसे अधिलेखित करें।
• एक सटीक स्नैपशॉट ID खोजना → हो सकता है कि उस स्नैपशॉट में कोई इंडेक्स न बदला हो → अनुरोध से कम या उसके बराबर सबसे बड़ी दर्ज ID खोजें।
• लोअर बाउंड का उपयोग करना और इसे सीधे लौटाना → यह बाद के बदलाव की ओर संकेत कर सकता है → अनुरोध पर अपर-बाउंड लागू करें और प्रिडिसेसर लौटाएं।
• इतिहास को खाली शुरू करना → अछूते इंडेक्स के लिए विशेष मामलों की आवश्यकता होती है → प्रत्येक इतिहास को [0, 0] के साथ सीड करें।
• snap से लौटने से पहले इंक्रीमेंट करना → पहली लौटाई गई ID 1 बन जाती है और रिकॉर्ड्स वर्ज़न शिफ्ट कर देते हैं → वर्तमान ID लौटाएं, फिर इंक्रीमेंट करें।
• यह दावा करना कि get O(log length) है → यह एक इंडेक्स के लिए परिवर्तन रिकॉर्ड्स खोजता है → O(log h) बताएं और h को परिभाषित करें।
• केवल प्रकाशित उदाहरण का परीक्षण करना → समान-वर्ज़न अधिलेखन और विरल इतिहास असत्यापित रह जाते हैं → बाउंड्री केसेस और एक विभेदक ऑरेकल जोड़ें।

फॉलो-अप प्रश्न और प्रतिक्रियाएं

फॉलो-अप 1: क्या snap() O(1) हो सकता है यदि स्नैपशॉट को इम्यूटबल होना आवश्यक है?

हाँ। इम्यूटैबिलिटी लॉजिकल है: एक ID लौटाए जाने के बाद, भविष्य के राइट्स एक बड़ी ID के तहत जोड़े जाते हैं और पुरानी IDs से संबंधित रिकॉर्ड्स को कभी म्यूटेट नहीं करते हैं। snap() केवल वर्ज़न बाउंड्री को आगे बढ़ाता है; इसे पूर्ण प्रतिलिपि बनाने की आवश्यकता नहीं है।

फॉलो-अप 2: प्रति स्नैपशॉट एक मैप के बजाय प्रति इंडेक्स इतिहास का उपयोग क्यों करें?

प्रति स्नैपशॉट एक मैप पॉइंट लुकअप को स्नैपशॉट्स में तब तक पीछे की ओर खोजने के लिए मजबूर करता है जब तक कि उसे वह इंडेक्स न मिल जाए। प्रति-इंडेक्स इतिहास पहली क्वेरी कुंजी द्वारा रिकॉर्ड्स को व्यवस्थित करता है, इसलिए get केवल प्रासंगिक परिवर्तनों को खोजता है। एक स्नैपशॉट-उन्मुख मैप तब उपयोगी हो सकता है जब मुख्य क्वेरी हो "स्नैपशॉट s में बदले गए सभी तत्वों की गणना करें," जो कि एक अलग अनुबंध है।

फॉलो-अप 3: क्या get एक मानक-लाइब्रेरी बाइनरी सर्च का उपयोग कर सकता है?

हाँ, जब भाषा किसी कुंजी के लिए सटीक अपर-बाउंड अनुबंध को प्रदर्शित करती है। उदाहरण के लिए, एक राइट-बाईसेक्शन स्थिति snapId के बराबर मौजूदा IDs के बाद इंसर्शन बिंदु होती है; एक घटाने पर प्रिडिसेसर प्राप्त होता है। यह मानने के बजाय कि सभी बाइनरी-सर्च हेल्पर्स समान बाउंड लौटाते हैं, लाइब्रेरी डॉक्यूमेंटेशन में कुंजी निष्कर्षण और समवर्ती व्यवहार की पुष्टि करें।

फॉलो-अप 4: यदि स्नैपशॉट हटाए जा सकते हैं तो क्या बदलता है?

पहले यह परिभाषित करें कि क्या एक ID को हटाने से बाद के स्नैपशॉट्स भी दुर्गम हो जाते हैं या क्या IDs स्थिर रहती हैं। स्थिर IDs के लिए आमतौर पर रेफरेंस काउंटिंग या कॉम्पैक्शन की आवश्यकता होती है जो बनाए रखे गए स्नैपशॉट द्वारा अभी भी सुलभ प्रत्येक मान को सुरक्षित रखती है। बिना सोचे-समझे एक रिकॉर्ड को हटाने से बाद के स्नैपशॉट्स द्वारा इनहेरिट किया गया मान बदल सकता है।

फॉलो-अप 5: आप इस संरचना को कैसे पर्सिस्ट (persist) करेंगे?

(array_id, index, snap_id) द्वारा कुंजित अपेंड-ओनली परिवर्तन रिकॉर्ड स्टोर करें और सभी पूर्ववर्ती राइट्स कमिट होने के बाद ही एक ड्यूरेबल स्नैपशॉट बाउंड्री प्रकाशित करें। रीड्स को (array_id, index, snap_id) पर एक प्रिडिसेसर इंडेक्स की आवश्यकता होती है। रिकवरी, लेनदेन और कॉम्पैक्शन तब इन-मेमोरी इंटरव्यू इम्प्लीमेंटेशन से परे स्टोरेज-सिस्टम की चिंताएं बन जाते हैं।

फॉलो-अप 6: क्या होगा यदि एक छोटे निश्चित ऐरे के लिए रीड्स की संख्या राइट्स से बहुत अधिक हो?

यदि ऐरे छोटा है और स्नैपशॉट लागत की तुलना में O(1) रीड्स अधिक मायने रखते हैं तो पूर्ण प्रतियां उचित हो सकती हैं। वास्तविक लंबाई, स्नैपशॉट संख्या, रीड रेट और मेमोरी बजट की तुलना करें। परिवर्तन-इतिहास डिज़ाइन विरल राइट्स और स्नैपशॉट निर्माण को अनुकूलित करता है; यह प्रत्येक वर्कलोड के लिए स्वतः ही सर्वोत्तम नहीं है।