कोडिंग साक्षात्कार: अज्ञात लंबाई वाले स्ट्रीम से समान रूप से (uniformly) सैंपल कैसे लें?

प्रॉम्प्ट और उपयोग के मामले

आप स्ट्रीम को केवल एक बार पढ़ सकते हैं; इसकी लंबाई n अज्ञात है, और आपको समान प्रायिकता के साथ k अलग-अलग तत्वों की आवश्यकता है। आप स्ट्रीम को स्टोर नहीं कर सकते हैं या अंतिम यादृच्छिक इंडेक्स की प्रतीक्षा नहीं कर सकते हैं। रिज़र्वॉयर सैंपलिंग k आकार का एक निश्चित रिज़र्वॉयर रखती है: जब तत्व i आता है, तो यह k/i प्रायिकता के साथ प्रवेश करता है और समान रूप से चुने गए रिज़र्वॉयर स्लॉट को बदल देता है।

यह प्रॉम्प्ट एक रैंडमाइज़्ड स्ट्रीमिंग एल्गोरिदम का परीक्षण करता है। Vitter का शोध पत्र जनसंख्या का आकार अज्ञात होने पर वन-पास सैंपलिंग का अध्ययन करता है, और विश्वविद्यालय के पाठ्यक्रम नोट्स एकरूपता का इंडक्शन (uniformity induction) प्रदान करते हैं। मुख्य श्रेणी coding है: मेमोरी सीमा के तहत प्रायिकता इनवेरिएंट, न कि डेटा-प्लेटफ़ॉर्म कार्यान्वयन।

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

• क्या आप अज्ञात-आकार, वन-पास, निश्चित-मेमोरी रिज़र्वॉयर पैटर्न को पहचानते हैं।
• क्या आप k के लिए सामान्यीकरण करने से पहले k=1 1/i प्रतिस्थापन नियम की व्याख्या करते हैं।
• क्या आप सिद्ध करते हैं कि तत्व i के बाद, सैंपल में प्रत्येक तत्व की प्रायिकता k/i है।
• क्या आप डुप्लिकेट सैंपल, गलत ज्ञात-n धारणा और पक्षपाती (biased) यादृच्छिक पूर्णांकों से बचते हैं।
• क्या आप O(n) समय, O(k) स्पेस और भारित सैंपलिंग की सीमा बताते हैं।

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

• क्या k एक धनात्मक पूर्णांक है? k <= 0 या k से कम स्ट्रीम तत्वों के लिए क्या होना चाहिए?
• क्या "अलग" (distinct) का अर्थ अलग रिकॉर्ड है या मान के आधार पर डिडुप्लिकेट करना है?
• क्या स्ट्रीम खाली, अनंत या बाधित हो सकती है? आउटपुट और रिकवरी अलग-अलग होते हैं।
• क्या अंतिम रिज़र्वॉयर ही एकमात्र आउटपुट है, या स्कैन के दौरान इसे देखा जा सकना चाहिए?
• क्या यादृच्छिक API आवश्यक सीमा पर निष्पक्ष (unbiased) पूर्णांक प्रदान करता है?
• क्या लक्ष्य समान (uniform) है या भारित/स्तरीकृत (weighted/stratified)? भारित सैंपलिंग के लिए एक अलग इनवेरिएंट की आवश्यकता होती है।

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

"रिज़र्वॉयर को पहले k तत्वों से भरें। एक से शुरू होने वाले तत्व i के लिए, [0, i-1] में एक निष्पक्ष पूर्णांक j उत्पन्न करें। यदि j < k है, तो reservoir[j] को बदलें; अन्यथा तत्व को छोड़ दें। तत्व i के बाद, प्रत्येक तत्व की प्रायिकता k/i होती है: नया तत्व k/i के साथ प्रवेश करता है, और एक पुराना तत्व k/(i-1) गुणा 1 - 1/i के साथ बना रहता है। एल्गोरिदम वन-पास है, O(n) समय और O(k) अतिरिक्त स्पेस लेता है।"

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

चरण 1: k=1 से शुरू करें।

पहला तत्व रखें। तत्व i के लिए, 1/i प्रायिकता के साथ वर्तमान उम्मीदवार को बदलें। i तत्वों को प्रोसेस करने के बाद, प्रत्येक के बने रहने की प्रायिकता 1/i होती है।

चरण 2: k के लिए सामान्यीकरण करें।

पहले k स्लॉट भरें। तत्व i के लिए, प्रायिकता k/i के साथ प्रवेश करें; यदि यह प्रवेश करता है, तो समान रूप से k स्लॉटों में से एक को चुनें। [0, i-1] में एक पूर्णांक j इसे लागू करता है: j < k का अर्थ है स्लॉट j को बदलना।

