कोडिंग साक्षात्कार: आप एक रिज़्यूमेबल (resumable) और सीरियलाइज़ेबल (serializable) इटरेटर कैसे लागू करते हैं?

प्रश्न और संदर्भ

get_state() और set_state() के साथ एक इटरेटर लागू करें: एक सूची से शुरू करें, फिर इसे कई स्रोतों पर समवर्ती पुनरावृत्ति (concurrent iteration) और एसिंक्रोनस रीड्स तक विस्तारित करें। आप स्थिति (state) को कैसे परिभाषित करते हैं, रिकवरी के बाद किसी भी डुप्लिकेट या स्किप न होने की गारंटी कैसे देते हैं, और पूर्णता (completion), विफलताओं और अमान्य स्नैपशॉट को कैसे संभालते हैं?

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

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

• क्या आप hasNext() पर भरोसा करने के बजाय next() के इनपुट, आउटपुट, पूर्णता और त्रुटि सेमेंटिक्स को परिभाषित करते हैं?
• क्या आप रनटाइम ऑब्जेक्ट्स को संरक्षित करने योग्य (persistable) स्थिति से अलग करते हैं?
• क्या आप यह साबित कर सकते हैं कि रिकवरी डिलीवर किए गए किसी भी तत्व को न तो दोहराती है और न ही छोड़ती है?
• क्या आप प्रत्येक स्रोत की प्रगति और वैश्विक शेड्यूलिंग क्रम को ट्रैक करते हैं?
• क्या आप एसिंक रीड्स, रद्दीकरण (cancellation), पुनः प्रयास (retry), और संसाधन क्लीनअप को संभालते हैं?
• क्या आप खाली स्रोतों, अमान्य स्नैपशॉट, स्रोत परिवर्तनों और निष्प्रभावी (idempotent) रिकवरी का परीक्षण करते हैं?

कोडिंग से पहले स्पष्टीकरण हेतु प्रश्न

• क्या कोई स्रोत एक अपरिवर्तनीय (immutable) सूची है, एक अपेंड-ओनली फ़ाइल है, या एक परिवर्तनशील बाहरी स्ट्रीम है? यदि यह बदल सकता है, तो स्नैपशॉट को एक संस्करण (version) या सामग्री फ़िंगरप्रिंट की आवश्यकता होती है।
• क्या रिकवरी अंतिम लौटाए गए मान को दोहराती है या अगले न लौटाए गए मान से शुरू होती है? यह उत्तर बाद वाले का उपयोग करता है और सफल डिलीवरी के बाद ही कर्सर को आगे बढ़ाता है।
• क्या मल्टी-सोर्स क्रम राउंड-रॉबिन है, वैश्विक समय क्रम है, या कोई भी तैयार स्रोत पहले (any-ready-source-first) है? यह विकल्प स्टेट फ़ील्ड्स और निष्पक्षता (fairness) प्रमाण को बदल देता है।
• क्या get_state() को किसी प्रक्रिया (process) या स्कीमा-संस्करण परिवर्तन के बाद भी बने रहना चाहिए? यदि हां, तो केवल संस्करणित स्केलर और स्रोत आईडी संग्रहीत करें, कभी भी फ़ाइल हैंडल, प्रॉमिस या जनरेटर ऑब्जेक्ट संग्रहीत न करें।

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

"मैं पहले चेकपॉइंट को उस तत्व के रूप में परिभाषित करता हूं जिसे अगला next() कॉल लौटाएगा। एक एकल सूची एक इंडेक्स और स्रोत संस्करण संग्रहीत करती है; कई स्रोत प्रत्येक कर्सर और शेड्यूलर स्थिति को संग्रहीत करते हैं। next() केवल सफल डिलीवरी के बाद कर्सर को आगे बढ़ाता है, इसलिए समान स्थिति को पुनर्स्थापित करने से वही तत्व वापस मिलता है और किसी पुष्ट किए गए तत्व को दोहराया नहीं जाता है। स्नैपशॉट संस्करणित JSON है, जिसे पुनर्स्थापना से पहले स्रोत फ़िंगरप्रिंट और सीमाओं के विरुद्ध मान्य किया जाता है। एसिंक संस्करण इन-फ़्लाइट I/O को पुनर्प्राप्ति योग्य स्थिति से अलग करता है, रद्दीकरण, क्लीनअप और प्रति-स्रोत पुनः प्रयास का समर्थन करता है, और कभी भी रनटाइम हैंडल को सीरियलाइज़ नहीं करता है।"

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

