प्रॉम्प्ट और संदर्भ
आपको निचले आधे हिस्से के लिए मैक्स-हीप और ऊपरी आधे हिस्से के लिए मिन-हीप वाला एक MedianFinder विरासत में मिलता है। यह 1, 2, 3 के लिए काम करता है, फिर भी 10, 1, 9, 2, अत्यधिक डुप्लिकेट वाले इनपुट और अत्यधिक बड़े/छोटे पूर्णांकों (extreme integers) जैसे अनुक्रमों पर विफल हो जाता है। कार्य मौजूदा कार्यान्वयन को डीबग करना है, न कि स्क्रैच से मानक डेटा संरचना तैयार करना।
इंटरव्यूअर क्या मूल्यांकन करता है
- क्या आप कोड बदलने से पहले इनवेरिएंट्स (invariants) बताते हैं।
- क्या आप विफल होने वाले अनुक्रम को छोटा कर सकते हैं और पहली अमान्य स्थिति की पहचान कर सकते हैं।
- क्या सुधार खाली क्वेरीज़, डुप्लिकेट्स और सम-लंबाई वाले ओवरफ़्लो को संभालता है।
- क्या प्रमाण और जटिलता कोड से मेल खाते हैं।
पूछने के लिए स्पष्टीकरण संबंधी प्रश्न
- पहली प्रविष्टि (insertion) से पहले
findMedian()को क्या करना चाहिए? - किस हीप में अतिरिक्त तत्व हो सकता है?
- API किस पूर्णांक चौड़ाई (integer width) को स्वीकार करता है, और मीडियन किस प्रकार का रिटर्न देता है?
- क्या डुप्लिकेट्स आ सकते हैं, और क्या समवर्ती पहुंच (concurrent access) इसके दायरे में है?
मान लें कि डुप्लिकेट्स मान्य हैं, निचले हीप में एक अतिरिक्त तत्व हो सकता है, क्वेरी एक फ़्लोटिंग-पॉइंट मान लौटाती है, और खाली लुकअप एक प्रलेखित त्रुटि (documented error) उत्पन्न करता है। कॉनक्रेन्सी इस कोडिंग कार्य के दायरे से बाहर है।
30-सेकंड का उत्तर
"मैं प्रत्येक प्रविष्टि के बाद दोनों हीप्स को इंस्ट्रूमेंट करूँगा और दो इनवेरिएंट्स का दावा करूँगा: उनके आकारों में अधिकतम एक का अंतर होना चाहिए और निचला हीप बड़ा होना चाहिए, तथा प्रत्येक निचला मान प्रत्येक ऊपरी मान से बड़ा नहीं होना चाहिए, जिसे हीप टॉप्स पर जाँचा जा सकता है। मैं पहले विफल होने वाले इनपुट को न्यूनतम करूँगा, फिर निचले हीप में पुश करके, इसके अधिकतम मान को ऊपरी हीप में ले जाकर, और ऊपरी न्यूनतम मान को केवल तभी वापस लाकर इन्सर्टियन को ठीक करूँगा जब वह बड़ा हो। मीडियन लुकअप विषम आकार के लिए निचले टॉप का उपयोग करता है और सम आकार के लिए दोनों टॉप्स के ओवरफ़्लो-सुरक्षित औसत का उपयोग करता है। अंत में, मैं संपूर्ण छोटे अनुक्रमों और प्रतिकूल चरम सीमाओं (adversarial extremes) पर एक सॉर्टेड-एरे ऑरेकल चलाऊँगा।"
चरण-दर-चरण गहन विश्लेषण
1. विफलता को अवलोकनीय (observable) बनाएं
प्रत्येक प्रविष्टि के बाद, इनपुट प्रीफ़िक्स, दोनों हीप साइज़ और दोनों टॉप्स को रिकॉर्ड करें। पहले टूटे हुए इनवेरिएंट पर रुकें। विफलता बने रहने तक मानों को हटाकर अनुक्रम को डेल्टा-डीबग करें। एक हज़ार यादृच्छिक मानों की तुलना में चार-मान वाला प्रति-उदाहरण (counterexample) अधिक उपयोगी होता है।
2. एक नियतात्मक (deterministic) प्रविष्टि पथ के साथ सुधार करें
निचले हीप को प्रवेश बिंदु के रूप में उपयोग करें। x को पुश करें, इसके अधिकतम मान को ऊपरी हीप में ले जाएं, फिर यदि ऊपरी हीप बड़ा हो गया है तो ऊपरी न्यूनतम मान को वापस ले आएं। यह क्रम आकार से पहले ऑर्डरिंग को पुनर्स्थापित करता है। ऐसी भाषा लाइब्रेरी के साथ जो केवल मिन-हीप प्रदान करती है, निचले हीप में ऋणात्मक मान संग्रहीत करें और सीमा पर साइन रूपांतरण बनाए रखें।
3. लुकअप को सुरक्षित बनाएं
जब दोनों हीप खाली हों तो लुकअप को अस्वीकार करें। विषम संख्या के लिए, निचला अधिकतम मान लौटाएं। सम संख्या के लिए, जोड़ने से पहले दोनों अंतिम बिंदुओं को एक व्यापक या फ़्लोटिंग प्रकार में परिवर्तित करें; (a + b) / 2 एक निश्चित-चौड़ाई वाले पूर्णांक प्रकार में ओवरफ़्लो हो सकता है, भले ही मीडियन प्रस्तुत करने योग्य हो।
4. सुधार को सिद्ध और परीक्षण करें
निचले अधिकतम मान को ऊपरी तरफ ले जाने से यह गारंटी मिलती है कि शेष निचले मान स्थानांतरित सीमा से अधिक नहीं होंगे। एक ऊपरी न्यूनतम मान को वापस ले जाने से क्रम को तोड़े बिना चुना हुआ आकार नियम बहाल हो जाता है। प्रत्येक प्रविष्टि हीप ऑपरेशनों की एक स्थिर संख्या निष्पादित करती है, इसलिए यह O(log n) है; लुकअप O(1) में एक या दो टॉप्स पढ़ता है, और स्टोरेज O(n) है।
प्रत्येक प्रीफ़िक्स के बाद एक सॉर्टेड-लिस्ट ऑरेकल का उपयोग करें। खाली लुकअप, एक मान, दो चरम सीमाएं, आरोही, अवरोही, वैकल्पिक निम्न/उच्च, सभी डुप्लिकेट, ऋणात्मक मान और विषम व सम आकार के बीच कई बदलावों को कवर करें।
एक सशक्त नमूना उत्तर
"मैं उस शाखा को ठीक नहीं करूँगा जो संयोगवश विफल हो गई। मैं पहले lower.size == upper.size या lower.size == upper.size + 1 का दावा करूँगा, साथ ही जब भी दोनों मौजूद हों तो max(lower) <= min(upper) का दावा करूँगा। प्रत्येक add पर, मैं निचले हीप में पुश करता हूँ, इसके अधिकतम मान को ऊपरी हीप में ले जाता हूँ, फिर ऊपरी न्यूनतम मान को केवल तभी वापस ले जाता हूँ जब ऊपरी हीप बड़ा हो। यह ऑर्डरिंग की पुनर्स्थापना को पिछले इनपुट पैटर्न से स्वतंत्र बनाता है।
findMedian एक खाली संरचना को अस्वीकार करता है। विषम आकार का स्ट्रीम निचले टॉप को लौटाता है; सम आकार का स्ट्रीम औसत निकालने से पहले दोनों टॉप्स को परिवर्तित करता है ताकि चरम पूर्णांक ओवरफ़्लो न हो सकें। मैं ऋणात्मक, शून्य, डुप्लिकेट और चरम मानों से लिए गए संपूर्ण छोटे अनुक्रमों के लिए एक सॉर्टेड-एरे ऑरेकल के विरुद्ध प्रत्येक प्रीफ़िक्स की तुलना करूँगा। मुख्य कार्यान्वयन प्रति जोड़ O(log n), प्रति क्वेरी O(1) और O(n) स्पेस बना रहता है।"
सामान्य गलतियाँ
- केवल आकारों को संतुलित करना → हीप्स में क्रॉस्ड मान हो सकते हैं → टॉप ऑर्डरिंग को एक अलग इनवेरिएंट के रूप में दावा करें।
- केवल आने वाले मान से एक शाखा चुनना → पिछली हीप स्थिति अभी भी अमान्य हो सकती है → एक नियतात्मक हीप-टू-हीप ट्रांसफर अनुक्रम का उपयोग करें।
- इनपुट पूर्णांक प्रकार में औसत निकालना → चरम अंतिम बिंदु ओवरफ़्लो हो सकते हैं → जोड़ने से पहले डेटा प्रकार को चौड़ा करें।
- केवल सॉर्ट किए गए अद्वितीय मानों का परीक्षण करना → डुप्लिकेट और वैकल्पिक चरम सीमाएं ब्रांच त्रुटियों को छिपाती हैं → प्रीफ़िक्स ऑरेकल और प्रतिकूल अनुक्रमों का उपयोग करें।
O(1)प्रविष्टि का दावा करना → हीप पुश और पॉप लॉगरिदमिक होते हैं → वास्तविक हीप ऑपरेशनों की गणना करें।
अनुवर्ती प्रश्न और उत्तर
आप सबसे छोटा विफल इनपुट कैसे खोजेंगे?
एक तत्व या एक सन्निहित खंड को हटाते रहें और इनवेरिएंट जाँचों को फिर से चलाएं। उस सबसे छोटे प्रीफ़िक्स को सुरक्षित रखें जिसकी अंतिम प्रविष्टि पहली बार ऑर्डरिंग या आकार का उल्लंघन करती है, फिर केवल उस संक्रमण का निरीक्षण करें।
डुप्लिकेट्स को विशेष हैंडलिंग की आवश्यकता क्यों नहीं है?
इनवेरिएंट <= का उपयोग करता है, इसलिए समान मान किसी भी तरफ रह सकते हैं। हीप का आकार यह निर्धारित करता है कि कौन सी समान प्रतिलिपि मीडियन में योगदान करती है; पहचान से कोई फर्क नहीं पड़ता।
आप किसी अन्य हीप कार्यान्वयन पर भरोसा किए बिना परीक्षण कैसे करेंगे?
छोटे इनपुट के लिए, प्रीफ़िक्स को कॉपी करें, इसे सॉर्ट करें, और सीधे गणितीय मीडियन की गणना करें। एक छोटे वर्णमाला (alphabet) पर सभी अनुक्रमों को समाप्त करें, फिर निश्चित-चौड़ाई वाले चरम मान और बड़े यादृच्छिक मामले जोड़ें।
क्या यह स्लाइडिंग विंडो का समर्थन करता है?
नहीं। किसी भी मनमाने समाप्त हो चुके (expired) मान को हटाने के लिए दोनों हीप्स में अनुक्रमित विलोपन (indexed deletion) या लेज़ी-विलोपन काउंटरों (lazy-deletion counters) की आवश्यकता होती है। यह एक अलग कार्य है और इसे इस सुधार के अंदर छिपाया नहीं जाना चाहिए।