कोडिंग इंटरव्यू: भारित रिज़र्वॉयर सैंपलिंग (Weighted Reservoir Sampling) लागू करना

1. संकेत और संदर्भ

स्ट्रीम के प्रत्येक रिकॉर्ड का एक सकारात्मक भार (positive weight) होता है, लेकिन न तो आइटमों की संख्या और न ही कुल भार ज्ञात होता है। बिना प्रतिस्थापन के आकार-k का भारित नमूना लागू करें: प्रत्येक रिकॉर्ड अधिकतम एक बार दिखाई देता है, इसके शामिल होने की संभावना इसके भार के समानुपाती होती है, और स्ट्रीम को केवल एक बार स्कैन किया जाता है। कुंजी निर्माण (key generation), उम्मीदवार प्रबंधन (candidate maintenance), अत्यधिक भार (extreme weights), और वितरण परीक्षणों (distribution tests) की व्याख्या करें।

2. साक्षात्कारकर्ता क्या परीक्षण कर रहा है

• क्या आप प्रतिस्थापन के साथ और बिना प्रतिस्थापन के सैंपलिंग में अंतर करते हैं तथा भार के समानुपाती प्रायिकता को समझते हैं।
• क्या आप भारित सैंपलिंग को शीर्ष k यादृच्छिक प्राथमिकताओं या घातीय कुंजियों (exponential keys) को बनाए रखने में बदल सकते हैं।
• क्या आप आकार-k का मिन-हीप (min-heap) चुनते हैं और प्रति रिकॉर्ड O(log k) अपडेट प्रदान करते हैं।
• क्या आप शून्य, विशाल, या सूक्ष्म भार, यादृच्छिक सीमाओं, डुप्लिकेट आईडी और एक पुनरुत्पादक सीड (reproducible seed) को संभालते हैं।

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

1. क्या भार परिमित सकारात्मक संख्याएं हैं, और क्या शून्य-भार वाले रिकॉर्ड को छोड़ दिया जाना चाहिए या बनाए रखा जाना चाहिए?
2. क्या सैंपलिंग बिना प्रतिस्थापन के है, या कोई रिकॉर्ड एक से अधिक बार आ सकता है?
3. क्या केवल अंतिम नमूना आवश्यक है, या प्रत्येक प्रीफ़िक्स में सही वितरण होना चाहिए?
4. क्या कई शार्ड्स को मर्ज किया जाना चाहिए, स्थिति को बनाए रखा जाना चाहिए, या परिणामों को सटीक रूप से पुनरुत्पादित किया जाना चाहिए?

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

भार w के प्रत्येक रिकॉर्ड के लिए एक स्वतंत्र यादृच्छिक कुंजी उत्पन्न करें और सबसे बड़ी k कुंजियाँ रखें। एक स्थिर रूप (0, 1] से समान रूप से u खींचता है और key = log(u) / w की गणना करता है; क्योंकि कुंजियाँ ऋणात्मक होती हैं, यह शून्य के सबसे निकटतम k कुंजियों को रखने के बराबर है। वर्तमान नमूने को आकार-k के मिन-हीप में संग्रहीत करें जिसका रूट सबसे छोटी कुंजी है; इसे केवल तभी बदलें जब कोई नई कुंजी बड़ी हो। एक एकल पास में O(n log k) समय और O(k) अतिरिक्त स्थान लगता है। भार को मान्य करें और यादृच्छिक स्रोत को इंजेक्ट करने योग्य बनाएं।

5. चरण-दर-चरण गहन उत्तर

चरण 1: वितरण को परिभाषित करें

बिना प्रतिस्थापन के भारित सैंपलिंग, प्रायिकता w / total के साथ k स्वतंत्र ड्रा नहीं है, क्योंकि यह किसी रिकॉर्ड को दोहरा सकती है। लक्ष्य आकार-k का एक ऐसा सेट है जिसका क्रम-सांख्यिकीय वितरण (order-statistic distribution) उसके शेष भार के अनुपात में एक अचयनित आइटम को बार-बार खींचने के बराबर हो। रिज़र्वॉयर प्रत्येक प्रीफ़िक्स के बाद एक मान्य नमूना होना चाहिए, न कि केवल स्ट्रीम समाप्त होने के बाद।