चरण 1: न्यूनतम इंटरफ़ेस और चेकपॉइंट परिभाषित करें

hasNext() को जोड़े बिना next(), get_state(), और set_state(state) का उपयोग करें। एक सीमित (finite) इटरेटर एक सुसंगत पूर्ण परिणाम लौटाता है या सहमत पूर्णता अपवाद (exception) उठाता है; कॉल करने वालों को पहले से जांच (probe) करके स्थिति का अनुमान नहीं लगाना चाहिए।

चेकपॉइंट को "अंतिम आइटम" के बजाय "अगले आइटम" पर रखें। एक सूची स्रोत {sourceId, version, index, done} संग्रहीत कर सकता है। next() items[index] को पढ़ता है और मान के सफलतापूर्वक डिलीवर होने के बाद ही इंडेक्स को बढ़ाता है; एक रीड विफलता पुनः प्रयास के लिए स्थिति को अपरिवर्तित छोड़ देती है।

class ListIterator:
    def __init__(self, items, source_id, version):
        self.items = items
        self.source_id = source_id
        self.version = version
        self.index = 0

    def next(self):
        if self.index == len(self.items):
            return {"done": True}
        value = self.items[self.index]
        self.index += 1
        return {"done": False, "value": value}

    def get_state(self):
        return {
            "schema": 1,
            "sourceId": self.source_id,
            "version": self.version,
            "index": self.index,
        }

    def set_state(self, state):
        if state["schema"] != 1 or state["sourceId"] != self.source_id:
            raise ValueError("incompatible state")
        if state["version"] != self.version or not 0 <= state["index"] <= len(self.items):
            raise ValueError("stale or invalid state")
        self.index = state["index"]

चरण 2: इनवेरिएंट बताएं और रिकवरी साबित करें

मुख्य इनवेरिएंट यह है कि index सफलतापूर्वक डिलीवर किए गए तत्वों की संख्या के बराबर है; स्नैपशॉट इंडेक्स इन-मेमोरी कर्सर के बराबर है; और स्रोत संस्करण अपरिवर्तित है। next() केवल मान लौटाने के बाद आगे बढ़ता है, जबकि set_state() केवल मिलान वाले संस्करण और मान्य सीमाओं को स्वीकार करता है, इसलिए वही चेकपॉइंट वही प्रत्यय (suffix) उत्पन्न करता है।

यदि व्यावसायिक अनुबंध ठीक-एक-बार (exactly-once) के बजाय कम-से-कम-एक-बार (at-least-once) है, तो डिलीवरी और चेकपॉइंट के बीच अंतिम आइटम को दोहराना स्वीकार्य है, लेकिन स्थिति में एक पावती मार्कर (acknowledgement marker) या इडेम्पोटेंसी कुंजी शामिल होनी चाहिए। एक ही set_state() अनुबंध में दोनों सेमेंटिक्स को न मिलाएं।

चरण 3: कई स्रोतों तक विस्तार करें

एक कंपोजिट इटरेटर एक स्वतंत्र children[sourceId] स्थिति और शेड्यूलर स्थिति जैसे कि राउंड-रॉबिन कतार, पूर्ण-स्रोत सेट और अनुक्रम संख्या संग्रहीत करता है। राउंड-रॉबिन अगले अधूरे स्रोत को चुनता है; वैश्विक क्रमबद्धता के लिए प्रत्येक स्रोत के पहले से प्राप्त (prefetched) हेड को सहेजने की आवश्यकता होती है ताकि रिकवरी के बाद तुलना को पुनरुत्पादित किया जा सके।