चरण 3: स्यूडोकोड लिखें।

reservoir = first k items
for i = k+1 .. n:
  j = uniformInteger(0, i-1)
  if j < k:
    reservoir[j] = item i
return reservoir

यदि स्ट्रीम को पहले से नहीं भरा जा सकता है, तो seen <= k तक जोड़ते रहें, फिर उसी ब्रांच का उपयोग करें। पूर्णांक जनरेटर को बिना किसी पूर्वाग्रह के पूरी सीमा को कवर करना चाहिए।

चरण 4: नए तत्व की प्रायिकता सिद्ध करें।

तत्व i पर, इसके शामिल होने की प्रायिकता k/i है। एक बार शामिल होने के बाद, यह प्रायिकता ∏(1 - 1/t) = i/n के साथ बाद के प्रत्येक चरण में बना रहता है, क्योंकि एक विशिष्ट स्लॉट को प्रायिकता 1/t के साथ बदला जाता है। इसलिए इसकी अंतिम प्रायिकता k/i × i/n = k/n है।

चरण 5: पुराने तत्व की प्रायिकता सिद्ध करें।

मान लें कि तत्व i-1 के बाद प्रत्येक पुराने तत्व की प्रायिकता k/(i-1) है। चरण i पर, इसे प्रायिकता k/i × 1/k = 1/i के साथ बदला जाता है, इसलिए यह प्रायिकता 1 - 1/i के साथ बचता है। इसकी नई प्रायिकता k/(i-1) × (i-1)/i = k/i है। नए और पुराने तत्व समान इनवेरिएंट को संतुष्ट करते हैं।

चरण 6: जटिलता और यादृच्छिक जनरेशन का विश्लेषण करें।

प्रत्येक तत्व को एक बार प्रोसेस किया जाता है: O(n) समय। रिज़र्वॉयर k तत्वों को रखता है: O(k) अतिरिक्त स्पेस। सुरक्षित पूर्णांक परिशुद्धता (precision) से परे की गणना के लिए, एक निष्पक्ष पूर्णांक API का उपयोग करें जो आवश्यक सीमा का समर्थन करता हो।

चरण 7: इनपुट सीमाओं को संभालें।

एक खाली स्ट्रीम एक खाली सैंपल लौटाती है। k = 0 एक खाली सैंपल लौटाता है या प्रलेखित त्रुटि उत्पन्न करता है। यदि k से कम तत्व आते हैं, तो वास्तविक तत्व लौटाएं या अनुबंध के अनुसार विफल हों। मान के आधार पर डिडुप्लिकेट करने के लिए अतिरिक्त स्थिति की आवश्यकता होती है और यह O(k) का उल्लंघन कर सकता है।

चरण 8: भारित और वितरित एक्सटेंशन की व्याख्या करें।

भारित सैंपलिंग लक्ष्य वितरण को बदल देती है, इसलिए समान-प्रायिकता प्रतिस्थापन अमान्य है; Efraimidis–Spirakis जैसी भारित-रिज़र्वॉयर कुंजियों पर चर्चा करें। वितरित रिज़र्वॉयर को सही ढंग से मर्ज करने के लिए काउंट और प्राथमिकताओं/भारों की आवश्यकता होती है; शार्ड नमूनों को सीधे जोड़ना (concatenate करना) पक्षपाती होता है।

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

"मैं क्षमता k का एक रिज़र्वॉयर बनाए रखता हूँ। इसे पहले k तत्वों से भरें। तत्व i = k+1 के बाद से, [0, i-1] में एक निष्पक्ष पूर्णांक j चुनें; यदि j < k है, तो स्लॉट j को बदलें, अन्यथा छोड़ दें। नया तत्व प्रायिकता k/i के साथ प्रवेश करता है। एक विशिष्ट पुराना तत्व प्रायिकता 1/i के साथ बदला जाता है, इसलिए इसकी प्रायिकता k/(i-1) से k/(i-1) × (1-1/i) = k/i में बदल जाती है। इंडक्शन द्वारा प्रत्येक तत्व की अंतिम प्रायिकता k/n होती है। एल्गोरिदम वन-पास है, O(n) समय और O(k) स्पेस लेता है। मैं खाली इनपुट, k=1, k=0, दोहराए गए रिकॉर्ड, दोहराए गए सिमुलेशन का परीक्षण करता हूँ, और भारित या वितरित वेरिएंट के लिए इनवेरिएंट को स्पष्ट रूप से फिर से प्राप्त करता हूँ।"

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