चरण 2: संख्यात्मक रूप से स्थिर कुंजी उत्पन्न करें

घातीय दौड़ (exponential race) एक सुविधाजनक कार्यान्वयन प्रदान करती है: एक समान u निकालें और key = log(u) / w की गणना करें, फिर सबसे बड़ी कुंजियों को बनाए रखें। जैसे-जैसे u शून्य के करीब पहुंचता है, log(u) अधिक ऋणात्मक हो जाता है; एक बड़ा भार कुंजी को शून्य के करीब लाता है और इसलिए शीर्ष k में प्रवेश करने की संभावना बढ़ जाती है। u ** (1 / w) से बचें, जो अत्यधिक भार के लिए अंडरफ्लो हो सकता है या पृथक्करण खो सकता है।

sample_key(weight):
    require finite(weight) and weight > 0
    u = uniform_random_open_interval()
    return log(u) / weight

चरण 3: मिन-हीप के साथ शीर्ष-k बनाए रखें

सटीक कुंजी टाई को तोड़ने के लिए अनुक्रम (sequence) का उपयोग करते हुए हीप में (key, sequence, item) संग्रहीत करें। जब तक रिज़र्वॉयर भरा न हो, तब तक पुश करें। एक बार भरने के बाद, नई कुंजी की तुलना रूट से करें और केवल तभी बदलें जब वह बड़ी हो। यदि k शून्य है, तो प्रत्येक रिकॉर्ड को छोड़ दें। प्रत्येक रिकॉर्ड के बाद एक ऐरे को फिर से सॉर्ट करने से अपडेट O(log k) के बजाय O(k log k) हो जाएगा।

चरण 4: इनपुट और यादृच्छिकता सीमाओं को संभालें

NaN, अनंत, और ऋणात्मक भार को अस्वीकार करें। सकारात्मक-भार वाले नमूने द्वारा शून्य-भार वाला रिकॉर्ड नहीं चुना जा सकता है और इसे छोड़ा जा सकता है। यादृच्छिक स्रोत को शून्य नहीं लौटाना चाहिए, अन्यथा log(0) अनुपयोगी हो जाता है; पुन: ड्रा करें या सबसे छोटे सकारात्मक फ्लोटिंग-पॉइंट मान पर क्लैंप करें। डुप्लिकेट आईडी को अलग-अलग रिकॉर्ड के रूप में मानें जब तक कि समस्या स्पष्ट रूप से आईडी डिडुप्लिकेशन के लिए न कहे। परीक्षणों में एक छद्म-यादृच्छिक (pseudo-random) स्रोत इंजेक्ट करें ताकि विफलताओं को पुनरुत्पादित किया जा सके।

चरण 5: जटिलता, सत्यापन और वितरित विस्तार

n रिकॉर्ड्स के लिए, सिंगल-मशीन कार्यान्वयन में O(n log k) समय और O(k) अतिरिक्त स्थान लगता है। यह जांचने के लिए निश्चित-भार मोंटे कार्लो सिमुलेशन का उपयोग करें कि सीमांत समावेशन (marginal inclusion) भार के साथ बढ़ता है, और पुष्टि (assert) करें कि नमूने में कोई डुप्लिकेट नहीं है। एक वितरित स्ट्रीम में, प्रत्येक शार्ड समान नियम के साथ कुंजियाँ उत्पन्न कर सकता है और एक समन्वयक (coordinator) शार्ड के शीर्ष-k उम्मीदवारों को मर्ज कर सकता है; स्थिति, अपडेट, विलोपन, सीड और संचार लागत के लिए अभी भी एक स्पष्ट डिज़ाइन की आवश्यकता है। केवल शार्ड रिज़र्वॉयर से समान रूप से सैंपलिंग करने से छोड़े गए रिकॉर्ड की जानकारी खो जाती है।