एक मल्टी-सोर्स स्नैपशॉट {schema, children: [{id, state}], scheduler: {kind, cursor}, emitted} हो सकता है। पहले स्रोत सदस्यता और क्रम को मान्य करें, उसके बाद चाइल्ड इटरेटर्स को पुनर्स्थापित करें, और अंत में शेड्यूलर को पुनर्स्थापित करें। एक एकल कुल गणना अपर्याप्त है क्योंकि स्रोत की प्रगति भिन्न होती है।

चरण 4: स्थिति को सीरियलाइज़ेबल और विकासशील बनाएं

केवल स्कीमा संस्करण वाले JSON-आकार के स्केलर, ऐरे और ऑब्जेक्ट्स को बनाए रखें। फ़ाइल हैंडल, नेटवर्क कनेक्शन, लॉक, प्रॉमिस, जनरेटर स्टैक और क्लोजर रनटाइम संसाधन हैं; उन्हें स्नैपशॉट में लिखने के बजाय रिकवरी के दौरान फिर से खोलें या पुनर्निर्मित करें।

जब कोई नया संस्करण किसी पुराने स्नैपशॉट को पढ़ता है, तो एक स्पष्ट माइग्रेशन चलाएं। यदि अनुकूलता अनिश्चित है, तो रिकवरी को अस्वीकार करें और एक सुरक्षित सीमा से पुनः आरंभ करें। यदि स्रोत सामग्री बदल सकती है, तो एक ETag, लंबाई, चंक चेकसम, या लॉजिकल संस्करण संग्रहीत करें ताकि समान इंडेक्स चुपचाप अलग-अलग डेटा को संदर्भित न कर सके।

चरण 5: एसिंक रीड्स, रद्दीकरण और पुनः प्रयास जोड़ें

एक एसिंक next() एक प्रॉमिस लौटाता है और समवर्ती रूप से कई स्रोतों की प्रतीक्षा कर सकता है, लेकिन स्टेट कमिट अभी भी "सफल डिलीवरी के बाद कमिट" का पालन करते हैं। रद्दीकरण नए रीड्स को रोकता है, फ़ाइलों या नेटवर्क संसाधनों को बंद करता है, और गैर-प्रतिबद्ध (uncommitted) कर्सर को अपरिवर्तित छोड़ देता है।

विफलताओं को पुनः प्रयास करने योग्य I/O, स्थायी प्रारूप त्रुटियों, या स्रोत-संस्करण परिवर्तनों के रूप में वर्गीकृत करें। पुनः प्रयास करने योग्य त्रुटियों के लिए बैक ऑफ करें और चेकपॉइंट बनाए रखें; स्थायी रूप से खराब स्रोत को समाप्त करने से पहले एक स्रोत आईडी और ऑफ़सेट रिकॉर्ड करें; सामग्री को चुपचाप बदलने के बजाय स्रोत परिवर्तन के बाद पुनर्मूल्यांकन या एक नए स्नैपशॉट की आवश्यकता होती है।

चरण 6: परीक्षण और जटिलता डिज़ाइन करें

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

सिंगल-सोर्स next और स्नैपशॉट रीड/राइट O(1) हैं, जिसमें O(1) स्टेट आकार होता है। m स्रोतों के साथ, एक स्नैपशॉट कम से कम O(m) होता है। एक हीप या पहले से प्राप्त हेड्स next को O(log m) बना सकते हैं; राउंड-रॉबिन परिशोधित (amortized) O(1) हो सकता है। जटिलता चुने गए शेड्यूलर से मेल खानी चाहिए।

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

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

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

एसिंक next समवर्ती रूप से I/O की प्रतीक्षा कर सकता है, लेकिन स्टेट कमिट अभी भी डिलीवरी के बाद ही होते हैं। रद्दीकरण संसाधनों को बंद करता है और गैर-प्रतिबद्ध स्थिति को सुरक्षित रखता है। त्रुटियों को पुनः प्रयास करने योग्य, स्थायी, या स्रोत-संस्करण परिवर्तनों के रूप में वर्गीकृत किया जाता है। परीक्षण यह साबित करते हैं कि एक स्नैपशॉट बिना किसी डुप्लिकेट या स्किप के समान प्रत्यय देता है, और यह कि पूर्णता क्रम को बदलने से भी शेड्यूलिंग अनुबंध संतुष्ट रहता है। सिंगल-सोर्स संचालन O(1) हैं, जबकि m-सोर्स स्नैपशॉट O(m) है, जिसमें next की जटिलता राउंड-रॉबिन या हीप शेड्यूलिंग द्वारा निर्धारित होती है।"

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

