कोडिंग इंटरव्यू: मोनोटोनिक स्टैक के साथ Next Greater Element II को हल करें

इंटरव्यूअर क्या मूल्यांकन करता है

एक सर्कुलर पूर्णांक ऐरे दिए जाने पर, प्रत्येक तत्व के लिए दक्षिणावर्त (clockwise) दिशा में मिलने वाला पहला स्ट्रिक्टली बड़ा मान लौटाएं, या कोई मान न होने पर -1 लौटाएं। इनपुट में डुप्लिकेट, मोनोटोनिक रन, या सभी समान मान हो सकते हैं।

सीमाएं और बाउंड्री स्थितियां

“बड़ा (Greater)” स्ट्रिक्ट है; एक समान मान इंडेक्स को रिज़ॉल्व नहीं कर सकता।
इंडेक्स i, i+1 से n-1 तक खोज करता है, फिर 0 पर रैप होता है।
प्रत्येक स्थिति को अधिकतम एक उत्तर प्राप्त होता है; दूसरे पास को पहले से रिज़ॉल्व किए गए परिणाम को ओवरराइट नहीं करना चाहिए।
O(n) समय और O(n) अतिरिक्त स्थान का लक्ष्य रखें।

30-सेकंड उत्तर फ्रेमवर्क

“मैं उन इंडेक्सों का एक घटता हुआ (decreasing) स्टैक रखता हूँ जो अभी भी एक बड़े मान की प्रतीक्षा कर रहे हैं। मैं एक वर्चुअल दोगुने ऐरे को स्कैन करता हूँ: एक स्ट्रिक्टली बड़ा वर्तमान मान स्टैक की प्रविष्टियों को पॉप और रिज़ॉल्व करता है; इंडेक्स केवल पहले पास के दौरान प्रवेश करते हैं, जबकि दूसरा पास रैपअराउंड उम्मीदवारों की आपूर्ति करता है। प्रत्येक इंडेक्स को अधिकतम एक बार पुश और पॉप किया जाता है, इसलिए एल्गोरिदम लीनियर है।”

उत्तर की प्रतीक्षा कर रही स्थितियों को स्टोर करना

मानों के बजाय इंडेक्स स्टोर करें ताकि एल्गोरिदम परिणाम लिख सके और डुप्लिकेट स्थितियों को सुरक्षित रख सके। स्टैक के नीचे से ऊपर तक मानों को गैर-बढ़ता (non-increasing) रखें। एक बड़ा वर्तमान मान उन सभी छोटे प्रतीक्षारत मानों को रिज़ॉल्व करता है जिन्हें वह पॉप कर सकता है।

रैपअराउंड को एक सीमित स्कैन में बदलना

0 से 2n-2 तक i के लिए nums[i % n] पढ़ें। जब i, n से कम हो, तो पुरानी प्रविष्टियों को रिज़ॉल्व करने के बाद इंडेक्स को पुश करें; दूसरी विज़िट पर, केवल शेष स्टैक को रिज़ॉल्व करने के लिए इसका उपयोग करें। यह ऐरे को कॉपी करने से बचाता है और अनंत लूप को रोकता है।

स्ट्रिक्ट तुलना और डुप्लिकेट्स को संभालना

केवल तभी पॉप करें जब nums[current] > nums[stackTop] हो। ग्रेटर-दैन-या-इक्वल (>=) गलत तरीके से समान मानों को एक-दूसरे को रिज़ॉल्व करने की अनुमति देगा; लेस-दैन (<) घटते हुए इनवेरिएंट को तोड़ता है। अनसुलझे इंडेक्स प्रारंभिक -1 को बनाए रखते हैं।

उत्तर देने से पहले स्पष्ट करने वाले प्रश्न

