समस्या और संदर्भ
मूल क्रम को पुनर्स्थापित करने के लिए reset() और समान रूप से यादृच्छिक क्रमपरिवर्तन वापस करने के लिए shuffle() को लागू करें। यह प्रश्न यादृच्छिक एल्गोरिदम, इन-प्लेस स्वैप, यादृच्छिक संख्या सीमाओं और परीक्षण क्षमता का परीक्षण करता है; यही पैटर्न सैंपलिंग, लॉटरी निकालने और टेस्ट फिक्स्चर में दिखाई देता है।
इंटरव्यूअर क्या जांच रहा है
- मनमाने यादृच्छिक स्थानों को बार-बार स्वैप करने के बजाय Fisher–Yates को चुनना।
- इंडेक्स
iको केवल उसी भाग से सैंपल करना जो अभी तक तय (fixed) नहीं हुआ है। - पूर्वाग्रह या ओवरफ्लो से बचने के लिए समावेशी (inclusive) और अर्ध-खुले (half-open) यादृच्छिक API में अंतर करना।
- एक अपरिवर्तनीय आधार रेखा (baseline) बनाए रखना ताकि
reset()शफ़ल से प्रभावित न हो। - O(n) समय, O(1) अतिरिक्त स्थान और एकरूपता (uniformity) की व्याख्या करना।
- सीडेड PRNG, खाली ऐरे, डुप्लिकेट मान और सांख्यिकीय परीक्षण सीमाओं पर चर्चा करना।
पूछने के लिए स्पष्टीकरण प्रश्न
- क्या
shuffle()को एक नया ऐरे वापस करना चाहिए या वर्किंग ऐरे को संशोधित करके वापस करना चाहिए? - क्या
reset()को एक रक्षात्मक प्रति (defensive copy) वापस करनी चाहिए ताकि कॉल करने वाले आंतरिक स्थिति को संशोधित न कर सकें? - क्या यादृच्छिक स्रोत इंजेक्टेबल है, या क्रिप्टोग्राफ़िक रूप से सुरक्षित स्रोत की आवश्यकता है?
- क्या डुप्लिकेट मानों की अनुमति है, और क्या अलग-अलग स्थानों पर समान मान अलग-अलग क्रमपरिवर्तन हैं?
- क्या हमें थ्रेड सुरक्षा, पुनरुत्पादित करने योग्य सीड, या क्रिप्टोग्राफ़िक अप्रत्याशितता की आवश्यकता है?
- क्या इनपुट को स्ट्रीमिंग या स्थिर सहायक स्थान की आवश्यकता है?
30-सेकंड उत्तर ढांचा
“मैं एक मूल स्नैपशॉट और एक वर्किंग ऐरे रखता हूँ। अंतिम इंडेक्स से लेकर एक तक i के लिए, मैं [0, i] में एक समान j का नमूना लेता हूँ और a[i] को a[j] के साथ स्वैप करता हूँ। प्रत्येक पास एक स्थिति को तय करता है, इसलिए चलने का समय O(n) है और सहायक स्थान O(1) है। reset() स्नैपशॉट की एक प्रति लौटाता है; पुनरुत्पादकता और सांख्यिकीय परीक्षणों के लिए यादृच्छिक स्रोत को इंजेक्ट किया जा सकता है।”
चरण-दर-चरण गहन विश्लेषण
चरण 1: स्थिति को अलग करें। इनपुट को original और working में कॉपी करें; reset() फिर से original को कॉपी करता है ताकि बाहरी संदर्भ आधार रेखा को बदल न सकें।
चरण 2: यादृच्छिक सीमा को परिभाषित करें। i को n - 1 से 1 तक घटने दें। अर्ध-खुले API के साथ 0..i प्राप्त करने के लिए randomInt(i + 1) को कॉल करें; समावेशी API के साथ 0 और i को स्पष्ट रूप से पास करें।
चरण 3: इन-प्लेस स्वैप करें। working[i] और working[j] को स्वैप करें; स्थिति i अब तय हो गई है और समान आकार का कोई अस्थायी ऐरे नहीं बनाया गया है।
चरण 4: एकरूपता की व्याख्या करें। पहली तय स्थिति में n समान रूप से संभावित विकल्प होते हैं, अगली में n-1 होते हैं, इत्यादि, जिससे n! समान रूप से संभावित विकल्प पथ प्राप्त होते हैं। यादृच्छिक स्रोत को प्रत्येक उम्मीदवार इंडेक्स पर एक समान होना चाहिए।
चरण 5: डुप्लिकेट को संभालें। एल्गोरिदम तत्व स्थितियों पर एक समान है। दोहराए गए मान कई स्थिति क्रमपरिवर्तनों को समान मान अनुक्रम के रूप में प्रदर्शित कर सकते हैं; दृश्यमान अनुक्रम स्थिति क्रमपरिवर्तन के समान नहीं हैं।
चरण 6: रीसेट लागू करें। original की एक प्रति लौटाएं और working को पुनर्गठित करें; आंतरिक ऐरे को उजागर करने से कॉल करने वालों को उपनाम (alias) बनाने और आधार रेखा को दूषित करने की अनुमति मिल जाएगी।
चरण 7: सत्यापित करें और जटिलता बताएं। पुनरुत्पादकता के लिए एक निश्चित सीड का उपयोग करें, अनुमानित एकरूपता के लिए छोटे ऐरे आवृत्तियों की गणना करें, और खाली और एक-तत्व वाले ऐरे का परीक्षण करें। प्रत्येक शफ़ल O(n) समय और O(1) सहायक स्थान लेता है; संग्रहीत स्नैपशॉट स्वयं O(n) स्थिति का उपयोग करता है।
मॉडल उत्तर
“मैं original और working ऐरे रखता हूँ। shuffle, i = n-1..1 को पुनरावृत्त करता है, एक समान j ∈ [0,i] निकालता है, और दो प्रविष्टियों को स्वैप करता है; reset, original की एक प्रति लौटाता है और working को पुनर्गठित करता है। मनमाने यादृच्छिक पदों को बार-बार स्वैप करने से पिछली स्थितियाँ दोबारा लिखी जा सकती हैं और पक्षपाती क्रमपरिवर्तन उत्पन्न हो सकते हैं। Fisher–Yates केवल अनिर्धारित उपसर्ग का नमूना लेता है, इसलिए प्रत्येक स्थितीय क्रमपरिवर्तन समान रूप से संभावित होता है। यह O(n) समय में चलता है और स्थिति स्नैपशॉट से परे किसी अतिरिक्त ऐरे की आवश्यकता नहीं होती है। मैं सीडेड परीक्षणों के लिए यादृच्छिक स्रोत को इंजेक्ट करूंगा और जब परिणाम सुरक्षा या निष्पक्षता को प्रभावित करता है तो इसे CSPRNG से बदल दूंगा।”
सामान्य गलतियाँ
- प्रत्येक दौर में
[0,n-1]का नमूना लेना → तय स्थितियाँ फिर से बदल जाती हैं →[0,i]का उपयोग करें। floor(random * i)की गणना करना → इंडेक्सiकभी नहीं चुना जाता है → अर्ध-खुली सीमा के रूप मेंi + 1का उपयोग करें।- मनमाने यादृच्छिक युग्मों को n बार स्वैप करना → क्रमपरिवर्तन एक समान होने की गारंटी नहीं है → प्रत्येक Fisher–Yates चरण में एक स्थिति तय करें।
- रीसेट से वही आंतरिक संदर्भ वापस करना → कॉल करने वाले आधार रेखा को दूषित कर सकते हैं → एक रक्षात्मक प्रति लौटाएं।
- PRNG को सुरक्षित यादृच्छिकता के रूप में मानना → ड्रा परिणाम पूर्वानुमेय हो सकते हैं → खतरे के मॉडल के लिए CSPRNG चुनें।
अनुवर्ती प्रश्न और उत्तर
अनुवर्ती 1: लूप इसके बजाय आगे की ओर क्यों चल सकता है?
आगे का रूप [i,n-1] से नमूना लेकर i को तय करता है; प्रमाण सममित है। अपरिवर्तनीय नियम यह है कि प्रत्येक विकल्प केवल अनिर्धारित क्षेत्र से आता है।
अनुवर्ती 2: आप एकरूपता कैसे साबित करते हैं?
स्थिति n-1 में n समान रूप से संभावित विकल्प हैं, स्थिति n-2 में n-1 हैं, इत्यादि। इसलिए प्रत्येक पूर्ण विकल्प पथ की प्रायिकता 1/n! है।
अनुवर्ती 3: आप यादृच्छिकता का परीक्षण कैसे करते हैं?
एक छोटे ऐरे पर कई परीक्षण चलाएं, सहनशीलता (tolerance) के साथ क्रमपरिवर्तन आवृत्तियों की तुलना करें, और पुनरुत्पादकता को सत्यापित करने के लिए एक निश्चित सीड का उपयोग करें। एक सीमित नमूना साक्ष्य है, प्रमाण नहीं।
अनुवर्ती 4: सामान्य छद्म-यादृच्छिकता कब अपर्याप्त होती है?
जब कोई ड्रा, टोकन या शफ़ल सुरक्षा या पात्रता को प्रभावित करता है, तो सिस्टम CSPRNG का उपयोग करें। सीड करने योग्य PRNG सिमुलेशन, गेम और परीक्षणों के लिए उपयुक्त हैं।
अनुवर्ती 5: क्या होगा यदि इनपुट एक लिंक्ड सूची है?
ऐरे में कनवर्ट करने में O(n) स्थान खर्च होता है। नोड स्वैप स्टोरेज को सुरक्षित रख सकते हैं लेकिन रैंडम एक्सेस महंगा हो जाता है, इसलिए बाधाओं पर फिर से बातचीत की जानी चाहिए।
अनुवर्ती 6: आप समवर्ती कॉल को कैसे संभालते हैं?
प्रत्येक इंस्टेंस को अलग स्थिति दें और म्यूटेशन को लॉक करें, या अपरिवर्तनीय स्नैपशॉट लौटाएं। जब कोई अन्य थ्रेड रीसेट करता है तो कॉल करने वाले को आंशिक स्वैप नहीं देखना चाहिए।
अनुवर्ती 7: क्या Java मानक लाइब्रेरी इस विचार का उपयोग करती है?
Oracle एक बैकवर्ड ट्रैवर्सल का दस्तावेजीकरण करता है जो वर्तमान स्थिति में एक यादृच्छिक तत्व को स्वैप करता है; एक निष्पक्ष स्रोत के साथ, सभी क्रमपरिवर्तन समान संभावना के साथ होते हैं।