• लौटाए गए इंडेक्स को अगले इंडेक्स के रूप में सहेजना → रिकवरी एक तत्व को दोहराती है या छोड़ देती है → चेकपॉइंट सेमेंटिक्स को परिभाषित करें और डिलीवरी के बाद आगे बढ़ें।
• फ़ाइल हैंडल या जनरेटर ऑब्जेक्ट्स को सीरियलाइज़ करना → ऑब्जेक्ट्स प्रक्रिया के पुनरारंभ होने पर नहीं बचते हैं → संस्करणित स्केलर संग्रहीत करें और संसाधनों को पुनर्निर्मित करें।
• hasNext() के साथ जांच (probe) करना → जांच करने और उपभोग करने के बीच एक एसिंक स्रोत बदल सकता है → next() को परमाणु रूप से (atomically) एक मान या पूर्णता परिणाम लौटाने दें।
• कई स्रोतों के लिए केवल एक कुल गणना सहेजना → प्रति-स्रोत प्रगति और शेड्यूलर की स्थिति गायब हो जाती है → प्रत्येक चाइल्ड स्थिति और शेड्यूलर स्थिति को सहेजें।
• रीड विफलता के बाद आगे बढ़ना → पुनः प्रयास से डेटा खो जाता है → केवल सफल डिलीवरी के बाद ही कमिट करें।
• स्रोत संस्करण की जांच किए बिना पुनर्स्थापित करना → समान ऑफ़सेट भिन्न सामग्री की पहचान कर सकता है → फ़िंगरप्रिंट, लंबाई, या लॉजिकल संस्करण को मान्य करें और बासी (stale) स्थिति को अस्वीकार करें।

अनुवर्ती प्रश्न और उत्तर

क्या होगा यदि रीड सफल होने के बाद लेकिन डिलीवरी की पावती मिलने से पहले स्नैपशॉट लिखा जाता है?

पावती सीमा (acknowledgement boundary) को परिभाषित करें। यदि स्नैपशॉट पहले आ सकता है, तो सिस्टम कम-से-कम-एक-बार (at-least-once) है और प्रत्येक आइटम को एक इडेम्पोटेंसी कुंजी या पावती मार्कर की आवश्यकता होती है। ठीक-एक-बार (exactly-once) व्यवहार के लिए, डिलीवरी पावती और कर्सर कमिट को एक पुनर्प्राप्ति योग्य लेनदेन या बाहरी कमिट लॉग में रखें।

आप कई तैयार एसिंक स्रोतों को निष्पक्ष (fair) कैसे रखते हैं?

एक राउंड-रॉबिन शेड्यूलर में अंतिम-चयनित कर्सर को बनाए रखें और प्रत्येक सफल डिलीवरी के बाद इसे आगे बढ़ाएं; सबसे तेज़ स्रोत को आउटपुट पर एकाधिकार नहीं करना चाहिए। वैश्विक समय क्रम के लिए, स्रोत हेड्स के मिन-हीप (min-heap) का उपयोग करें और स्नैपशॉट में हीप हेड और तुलना नियम शामिल करें।

क्या रोके जाने (paused) के दौरान अपेंड की गई फ़ाइल को सुरक्षित रूप से फिर से शुरू किया जा सकता है?

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

जब next() कई I/O ऑपरेशनों की प्रतीक्षा कर रहा हो तो आप इसे कैसे रद्द करते हैं?

एक रद्दीकरण संकेत पास करें, उन रीड्स को रोकें जो शुरू नहीं हुए हैं, और खुले संसाधनों को बंद करें। कोई भी अनसुलझा प्रॉमिस कर्सर को आगे नहीं बढ़ा सकता है। बाद का next() या तो मूल चेकपॉइंट से पुनः प्रयास करता है या एक स्पष्ट रद्दीकरण स्थिति लौटाता है।