क्या “next” स्ट्रिक्टली बड़ा है? ग्रेटर-या-इक्वल की अनुमति देने से पॉप की स्थिति और डुप्लिकेट का व्यवहार बदल जाता है।
क्या ऐरे खाली हो सकता है? लागू करने से पहले रिटर्न के आकार को परिभाषित करें।
क्या परिणाम में मान होने चाहिए या इंडेक्स? दूरियों और इंडेक्सों को अलग-अलग रैपअराउंड गणनाओं की आवश्यकता होती है।

चरण-दर-चरण विस्तृत विश्लेषण

प्रत्येक परिणाम को -1 पर इनिशियलाइज़ करें और एक खाली स्टैक रखें। वर्चुअल स्थिति i के लिए, index = i % n सेट करें और value = nums[index] पढ़ें। पहले उन स्टैक इंडेक्सों को रिज़ॉल्व करें जिनका मान छोटा है; जब i, n से कम हो, तो index को पुश करें क्योंकि इसकी पूरी दक्षिणावर्त खोज अभी बाकी है। दूसरा पास कभी भी पुश नहीं करता है, इसलिए प्रत्येक इंडेक्स एक बार प्रवेश करता है।

text

result = [-1] * n
stack = []
for i in range(2 * n - 1):
    index = i % n
    while stack and nums[stack[-1]] < nums[index]:
        result[stack.pop()] = nums[index]
    if i < n:
        stack.append(index)

[1,2,1] के लिए, अंतिम 1 रैप करने के बाद 2 को देखता है, जबकि 2 के पास कोई स्ट्रिक्टली बड़ा मान नहीं है। शेष स्टैक इंडेक्स सही ढंग से -1 बनाए रखते हैं।

मॉडल उच्च-गुणवत्ता वाला उत्तर

“मैं उन इंडेक्सों को एक गैर-बढ़ते (non-increasing) स्टैक में स्टोर करता हूँ जिन्हें कोई उत्तर नहीं मिला है। मैं i % n के साथ ऐरे को तार्किक रूप से दो बार स्कैन करता हूँ; स्टैक के शीर्ष से स्ट्रिक्टली बड़ा वर्तमान मान उस इंडेक्स को पॉप और रिज़ॉल्व करता है। मैं प्रत्येक इंडेक्स को केवल उसकी पहली विज़िट पर ही पुश करता हूँ, ताकि दूसरा पास बिना किसी दोहराव के रैपअराउंड को संभाल सके। परिणाम -1 से शुरू होते हैं, जिससे समान ऐरे और अनुपलब्ध उत्तर सही हो जाते हैं। प्रत्येक इंडेक्स को अधिकतम एक बार पुश और पॉप किया जाता है, जिससे O(n) समय और O(n) स्पेस मिलता है।”

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

सर्कुलैरिटी को संभालने के लिए ऐरे को तीन बार कॉपी करना।
दूसरे पास में इंडेक्सों को फिर से पुश करना, जिससे दोहराव वाला कार्य या ओवरराइट हो जाता है।
ग्रेटर-दैन-या-इक्वल का उपयोग करना और समान मानों को बड़ा मानना।
बिना किसी स्टैक इनवेरिएंट को बताए दाईं ओर से स्कैन करना, जिससे उत्तर पहला बड़ा मान नहीं होता।
परिणामों को अन-इनिशियलाइज़्ड छोड़ना और स्कैन के बाद स्टैक को ठीक करने का प्रयास करना।

विफलता के लक्षण और समाधान

यदि [1,1,1] एक गैर--1 मान लौटाता है, तो समानता का नियम गलत है। यदि [1,2,1] में अंतिम 1, -1 लौटाता है, तो रैपअराउंड छूट गया था। स्टैक इंडेक्सों और मानों को ट्रेस करें और पुष्टि करें कि प्रत्येक पॉप में स्ट्रिक्टली बड़ा वर्तमान मान हो।

प्रोडक्शन कार्यान्वयन

इनपुट के लिए पर्याप्त रूप से बड़े इंडेक्स प्रकार का उपयोग करें। जब मेमोरी कम हो तो ऐरे को कॉपी करने से बचें। दूरी लौटाने के लिए, इंडेक्स j को रिज़ॉल्व करते समय (index - j + n) % n की गणना करें, और परिभाषित करें कि क्या शून्य दूरी की अनुमति है।