• पहले पूरी स्ट्रीम को स्टोर करना → अज्ञात-आकार और मेमोरी बाधाओं का उल्लंघन करता है → रिज़र्वॉयर को ऑनलाइन अपडेट करें।
• प्रत्येक नए तत्व के लिए 1/k का उपयोग करना → प्रायिकताएं i के अनुकूल नहीं होती हैं → k/i का उपयोग करें।
• random() % i का उपयोग करना → मॉड्यूलो पक्षपाती हो सकता है → निष्पक्ष पूर्णांक सैंपलिंग का उपयोग करें।
• प्रतिस्थापन स्लॉट को गैर-समान रूप से चुनना → कुछ संयोजन अधिक संभावित हो जाते हैं → k स्लॉटों में से समान रूप से चुनें।
• स्कैन करते समय k/n का उपयोग करना → n अज्ञात है और प्रायिकता प्रत्येक चरण में बदलती है → वर्तमान गणना i का उपयोग करें।
• डुप्लिकेट सिमेंटिक्स को अनदेखा करना → अलग रिकॉर्ड और अलग मान भिन्न होते हैं → पहले डिडुप्लिकेशन को स्पष्ट करें।
• शार्ड रिज़र्वॉयर को सीधे जोड़ना → असमान शार्ड आकार परिणाम को पक्षपाती बनाते हैं → काउंट और प्राथमिकताओं के साथ मर्ज करें।
• भार के लिए समान एल्गोरिदम का पुन: उपयोग करना → लक्ष्य वितरण बदल गया है → एक नए प्रमाण के साथ भारित रिज़र्वॉयर सैंपलिंग का उपयोग करें।

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

अनुवर्ती प्रश्न 1: नए तत्व की प्रतिस्थापन प्रायिकता k/i क्यों है?

तत्व i पर, एल्गोरिदम समान रूप से i स्थितियों में से एक चुनता है। पहली k स्थितियां रिज़र्वॉयर का प्रतिनिधित्व करती हैं, इसलिए किसी एक को चुनने की संभावना k/i है।

अनुवर्ती प्रश्न 2: आप k=1 के लिए निष्पक्षता कैसे सिद्ध करते हैं?

पहला तत्व प्रायिकता एक के साथ रखा जाता है। तत्व i इसे 1/i के साथ बदलता है; कोई भी पुराना तत्व (1/(i-1)) × (1-1/i) = 1/i के साथ बचता है, जिससे इंडक्शन प्राप्त होता है।

अनुवर्ती प्रश्न 3: आप एक निष्पक्ष पूर्णांक कैसे उत्पन्न करते हैं?

एक समान-पूर्णांक API, या रिजेक्शन सैंपलिंग का उपयोग करें जो सबसे बड़ी विभाज्य सीमा के बाहर के यादृच्छिक मानों को त्याग देती है। यह न मान लें कि साधारण मॉड्यूलो हमेशा निष्पक्ष होता है।

अनुवर्ती प्रश्न 4: क्या होगा यदि स्ट्रीम k तत्वों से पहले समाप्त हो जाए?

वास्तविक तत्व लौटाएं या प्रलेखित त्रुटि उत्पन्न करें। कभी भी प्रविष्टियां मनगढ़ंत न बनाएं; कोडिंग से पहले व्यवहार बताएं।

अनुवर्ती प्रश्न 5: आप भार के साथ सैंपल कैसे लेंगे?

भारित लक्ष्य वितरण को परिभाषित करें, फिर भारित-रिज़र्वॉयर यादृच्छिक कुंजियों या घातीय/लॉग ट्रांसफ़ॉर्म का उपयोग करें। समान k/i प्रमाण अब सीधे लागू नहीं होता है।

अनुवर्ती प्रश्न 6: आप वितरित रिज़र्वॉयर को कैसे मर्ज करेंगे?

प्रत्येक शार्ड अपने तत्वों की संख्या और पर्याप्त यादृच्छिक प्राथमिकता या भार जानकारी रखता है। वैश्विक सैंपलिंग नियम के अनुसार मर्ज करें; सीधा संयोजन या यादृच्छिक ट्रंकेशन छोटे शार्ड का पक्ष लेता है।

अनुवर्ती प्रश्न 7: आप एकरूपता को कैसे मान्य करते हैं?

एक निश्चित छोटी स्ट्रीम पर कई परीक्षण चलाएं, प्रत्येक तत्व की समावेशन आवृत्ति की तुलना k/n से करें, और सीमाओं और पुनरुत्पादक (reproducible) बीजों का परीक्षण करें। सांख्यिकी पूर्वाग्रह को प्रकट कर सकती है, लेकिन वे प्रायिकता प्रमाण की जगह नहीं लेती हैं।