कोडिंग इंटरव्यू: popMax के साथ Max Stack को कैसे डिज़ाइन करें?

समस्या और संदर्भ

MaxStack को लागू करें: push(x) एक आइटम जोड़ता है, pop() शीर्ष को हटाता है और लौटाता है, top() शीर्ष को पढ़ता है, peekMax() अधिकतम मान को पढ़ता है, और popMax() शीर्ष के सबसे निकटतम अधिकतम मान को हटाता है और लौटाता है। दोहराए गए अधिकतम मान अंतिम-इन-फर्स्ट-आउट (LIFO) टाई-ब्रेक का उपयोग करते हैं; खाली-स्टैक व्यवहार एक स्पष्ट त्रुटि या खाली परिणाम होना चाहिए।

सार्वजनिक LeetCode समस्या और हाल के साक्षात्कार-प्रश्न रिकॉर्ड इसी इंटरफ़ेस का उपयोग करते हैं। यह एक प्रीफ़िक्स-न्यूनतम स्टैक से भिन्न है: popMax को एक आंतरिक नोड का पता लगाना चाहिए और शेष स्टैक क्रम को पुनर्स्थापित करना चाहिए।

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

• क्या आप पहले डुप्लिकेट-अधिकतम टाई-ब्रेक और खाली-स्टैक अनुबंध को तय करते हैं।
• क्या आप समझा सकते हैं कि एक अकेला currentMax वेरिएबल विलोपन के बाद अगले अधिकतम मान को पुनर्स्थापित क्यों नहीं कर सकता।
• क्या आप स्टैक क्रम को मान क्रम से अलग करते हैं और दोनों इंडेक्स से एक ही नोड को हटाते हैं।
• क्या आप एक परिशोधित (amortized) O(1) सहायक-स्टैक डिज़ाइन और एक O(log n) क्रमित-इंडेक्स डिज़ाइन के बीच अंतर करते हैं।

कोडिंग से पहले स्पष्टीकरण

1. क्या popMax को O(1), परिशोधित O(1) होना चाहिए, या यह O(log n) हो सकता है? यह डेटा संरचना को निर्धारित करता है।
2. डुप्लिकेट अधिकतम मानों के लिए, क्या शीर्ष के सबसे निकटतम आइटम को हटाया जाना चाहिए, या कोई भी अधिकतम स्वीकार्य है? यह नियम इंडेक्स लुकअप को बदल देता है।
3. क्या स्थिर इटरेटर, समवर्ती कॉल या पर्सिस्टेंस की आवश्यकता है? वे नोड के जीवनकाल और लॉकिंग को बदलते हैं।
4. क्या मान तुलनीय ऑब्जेक्ट हैं या सीमित पूर्णांक हैं? सीमित पूर्णांक बकेट की अनुमति देते हैं; जेनेरिक ऑब्जेक्ट्स को आम तौर पर तुलना इंडेक्स की आवश्यकता होती है।

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

“मैं प्रत्येक मान को एक नोड में एक मोनोटोनिक रूप से बढ़ते अनुक्रम संख्या के साथ रैप करता हूँ। एक doubly linked list स्टैक क्रम को सुरक्षित रखती है; एक क्रमित इंडेक्स (value, sequence) द्वारा सॉर्ट करता है, इसलिए इसकी अंतिम प्रविष्टि शीर्ष के सबसे निकटतम अधिकतम मान होती है। top सूची के टेल को पढ़ता है, peekMax इंडेक्स के टेल को पढ़ता है, और popMax उस नोड को लेता है और उसके सूची पॉइंटर्स के माध्यम से उसे अनलिंक करता है। एक संतुलित-पेड़ इंडेक्स के साथ, push, pop, peekMax, और popMax O(log n) हैं, जबकि top O(1) है। यदि केवल शीर्ष संचालन और peekMax को निरंतर समय की आवश्यकता है, तो एक सहायक मैक्स स्टैक सरल है, लेकिन popMax ईमानदारी से O(1) नहीं रह सकता है।”