6. उच्च-गुणवत्ता वाले उत्तर का उदाहरण

प्रत्येक सकारात्मक-भार वाले रिकॉर्ड के लिए मैं key = log(u) / w उत्पन्न करता हूँ, जहाँ u एक खुले अंतराल पर समान है, और सबसे बड़ी k कुंजियाँ रखता हूँ। कुंजियाँ ऋणात्मक होती हैं, इसलिए बड़े भार शून्य के करीब होते हैं। क्षमता-k वाला मिन-हीप नमूने को संग्रहीत करता है; भरने पर, एक नई कुंजी सबसे छोटे रूट को केवल तभी बदलती है जब वह बड़ी हो। मैं अमान्य भार, शून्य यादृच्छिक मान, k = 0, और डुप्लिकेट रिकॉर्ड के लिए व्यवहार को परिभाषित करता हूँ। स्कैन में O(n log k) समय और O(k) स्थान लगता है। मैं बार-बार निश्चित-भार सिमुलेशन के साथ वितरण को मान्य करता हूँ और उसी वैश्विक शीर्ष-k कुंजी नियम द्वारा वितरित उम्मीदवारों को मर्ज करता हूँ।

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

• w / total के साथ स्वतंत्र रूप से ड्रा करना → डुप्लिकेट बनाता है और प्रतिस्थापन के बिना सैंपलिंग नहीं है → यादृच्छिक कुंजियों और शीर्ष-k का उपयोग करें।
• सीधे u ** (1 / w) की गणना करना → अत्यधिक भार के लिए अंडरफ्लो → लघुगणकीय (logarithmic) कुंजियों की तुलना करें।
• शीर्ष-k के लिए मैक्स-हीप (max-heap) का उपयोग करना → सबसे छोटे मान की खोज करने की आवश्यकता होती है → मिन-हीप का उपयोग करें ताकि प्रतिस्थापन बिंदु रूट हो।
• u = 0 की अनुमति देना → log(0) ऋणात्मक अनंत हो जाता है → एक खुले अंतराल स्रोत का उपयोग करें या फिर से ड्रा करें।
• केवल एक आउटपुट का परीक्षण करना → दीर्घकालिक पूर्वाग्रह छूट जाता है → निश्चित-भार मोंटे कार्लो परीक्षण चलाएं और दावा करें कि कोई डुप्लिकेट नहीं है।

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

key = log(u) / w भारित सैंपलिंग क्यों देता है?

दर एक (rate one) के साथ -log(u) को एक घातीय चर (exponential variable) के रूप में मानें। w से विभाजित करने पर दर w के साथ एक घातीय समय मिलता है। सबसे छोटा घातीय समय एक बड़ी दर से आने की अधिक संभावना होती है; इसे नकारने का अर्थ सबसे बड़ी कुंजियों को बनाए रखना है, जिससे बिना प्रतिस्थापन के भारित सैंपलिंग प्राप्त होती है।

आप परिणामों को पुनरुत्पादित करने योग्य कैसे बनाते हैं?

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

क्या पहले से बने दो रिज़र्वॉयर को मर्ज किया जा सकता है?

यदि दोनों शार्ड्स ने समान नियम के तहत स्वतंत्र कुंजियाँ उत्पन्न की हैं, तो उनकी उम्मीदवार कुंजियों को मर्ज करें और वैश्विक शीर्ष k लें। केवल दो अंतिम रिज़र्वॉयर को सामान्य डेटा के रूप में मानना और फिर से सैंपलिंग करना छोड़े गए रिकॉर्ड के बारे में जानकारी खो देता है। पर्सिस्टेड कुंजियों और शार्ड अपडेट या विलोपन के लिए भी परिभाषित व्यवहार की आवश्यकता होती है।

क्या होगा यदि समय के साथ भार बदल जाए?

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