प्रॉम्प्ट और लागू संदर्भ
सेट को सदस्यता (membership) की जांच करनी चाहिए, इंसर्ट करना चाहिए, डिलीट करना चाहिए, और वर्तमान एलिमेंट को समान रूप से रैंडम तरीके से वापस करना चाहिए। एक हैश मैप लुकअप प्रदान करता है जबकि एक डायनामिक ऐरे रैंडम इंडेक्सिंग प्रदान करता है; बीच के किसी एलिमेंट को हटाना यहाँ मुख्य चुनौती (conflict) है।
इंटरव्यूअर क्या मूल्यांकन करता है
- एक ही संरचना पर सब कुछ करने का दबाव डालने के बजाय हैश मैप और ऐरे को संयोजित करना।
- वैल्यू-टू-ऐरे-इंडेक्स मैप को बनाए रखना और प्रत्येक स्वैप के बाद इसे अपडेट करना।
- औसत O(1) और एमॉर्टाइज़्ड ऐरे ग्रोथ को समझना।
- यूनिफॉर्म getRandom और डुप्लिकेट-वैल्यू सिमेंटिक्स को परिभाषित करना।
- खाली सेट, अनुपस्थित डिलीट, और कंकरेंसी सीमाओं को संभालना।
उत्तर देने से पहले स्पष्ट करने वाले प्रश्न
- क्या वैल्यूज़ यूनिक हैं? डुप्लिकेट्स के लिए एक वैल्यू को इंडेक्स के सेट पर मैप करने की आवश्यकता होती है।
- क्या getRandom का यूनिफॉर्म होना आवश्यक है, या यह किसी भी रैंडम सदस्य को लौटा सकता है? स्वीकृति परीक्षण बदल जाता है।
- क्या O(1) एमॉर्टाइज़्ड औसत है या सख्त वर्स्ट-केस है? हैश टकराव नीति वादे को बदल देती है।
- क्या API वैल्यूज लौटाती है या हैंडल्स? म्यूटेबल ऑब्जेक्ट्स को समानता और हैशिंग नियमों की आवश्यकता होती है।
- क्या थ्रेड सुरक्षा, फिक्स्ड मेमोरी, या पुनरुत्पादक रैंडमनेस की आवश्यकता है?
30-सेकंड उत्तर ढांचा (Framework)
“मैं एक items ऐरे और एक indexOf हैश मैप रखता हूँ। Insert एक नया मान जोड़ता है और उसका इंडेक्स रिकॉर्ड करता है; getRandom एक यूनिफॉर्म ऐरे इंडेक्स का सैंपल लेता है। Remove टारगेट इंडेक्स ढूंढता है, अंतिम एलिमेंट को उस स्लॉट में ले जाता है, स्थानांतरित एलिमेंट के इंडेक्स को अपडेट करता है, ऐरे को पॉप करता है, और टारगेट मैपिंग को हटा देता है। यह O(n) शिफ्ट से बचाता है। हैश ऑपरेशंस और डायनामिक-ऐरे ग्रोथ औसतन एमॉर्टाइज़्ड O(1) हैं; एक खाली सेट सहमत त्रुटि लौटाता है, और डुप्लिकेट्स के लिए इंडेक्स-सेट मैपिंग की आवश्यकता होती है।”
चरण-दर-चरण गहन विश्लेषण
चरण 1: इनवेरिएंट स्थापित करें। प्रत्येक मान v के लिए, indexOf[v], items में इसके अद्वितीय स्थान की ओर इंगित करता है; ऐरे में कोई रिक्त स्थान नहीं है और प्रत्येक इंडेक्स सीमा के भीतर है।
चरण 2: insert लागू करें। यदि मैप में पहले से ही मान मौजूद है, तो निर्दिष्ट अनुसार false लौटाएं। अन्यथा इसे अंत में जोड़ें और नए इंडेक्स को औसत O(1) में स्टोर करें।
चरण 3: remove लागू करें। टारगेट इंडेक्स i और अंतिम इंडेक्स last को पढ़ें। यदि i !== last, तो अंतिम मान को items[i] में लिखें और इसकी मैप प्रविष्टि को बदलकर i कर दें; फिर अंतिम स्लॉट को पॉप करें और टारगेट प्रविष्टि को हटा दें।
चरण 4: getRandom लागू करें। गैर-खाली ऐरे से एक समान इंडेक्स का सैंपल लें। पायथन का choice दस्तावेज़ीकरण समान-संभावना अनुक्रम चयन को परिभाषित करता है; हैश पुनरावृत्ति क्रम (iteration order) रैंडमनेस की गारंटी नहीं है।
चरण 5: जटिलता बताएं। हैश लुकअप, अपेंड, स्वैप और पॉप औसतन एमॉर्टाइज़्ड O(1) हैं; ऐरे और मैप स्पेस O(n) हैं। वर्स्ट-केस हैश टकराव या रीसाइज़ पॉज़ के लिए अलग से SLO चर्चा की आवश्यकता होती है।
चरण 6: डुप्लिकेट्स को संभालें। indexOf[v] को इंडेक्स के सेट में बदलें। एक उदाहरण को हटाते समय, उसके इंडेक्स को हटा दें और दोनों इंडेक्स सेट को अपडेट करते हुए वही टेल स्वैप लागू करें।
चरण 7: सीमाओं को सत्यापित करें। एक खाली सेट, एक आइटम, बार-बार विलोपन, टेल को हटाना, बार-बार विकास, और एक निश्चित सीड का परीक्षण करें। केवल सदस्यता ही नहीं, बल्कि आवृत्तियों की जांच के लिए कई getRandom कॉल चलाएं।
मॉडल उत्तर
“मैं वर्तमान मानों को एक ऐरे में और प्रत्येक मान के ऐरे इंडेक्स को एक हैश मैप में संग्रहीत करता हूँ। बीच के किसी आइटम को हटाने के लिए, मैं टेल आइटम को उसके स्लॉट में ले जाता हूँ, उस आइटम के इंडेक्स को अपडेट करता हूँ, और टेल को पॉप करता हूँ, ताकि कोई भी एलिमेंट शिफ्ट न हो। getRandom समान रूप से चयनित ऐरे इंडेक्स को पढ़ता है, जिससे प्रत्येक अद्वितीय मान की संभावना समान हो जाती है। O(1) का दावा हैश संचालन और डायनामिक-ऐरे विकास के लिए औसत एमॉर्टाइज़्ड है; यदि डुप्लिकेट्स की अनुमति है, तो मैं सिंगल इंडेक्स को एक इंडेक्स सेट से बदल देता हूँ और विलोपन को एक इंस्टेंस हटाने के रूप में परिभाषित करता हूँ।”
सामान्य गलतियाँ
- केवल हैश मैप का उपयोग करना → getRandom प्रत्येक कुंजी को स्कैन करता है → एक कॉम्पैक्ट ऐरे जोड़ें।
- विलोपन के बाद शिफ्ट करना → delete O(n) बन जाता है → टेल के साथ स्वैप करें।
- स्थानांतरित मान के इंडेक्स को भूल जाना → बाद के डिलीट गलत स्लॉट को टारगेट करते हैं → मैप अपडेट को स्वैप के हिस्से के रूप में मानें।
- हैश इटरेटर का नमूना लेना → इटरेशन क्रम यूनिफॉर्मिटी की गारंटी नहीं देता है → ऐरे इंडेक्स का नमूना लें।
- औसत O(1) को वर्स्ट-केस O(1) कहना → टकराव और रीसाइज़ लागतों को नजरअंदाज किया जाता है → एमॉर्टाइज़्ड मान्यताओं का उल्लेख करें।
फॉलो-अप प्रश्न और उत्तर
फॉलो-अप 1: अंतिम ऐरे एलिमेंट को हटाते समय क्या होता है?
टारगेट इंडेक्स टेल इंडेक्स के बराबर होता है, इसलिए इसे बिना किसी स्वैप के पॉप करें और इसकी मैप प्रविष्टि को हटा दें।
फॉलो-अप 2: आप डुप्लिकेट्स का समर्थन कैसे करते हैं?
प्रत्येक मान को एक इंडेक्स सेट पर मैप करें। टेल को स्थानांतरित करने के बाद, उसके पुराने इंडेक्स को हटा दें, नया इंडेक्स जोड़ें, और टारगेट सेट से एक इंडेक्स हटा दें।
फॉलो-अप 3: आप कैसे साबित करते हैं कि getRandom यूनिफॉर्म है?
प्रत्येक वर्तमान इंस्टेंस एक ऐरे स्थिति पर कब्जा करता है, और इंडेक्स 0..n-1 पर समान है; इसलिए अद्वितीय मान प्रत्येक समान रूप से संभावित स्थिति पर कब्जा करते हैं।
फॉलो-अप 4: क्या हैश टकराव O(1) को तोड़ सकते हैं?
औसत जटिलता लोड फैक्टर और हैश गुणवत्ता पर निर्भर करती है। सख्त वर्स्ट-केस गारंटी के लिए ट्रीफाइड बकेट्स (treeified buckets), रैंडमाइज्ड हैशिंग या किसी अन्य संरचना की आवश्यकता होती है।
फॉलो-अप 5: आप समवर्ती रीड और डिलीट को कैसे संभालते हैं?
एक लॉक या वर्ज़न चेक के साथ रैंडम-इंडेक्स रीड और डिलीट स्वैप को सुरक्षित रखें; अन्यथा एक रीडर पॉप किए गए इंडेक्स का अवलोकन कर सकता है।
फॉलो-अप 6: आप वितरण (distribution) का परीक्षण कैसे करते हैं?
एक निश्चित सेट पर कई परीक्षण चलाएं, प्रत्येक मान की गणना करें, एक सांख्यिकीय सहनशीलता (statistical tolerance) निर्धारित करें, और यह भी सत्यापित करें कि प्रत्येक लौटाया गया मान सेट में बना रहे।