चरण-दर-चरण गहन विश्लेषण

चरण 1: स्टैक क्रम को सॉर्ट किए गए क्रम से अलग करें।

प्रत्येक नोड value, एक मोनोटोनिक रूप से बढ़ता sequence, prev, और next संग्रहीत करता है। सूची का टेल स्टैक का शीर्ष है। क्रमित कुंजी (value, sequence) है; समान मानों के लिए, बड़ा अनुक्रम बाद में सॉर्ट होता है, जिससे इंडेक्स टेल शीर्ष के निकटतम अधिकतम मान बन जाता है।

चरण 2: एक हटाने योग्य क्रमित इंडेक्स चुनें।

डुप्लिकेट-जागरूक संतुलित पेड़, TreeMap के साथ एक क्रमित नोड सेट, या मान से क्रमित अनुक्रम आईडी तक दो-स्तरीय इंडेक्स का उपयोग करें। एक अकेला currentMax अपर्याप्त है: इसे हटाने के बाद, अगला अधिकतम और उसका नोड पाया जाना चाहिए।

चरण 3: सभी पाँच संचालनों को सिंक्रनाइज़ रखें।

• push: एक नोड बनाएं, इसे सूची में जोड़ें, और इसे क्रमित इंडेक्स में डालें।
• pop: सूची टेल लें, उस नोड को क्रमित इंडेक्स से हटाएं, फिर इसे अनलिंक करें।
• top: सूची टेल का मान लौटाएं।
• peekMax: क्रमित इंडेक्स टेल का मान लौटाएं।
• popMax: क्रमित इंडेक्स टेल लें, इसे इसके सूची पॉइंटर्स के माध्यम से अनलिंक करें, फिर इसे इंडेक्स से हटाएं।

स्यूडोकोड मुख्य इनवेरिएंट को दर्शाता है; कंक्रीट ट्री एपीआई भाषा-विशिष्ट है:

node = orderedByValueAndSequence.last()
orderedByValueAndSequence.erase(node.key)
unlink(node.prev, node, node.next)
return node.value

चरण 4: जटिलता और सरल विकल्प।

संतुलित पेड़ के साथ, top O(1) है और अन्य इंडेक्स संचालन O(log n) हैं; स्पेस O(n) है। यदि परिशोधित O(n) popMax स्वीकार्य है, तो एक मुख्य स्टैक और एक प्रीफ़िक्स-मैक्स स्टैक प्रत्येक गहराई पर अधिकतम को रिकॉर्ड करता है। वह आसान है, लेकिन यह बार-बार मनमाने स्थान से हटाने के लिए उपयुक्त नहीं है।

चरण 5: डुप्लिकेट, खाली स्थिति, और नोड पहचान।

अनुक्रम डुप्लिकेट ऑर्डरिंग और popMax टाई-ब्रेक दोनों को हल करता है। खाली संचालन एक सुसंगत त्रुटि लौटाते हैं। प्रत्येक नोड सूची में ठीक एक बार और इंडेक्स में एक बार दिखाई देता है; केवल उसके मान से पुनर्निर्माण करने के बजाय दोनों संरचनाओं से एक ही नोड को हटाएं।

चरण 6: क्रम और इंडेक्स का परीक्षण करें।

संदर्भ मॉडल के रूप में एक धीमी ऐरे का उपयोग करें। दो popMax कॉलों के साथ [5,1,5] का परीक्षण करें; इसे शीर्ष 5 और फिर निचले 5 को हटाना चाहिए। ऋणात्मक मान, सभी-समान मान, खाली स्थिति, वैकल्पिक push/pop, एक आंतरिक अधिकतम, बार-बार हटाना, और लंबे यादृच्छिक अनुक्रमों को कवर करें। प्रत्येक ऑपरेशन के बाद, सूची क्रम, इंडेक्स आकार और peekMax को सत्यापित करें।

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

