प्रॉम्प्ट और संदर्भ
push, pop, top और getMin के साथ एक स्टैक इम्प्लीमेंट करें। प्रत्येक ऑपरेशन O(1) होना चाहिए, और खाली-स्टैक का व्यवहार स्पष्ट होना चाहिए। यह प्रश्न कोडिंग, बैकएंड और लाइब्रेरी भूमिकाओं के लिए उपयुक्त है। मुख्य बात हर स्टैक डेप्थ के लिए न्यूनतम मान को बनाए रखना है, न कि किसी API को याद रखना।
इंटरव्यूअर क्या जांच रहा है
इनवेरिएंट
डेप्थ d पर सहायक स्ट्रक्चर पहले d मानों के न्यूनतम मान को स्टोर करता है। मुख्य और सहायक स्टैक की लंबाई समान रहती है।
डुप्लिकेट मिनिमम
जब कोई नया मान वर्तमान न्यूनतम मान के बराबर होता है, तो उसे फिर भी रिकॉर्ड किया जाना चाहिए। अन्यथा एक कॉपी को पॉप करने से सही न्यूनतम मान खो जाता है।
त्रुटियाँ और सीमाएँ
खाली स्टैक पर pop, top और getMin के लिए एक सुसंगत अनुबंध की आवश्यकता होती है: एक्सेप्शन, ऑप्शन, या एरर कोड। एक साइलेंट सेंटिनल सुरक्षित नहीं है।
जटिलता
प्रत्येक ऑपरेशन केवल शीर्ष (top) को छूता है, इसलिए समय O(1) है और अतिरिक्त स्पेस O(n) है। getMin के दौरान स्कैन करना इस आवश्यकता को पूरा नहीं करता है।
पहले स्पष्ट करने योग्य प्रश्न
- एक खाली ऑपरेशन को क्या वापस करना चाहिए: एक्सेप्शन, ऑप्शन, या एरर कोड?
- क्या मान नकारात्मक, दोहराए गए, या पूर्णांक सीमाओं के करीब हो सकते हैं?
- क्या एक जेनेरिक कम्पेरेटर की आवश्यकता है, या केवल पूर्णांकों की?
- क्या API को न्यूनतम इंडेक्स या ऑकरेंस काउंट वापस करना चाहिए?
- क्या थ्रेड सुरक्षा या लॉक-फ्री इम्प्लीमेंटेशन की आवश्यकता है?
- क्या परीक्षणों को अलग-अलग कॉल्स या यादृच्छिक ऑपरेशन अनुक्रमों को कवर करना चाहिए?
30-सेकंड का उत्तर
“मैं समान लंबाई के दो स्टैक रखूँगा: values और mins। mins का शीर्ष वर्तमान में मौजूद सभी मानों के न्यूनतम मान को स्टोर करता है। push पर, मैं min(x, current minimum) पुश करता हूँ; pop पर, मैं दोनों को पॉप करता हूँ; top और getMin प्रासंगिक शीर्ष को पढ़ते हैं। प्रत्येक ऑपरेशन O(1) है, जिसमें O(n) अतिरिक्त स्पेस है। मैं डुप्लिकेट मिनिमम रिकॉर्ड करता हूँ, एक खाली-स्टैक एरर अनुबंध परिभाषित करता हूँ, और एक धीमी संदर्भ सूची के विरुद्ध यादृच्छिक अनुक्रमों की जांच करता हूँ।”
चरण-दर-चरण विस्तृत उत्तर
चरण 1: इनवेरिएंट बताएं
मान लें कि S वैल्यू स्टैक है और M सहायक स्टैक है। प्रत्येक डेप्थ d के लिए, M[d], S[0..d] के न्यूनतम के बराबर होता है। उनकी लंबाई हमेशा बराबर होती है।
चरण 2: push डिज़ाइन करें
यदि M खाली नहीं है, तो M पर min(x, M.top()) पुश करें; अन्यथा x पुश करें। फिर S पर x पुश करें। नया सहायक शीर्ष प्रीफिक्स न्यूनतम है।
चरण 3: pop और क्वेरीज़ डिज़ाइन करें
Pop दोनों स्टैक से एक आइटम को हटाता है। top, S.top() को पढ़ता है, और getMin, M.top() को पढ़ता है। किसी स्कैन की आवश्यकता नहीं है।
चरण 4: डुप्लिकेट सुरक्षित रखें
2, 1, 1 पुश करने के बाद, M 2, 1, 1 होता है। एक बार पॉप करने पर भी 1 वापस आना चाहिए। केवल कड़ाई से छोटे मानों को रिकॉर्ड करने से इनवेरिएंट टूट जाता है।
चरण 5: त्रुटियाँ और प्रकार परिभाषित करें
एक खाली स्टैक EmptyStackError थ्रो कर सकता है या एक टाइप्ड Result वापस कर सकता है। एक जेनेरिक इम्प्लीमेंटेशन को टोटल-ऑर्डर कम्पेरेटर स्वीकार करना चाहिए और समानता को लगातार परिभाषित करना चाहिए।
चरण 6: जटिलता सिद्ध करें और परीक्षण करें
सभी चार ऑपरेशन O(1) हैं, जिसमें O(n) सहायक स्पेस है। एक यादृच्छिक परीक्षण ओरेकल के रूप में एक सामान्य सूची बनाए रख सकता है और हर ऑपरेशन के बाद top, न्यूनतम, आकार और त्रुटियों की तुलना कर सकता है।
~~~python class MinStack: def push(self, value): ... def pop(self): ... def top(self): ... def get_min(self): ... ~~~
मॉडल उत्तर
“मैं values और mins बनाए रखूँगा। mins[i], values[0..i] का न्यूनतम है, इसलिए स्टैक की लंबाई बराबर होती है। push मान और उसके नए प्रीफिक्स न्यूनतम को स्टोर करता है; एक खाली mins स्टैक सीधे मान को स्टोर करता है। pop दोनों से हटाता है, जबकि top और getMin संबंधित शीर्ष को पढ़ते हैं।
डुप्लिकेट मिनिमम को स्टोर किया जाना चाहिए। 2, 1, 1 के लिए, mins 2, 1, 1 है; अन्यथा एक pop गलत तरीके से 2 लौटाएगा। खाली ऑपरेशन एक स्पष्ट एरर अनुबंध का उपयोग करते हैं। समय प्रति ऑपरेशन O(1) है और अतिरिक्त स्पेस O(n) है। मैं सूची-आधारित ओरेकल के विरुद्ध खाली, नकारात्मक, डुप्लिकेट, वैकल्पिक और यादृच्छिक अनुक्रमों का परीक्षण करूँगा।”
सामान्य गलतियाँ
- getMin के दौरान वैल्यू स्टैक को स्कैन करना, जिससे यह O(n) हो जाता है।
- केवल कड़ाई से छोटे मानों को रिकॉर्ड करना और डुप्लिकेट मिनिमम को खो देना।
- केवल मुख्य स्टैक को पॉप करना और स्ट्रक्चर्स को डीसिंक्रनाइज़ करना।
- एक एकल ग्लोबल न्यूनतम रखना जिसे pop के बाद पुनर्स्थापित नहीं किया जा सकता है।
- खाली स्टैक के लिए शून्य लौटाना और इसे मान्य इनपुट के साथ भ्रमित करना।
- नकारात्मक मानों या पूर्णांक सीमाओं की उपेक्षा करना।
- बिना किसी औचित्य के एमॉर्टाइज़्ड बाउंड को सख्त O(1) कहना।
- कम्पेरेटर को परिभाषित किए बिना जेनेरिक-ऑब्जेक्ट समर्थन का दावा करना।
फॉलो-अप प्रश्न
फॉलो-अप 1: क्या आप एक स्टैक का उपयोग कर सकते हैं?
हाँ। प्रत्येक प्रविष्टि में मान और प्रीफिक्स न्यूनतम का एक युग्म (pair) स्टोर करें। इनवेरिएंट अपरिवर्तित रहता है और स्पेस O(n) बना रहता है।
फॉलो-अप 2: आप getMax कैसे जोड़ेंगे?
एक मैक्सिमम-प्रीफिक्स स्टैक भी बनाए रखें, या प्रत्येक प्रविष्टि में मान, min और max स्टोर करें। समय प्रति ऑपरेशन O(1) और कुल स्पेस O(n) बना रहता है।
फॉलो-अप 3: आप न्यूनतम संख्या (count) कैसे लौटाएंगे?
प्रत्येक सहायक प्रविष्टि में min और count स्टोर करें। समान मान count को बढ़ाते हैं, और pop पिछली प्रविष्टि को पुनर्स्थापित करता है। डुप्लिकेट और रोलबैक सिमेंटिक्स को स्पष्ट रूप से परिभाषित करें।
फॉलो-अप 4: आप इसे थ्रेड-सुरक्षित कैसे बनाएंगे?
प्रत्येक लॉजिकल ऑपरेशन के चारों ओर एक एकल म्यूटेक्स (mutex) के साथ दोनों स्टैक को सुरक्षित करें। अलग-अलग लॉक एक असंगत मध्यवर्ती स्थिति को उजागर कर सकते हैं। लॉक-फ्री डिज़ाइनों के लिए एक एटॉमिक समग्र स्थिति और मेमोरी-रिक्लेमेशन चर्चा की आवश्यकता होती है।
फॉलो-अप 5: आप शुद्धता कैसे सिद्ध करते हैं?
इंडक्शन (गणितीय आगमन) का प्रयोग करें। खाली स्टैक इनवेरिएंट को संतुष्ट करता है; push नए प्रीफिक्स न्यूनतम की गणना करता है; pop पिछले रिकॉर्ड को पुनर्स्थापित करता है। इसलिए getMin हमेशा वर्तमान वैल्यू स्टैक का न्यूनतम मान लौटाता है।