इंटरव्यूअर क्या मूल्यांकन करता है
एक पूर्णांक ऐरे दिए जाने पर, अधिकतम एक तत्व को हटाने के बाद गैर-खाली सन्निहित सबर्रे का अधिकतम योग लौटाएं। निष्कासन वैकल्पिक है, और शेष तत्व एक ही सन्निहित अंतराल से आने चाहिए।
सीमाएं और बाउंड्रीज़
- ऐरे गैर-खाली है और इसमें ऋणात्मक, शून्य या धनात्मक मान हो सकते हैं।
- परिणाम एक खाली ऐरे नहीं हो सकता।
- किसी अंतराल के अंतिम बिंदु को हटाना उस अंतिम बिंदु को चुने गए अंतराल से बाहर करने के बराबर है।
- निष्कासन स्थिति और दो सबर्रे को एन्युमरेट करने के बजाय एक स्कैन का लक्ष्य रखें।
निष्कासन को एक स्टेट में बदलें
keep बनाए रखें, जो बिना किसी निष्कासन के वर्तमान इंडेक्स पर समाप्त होने वाला सबसे अच्छा योग है, और drop, जो एक निष्कासन के बाद वहां समाप्त होने वाला सबसे अच्छा योग है। एक मान x के लिए, keep फिर से शुरू करने या आगे बढ़ाने का विकल्प चुनता है; drop, x को हटाने या पहले से हटाए गए स्टेट को आगे बढ़ाने का विकल्प चुनता है।
परिणाम स्टेट्स को मध्यवर्ती स्टेट्स से अलग करें
उत्तर को दोनों स्टेट्स का निरीक्षण करना चाहिए क्योंकि इष्टतम समाधान में किसी निष्कासन का उपयोग नहीं हो सकता है या यह किसी ऋणात्मक मान को हटा सकता है। drop को शून्य पर इनिशियलाइज़ करने से एक खाली सबर्रे या गैर-मौजूद तत्व के निष्कासन की अनुमति मिल जाएगी।
लीनियर जटिलता की व्याख्या करें
प्रत्येक मान दो स्थिर-आकार के स्टेट्स को अपडेट करता है, इसलिए समय O(n) है और अतिरिक्त स्पेस O(1) है। स्टेट्स पूर्ण हैं क्योंकि यहां समाप्त होने वाले प्रत्येक मान्य अंतराल ने या तो कोई निष्कासन नहीं किया है या ठीक एक निष्कासन किया है।
उत्तर देने से पहले स्पष्टीकरण प्रश्न
- क्या "अधिकतम एक" में कोई निष्कासन न होना शामिल है? ठीक एक की आवश्यकता होने से उत्तर और एकल-तत्व बाउंड्री बदल जाती है।
- क्या परिणाम गैर-खाली होना चाहिए? खाली आउटपुट की अनुमति देने से शून्य गलत तरीके से उत्तर बन सकता है।
- क्या योग 32-बिट पूर्णांक को ओवरफ्लो कर सकता है? यह एक्यूमुलेटर प्रकार और परीक्षण सीमा निर्धारित करता है।
30-सेकंड उत्तर रूपरेखा
"मैं वर्तमान इंडेक्स पर समाप्त होने वाले दो स्टेट्स रखता हूँ: keep में कोई निष्कासन नहीं है और drop में एक निष्कासन है। x के लिए, keep पुनरारंभ या विस्तार है; drop, x को हटाना या पुराने drop का विस्तार करना है। उत्तर दोनों स्टेट्स में देखा गया अधिकतम है। मैं सभी-ऋणात्मक इनपुट के लिए शून्य के बजाय पहले तत्व से इनिशियलाइज़ करता हूँ, जिससे O(n) समय और O(1) स्पेस प्राप्त होता है।"
चरण-दर-चरण गहन विश्लेषण
मान लें कि पिछले स्टेट्स keepPrev और dropPrev हैं। उन्हें निम्नानुसार अपडेट करें:
keep = max(x, keepPrev + x)
drop = max(dropPrev + x, keepPrev)दूसरी पंक्ति के keepPrev का अर्थ वर्तमान तत्व को हटाना है; पुराने अंतराल में पहले से ही एक तत्व मौजूद है। dropPrev + x का अर्थ है कि निष्कासन पहले हुआ था और वर्तमान मान जोड़ा गया है। किसी भी स्टेट को ओवरराइट करने से पहले पुराने मानों को सहेजें।
एक-तत्व वाले ऐरे के लिए, keep वह तत्व है और drop को कानूनी खाली अंतराल का प्रतिनिधित्व नहीं करना चाहिए। drop को ऋणात्मक अनंत पर इनिशियलाइज़ करें और दूसरे तत्व से अपडेट करें, या गैर-खाली नियम को बनाए रखते हुए स्पष्ट प्रथम-तत्व सिमेंटिक्स को परिभाषित करें।
मॉडल उच्च-गुणवत्ता वाला उत्तर
"मैं समस्या को दो DP स्टेट्स में विभाजित करता हूँ। keep बिना निष्कासन के इस इंडेक्स पर समाप्त होने वाला सबसे अच्छा योग है; drop एक निष्कासन के बाद सबसे अच्छा योग है। प्रत्येक x के लिए, पुराने स्टेट्स का उपयोग करके, keep=max(x, keep+x) और drop=max(drop+x, oldKeep) की गणना करें। मैं पहले मान से इनिशियलाइज़ करता हूँ ताकि सभी-ऋणात्मक ऐरे कभी शून्य न लौटाए, फिर दोनों स्टेट्स पर अधिकतम मान लेता हूँ। प्रत्येक मान में स्थिर कार्य होता है, जिससे O(n) समय और O(1) स्पेस मिलता है।"
सामान्य गलतियाँ
- निष्कासन के लिए बिना किसी स्टेट के साधारण Kadane चलाना।
dropको शून्य पर इनिशियलाइज़ करना और खाली अंतराल की अनुमति देना।- पहले से अपडेट किए गए
keepसेdropकी गणना करना, एक मान का दो बार उपयोग करना। - समस्या की बाउंड्री को स्पष्ट किए बिना खाली परिणाम की अनुमति देना।
- केवल धनात्मक ऐरे का परीक्षण करना और सभी-ऋणात्मक, एकल-तत्व और अंतिम बिंदु निष्कासन मामलों को छोड़ देना।
विफलता के लक्षण और समाधान
[-5] के लिए शून्य लौटाना गैर-खाली नियम का उल्लंघन करता है। यदि [1,-2,0,3] कभी भी साधारण Kadane से बेहतर नहीं होता है, तो निष्कासन स्टेट योगदान नहीं दे रहा है। पहले इनवेरिएंट लिखें, फिर एक बार में एक ट्रांज़िशन करते हुए एक छोटे ऐरे को ट्रेस करें।
प्रोडक्शन कार्यान्वयन
इनपुट रेंज के लिए पर्याप्त चौड़े एक्यूमुलेटर का उपयोग करें। अंतराल को वापस करने के लिए, प्रत्येक स्टेट के साथ प्रारंभ, निष्कासन इंडेक्स और समाप्ति मेटाडेटा रखें; स्टेट्स की संख्या स्थिर रहती है, लेकिन टाई-ब्रेकिंग नियतात्मक (deterministic) होनी चाहिए।
सत्यापन चेकलिस्ट
एक तत्व, सभी ऋणात्मक, सभी धनात्मक, मध्य ऋणात्मक को हटाना, अंतिम बिंदु को हटाना, कई इष्टतम और अधिकतम मानों का परीक्षण करें। छोटे ऐरे के लिए, एक O(n²) संदर्भ के विरुद्ध तुलना करें जो वैकल्पिक निष्कासन की गणना करता है और यादृच्छिक विभेदक परीक्षणों (randomized differential tests) का उपयोग करके Kadane चलाता है।
फॉलो-अप प्रश्न और उत्तर
यदि एक निष्कासन अनिवार्य हो तो क्या बदलता है?
आप केवल keep नहीं लौटा सकते, क्योंकि समाधान को drop का उपयोग करना चाहिए। एक-तत्व वाले ऐरे का कोई कानूनी गैर-खाली परिणाम नहीं होता है, इसलिए API को एक स्पष्ट सेंटिनल या न्यूनतम इनपुट लंबाई की आवश्यकता होती है।
क्या प्रीफिक्स योग इसे हल कर सकता है?
प्रीफिक्स योग O(n²) में निष्कासन स्थितियों और अंतरालों की गणना कर सकता है। बाएँ और दाएँ अधिकतम-सबर्रे प्रीप्रोसेसिंग O(n) स्पेस के साथ O(n) तक पहुँचती है; दो-स्टेट स्कैन अधिक स्पेस-कुशल है।
आप वास्तविक अंतराल को कैसे पुनर्प्राप्त करते हैं?
प्रत्येक स्टेट के साथ एक प्रारंभ और निष्कासन इंडेक्स रखें। पुनरारंभ करते समय प्रारंभ को रीसेट करें, वर्तमान मान को हटाते समय इंडेक्स रिकॉर्ड करें, और उस स्टेट से अंत को बैकट्रैक करें जिसने सबसे अच्छा उत्तर दिया।
स्कोरिंग रूब्रिक
- स्टेट परिभाषा: स्पष्ट रूप से बिना निष्कासन और एक निष्कासन के बीच अंतर करता है।
- सही ट्रांज़िशन: पुराने स्टेट्स का उपयोग करता है और पुनरारंभ, विस्तार और वर्तमान को हटाने को कवर करता है।
- पूर्ण बाउंड्रीज़: सभी-ऋणात्मक, एकल-तत्व, गैर-खाली और ओवरफ्लो मामलों को संभालता है।
- सटीक जटिलता: O(n) समय और O(1) अतिरिक्त स्पेस प्राप्त करता है।
- मजबूत सत्यापन: एक संदर्भ एन्यूमरेटर और बाउंड्री-केंद्रित परीक्षणों का प्रस्ताव करता है।
अनुपालन जाँच
पुष्टि करें कि स्टेट ट्रांज़िशन, गैर-खाली बाउंड्रीज़ और जटिलता के दावे सुसंगत बने रहें।
इंटरव्यू उत्तर चेकलिस्ट
दो इनवेरिएंट बताएं, दोनों ट्रांज़िशन लिखें, पुराने मानों को सहेजने और पहले-तत्व इनिशियलाइज़ेशन पर जोर दें, फिर जटिलता और यादृच्छिक विभेदक परीक्षण दें।
एक-पंक्ति का निष्कर्ष
एक निष्कासन की अनुमति देना Kadane के सन्निहित-स्टेट DP में "पहले से हटाया गया" आयाम जोड़ता है, जिससे लीनियर समय और स्थिर स्पेस में एक गैर-खाली इष्टतम प्राप्त होता है।