“मैं स्टैक क्रम के लिए एक doubly linked list और अधिकतम लुकअप के लिए (value, sequence) द्वारा कुंजीबद्ध एक संतुलित क्रमित इंडेक्स का उपयोग करूँगा। अनुक्रम बढ़ रहा है, इसलिए समान अधिकतम मानों के बीच सबसे बड़ा अनुक्रम शीर्ष के सबसे निकट वाला होता है। प्रत्येक नोड में सूची पॉइंटर्स और इसकी इंडेक्स कुंजी दोनों होते हैं: pop सूची टेल लेता है, popMax इंडेक्स टेल लेता है, और दोनों दूसरी संरचना से उसी नोड को हटाते हैं। Top O(1) है, शेष ऑपरेशन O(log n) हैं, और स्पेस O(n) है। यदि साक्षात्कारकर्ता को केवल peekMax की आवश्यकता है, तो मैं कार्यान्वयन जटिलता को कम करने के लिए एक सहायक मैक्स स्टैक का उपयोग करूँगा।”

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

• केवल एक वर्तमान अधिकतम मान रखना → हटाने के बाद अगला अधिकतम अज्ञात रहता है → एक खोजने योग्य क्रमित इंडेक्स बनाए रखें।
• popMax को pop के रूप में मानना → गलत स्थिति हट जाती है और स्टैक क्रम बदल जाता है → मान इंडेक्स द्वारा नोड खोजें, फिर सूची पॉइंटर द्वारा अनलिंक करें।
• डुप्लिकेट को बिना किसी अनुक्रम के छोड़ना → शीर्ष-निकटतम अधिकतम मान सिद्ध नहीं किया जा सकता → (value, sequence) द्वारा कुंजी बनाएं।
• इंडेक्स से हटाना लेकिन सूची से नहीं → top हटाए गए नोड को लौटा सकता है → नोड पहचान साझा करें और दोनों संरचनाओं को परमाणु रूप से अपडेट करें।
• सहायक-स्टैक डिज़ाइन के लिए popMax को O(1) होने का दावा करना → मनमाना निष्कासन आमतौर पर आइटमों को स्थानांतरित करता है या स्थिति का पुनर्निर्माण करता है → परिशोधित और सबसे खराब स्थिति की सीमाओं को सटीक रूप से बताएं।

फॉलो-अप प्रश्न और उत्तर

फॉलो-अप 1: क्या प्रत्येक ऑपरेशन O(1) हो सकता है?

निश्चित-चौड़ाई वाले पूर्णांकों के लिए, बकेटेड या विशेष पूर्णांक-प्राथमिकता संरचनाएं संभव हैं, लेकिन यह सीमा कुंजी की चौड़ाई, मेमोरी और कम्प्यूटेशनल मॉडल पर निर्भर करती है। मनमाने तुलनीय ऑब्जेक्ट्स के लिए, परिशोधित, अपेक्षित और सबसे खराब स्थिति के दावों को मिलाने के बजाय ईमानदार O(log n) इंडेक्स समाधान दें।

फॉलो-अप 2: आप इसे थ्रेड-सुरक्षित (thread-safe) कैसे बनाएंगे?

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

फॉलो-अप 3: क्या होगा यदि केवल peekMax की आवश्यकता हो, popMax की नहीं?

एक मुख्य स्टैक और समान लंबाई वाले प्रीफ़िक्स-मैक्स स्टैक का उपयोग करें। Push दोनों स्टैक में नए अधिकतम को रिकॉर्ड करता है; pop दोनों से हटाता है; top और peekMax अपने संबंधित शीर्षों को पढ़ते हैं। प्रत्येक ऑपरेशन O(1) है, और डुप्लिकेट अधिकतम मानों को बार-बार रिकॉर्ड किया जाना चाहिए।