सत्यापन चेकलिस्ट

खाली इनपुट, एक तत्व, सभी समान, स्ट्रिक्टली बढ़ते, स्ट्रिक्टली घटते, दोहराए गए शिखर, और यादृच्छिक (random) ऐरे का परीक्षण करें। छोटे इनपुट के लिए, एक O(n²) संदर्भ के साथ तुलना करें जो यादृच्छिक अंतर परीक्षणों (randomized differential tests) का उपयोग करके प्रत्येक इंडेक्स से दक्षिणावर्त स्कैन करता है।

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

प्रत्येक इंडेक्स को केवल एक बार ही पॉप क्यों किया जा सकता है?

एक बार जब किसी इंडेक्स को अपना पहला स्ट्रिक्टली बड़ा मान मिल जाता है, तो वह स्टैक छोड़ देता है। कोई दूर का तत्व पहला बड़ा मान नहीं हो सकता। प्रत्येक इंडेक्स एक बार प्रवेश करता है और एक बार निकलता है, इसलिए कुल पॉपिंग O(n) है।

ग्रेटर-या-इक्वल के लिए क्या बदलता है?

जब वर्तमान मान स्टैक के शीर्ष से कम या उसके बराबर हो तो पॉप करें, फिर परिभाषित करें कि चक्र के चारों ओर समान मानों को कैसा व्यवहार करना चाहिए, जिसमें यह भी शामिल है कि क्या कोई तत्व बाद की विज़िट पर खुद को रिज़ॉल्व कर सकता है।

यदि इनपुट एक अनंत दोहराने वाली स्ट्रीम हो तो क्या होगा?

प्रत्येक स्थिति के रिज़ॉल्व होने की प्रतीक्षा न करें। एक सीमित अवलोकन विंडो या टाइमआउट सेट करें। एक निश्चित ऐरे के लिए, दो पास प्रत्येक संभावित बाद के उम्मीदवार को कवर करते हैं।

स्कोरिंग रूब्रिक

इनवेरिएंट: व्याख्या करता है कि घटता हुआ स्टैक उत्तरों की प्रतीक्षा कर रहे इंडेक्सों को रखता है।
सर्कुलर हैंडलिंग: बिना कॉपी किए या अनंत लूप के दो सीमित पास का उपयोग करता है।
डुप्लिकेट बाउंड्री: स्ट्रिक्ट तुलना का उपयोग करता है और अनसुलझे -1 मानों को सुरक्षित रखता है।
कॉम्प्लेक्सिटी: O(n) समय और O(n) अतिरिक्त स्थान प्रदान करता है।
सत्यापन: एक O(n²) ओरेकल और यादृच्छिक, डुप्लिकेट और मोनोटोनिक परीक्षण शामिल हैं।

अनुपालन जांच

पुष्टि करें कि स्टैक इनवेरिएंट, सर्कुलर बाउंड्री और कॉम्प्लेक्सिटी का दावा सुसंगत रहे।

साक्षात्कार उत्तर चेकलिस्ट

बताएं कि स्टैक इंडेक्स एक बड़े मान की प्रतीक्षा करते हैं, फिर i % n, दो पास, स्ट्रिक्ट पॉपिंग, प्रति इंडेक्स एक पुश, और एमॉर्टाइज़्ड कॉम्प्लेक्सिटी की व्याख्या करें।

एक-वाक्य का निष्कर्ष

एक सर्कुलर नेक्स्ट-ग्रेटर क्वेरी दो इंडेक्स पास और एक घटते हुए मोनोटोनिक स्टैक के साथ लीनियर हो जाती है, जबकि स्ट्रिक्ट तुलना और -1 इनिशियलाइज़ेशन डुप्लिकेट और अनुपलब्ध-मान शब्दार्थ को बनाए रखते हैं।