इंटरव्यूअर क्या मूल्यांकन करता है
डुप्लिकेट वाले संभावित पूर्णांक ऐरे को इन-प्लेस ही शब्दकोश के अनुसार ठीक अगले बड़े क्रमचय में बदलें; यदि वर्तमान क्रम अधिकतम है, तो सबसे छोटा आरोही क्रमचय बनाएँ।
सीमाएँ और शर्तें (Constraints and boundaries)
- O(1) अतिरिक्त स्पेस और केवल स्वैप या रिवर्स का उपयोग करें।
- डुप्लिकेट मान अलग पहचान नहीं हैं, लेकिन तुलनाएँ संख्यात्मक हैं।
- खाली और एक तत्व वाले ऐरे अपरिवर्तित रहते हैं।
- परिणाम विश्व स्तर पर आसन्न (globally adjacent) लेक्सिकोग्राफ़िक क्रमचय होना चाहिए, कोई मनमाना स्थानीय स्वैप नहीं।
सबसे दायाँ पिवट ढूँढें
दाईं ओर से पहले ऐसे इंडेक्स i के लिए स्कैन करें जहाँ बायाँ मान दाएँ मान से पूरी तरह से कम (strictly less) हो। प्रत्यय (suffix) पहले से ही गैर-बढ़ता (non-increasing) है। यदि कोई पिवट मौजूद नहीं है, तो पूरा ऐरे अधिकतम है; न्यूनतम क्रमचय प्राप्त करने के लिए इसे उलट दें।
स्वैप करें और प्रत्यय को न्यूनतम करें
पिवट मिलने के बाद, nums[i] से बड़े पहले मान के लिए दाईं ओर से स्कैन करें। चूँकि प्रत्यय गैर-बढ़ता है, वह पहला उम्मीदवार सबसे छोटा संभव बड़ा मान होता है। इसे पिवट के साथ स्वैप करें, फिर i के बाद के प्रत्यय को आरोही बनाने के लिए उलट दें।
30-सेकंड का उत्तर ढांचा
“दाईं ओर से पहले बढ़ते पिवट i के लिए स्कैन करें। यदि कोई मौजूद नहीं है, तो अधिकतम अवरोही ऐरे को उलट दें। अन्यथा nums[i] से बड़ा सबसे दायाँ मान ढूँढें, उन्हें स्वैप करें, और प्रत्यय को उलट दें। प्रत्यय विपरीत दिशा में व्यवस्थित शुरू होता है, इसलिए यह O(n) समय और O(1) स्पेस में न्यूनतम संभव वृद्धि करता है।”
उत्तर देने से पहले स्पष्ट करने वाले प्रश्न
- क्या बदलाव इन-प्लेस ही होना चाहिए? अतिरिक्त स्पेस किसी कॉपी को सॉर्ट करने की अनुमति देगा, जबकि इन-प्लेस के लिए रिवर्स करने की आवश्यकता होती है।
- क्या लेक्सिकोग्राफ़िक क्रम संख्यात्मक है या स्ट्रिंग-आधारित? नकारात्मक और बहु-अंकीय मान भिन्न होते हैं।
- क्या मान दोहराए जा सकते हैं? डुप्लिकेट के लिए पिवट और स्वैप उम्मीदवार दोनों के लिए सख्त तुलना (strict comparisons) की आवश्यकता होती है।
चरण-दर-चरण विस्तृत विश्लेषण
[1,2,3] के लिए, 1 पर पिवट प्रत्यय के सबसे छोटे बड़े मान 2 के साथ स्वैप होता है, जिससे प्रत्यय के रिवर्सल के बाद [2,1,3] बचता है। [3,2,1] के लिए, कोई पिवट मौजूद नहीं है, इसलिए रिवर्स करने पर [1,2,3] प्राप्त होता है।
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
j = n - 1
while nums[j] <= nums[i]:
j -= 1
swap(nums[i], nums[j])
reverse(nums, i + 1, n - 1)पिवट उम्मीदवारों को छोड़ते समय “बड़ा या बराबर” और स्वैप उम्मीदवारों को छोड़ते समय “छोटा या बराबर” का उपयोग करें, जिससे एक सख्त वृद्धि (strict increase) सुनिश्चित हो सके। सॉर्ट करने के बजाय रिवर्स करें क्योंकि प्रत्यय पहले से ही व्यवस्थित है, इसलिए रिवर्सल लीनियर और इन-प्लेस रहता है।
मॉडल उच्च-गुणवत्ता वाला उत्तर
“अगला क्रमचय सबसे दाईं ओर की संभावित स्थिति को बदलता है और उसके बाद की सभी चीज़ों को यथासंभव छोटा बनाता है। मैं सबसे दायाँ पिवट ढूँढता हूँ जहाँ बायाँ मान दाएँ मान से सख्त रूप से कम हो, इसे इससे बड़े सबसे दाएँ मान के साथ स्वैप करता हूँ, और प्रत्यय को उलट देता हूँ। कोई पिवट न होने का अर्थ है कि ऐरे अधिकतम है, इसलिए मैं पूरे ऐरे को उलट देता हूँ। स्कैन और रिवर्सल O(n) हैं और एल्गोरिदम निरंतर अतिरिक्त वेरिएबल्स का उपयोग करता है।”
सामान्य गलतियाँ
- बाईं ओर से पिवट ढूँढना और उच्च-क्रम की स्थिति को बदलना।
- प्रत्यय को न्यूनतम किए बिना स्वैप के बाद रुक जाना।
- स्वैप उम्मीदवार के लिए 'बड़ा-या-बराबर' का उपयोग करना, जिससे डुप्लिकेट सख्त रूप से बढ़ने में विफल हो जाते हैं।
- प्रत्यय पर सामान्य सॉर्ट कॉल करना और इन-प्लेस बाधा का उल्लंघन करना।
- एक अवरोही ऐरे को अपरिवर्तित लौटाना जब उसे न्यूनतम क्रम में रैप होना चाहिए।
विफलता के लक्षण और समाधान
यदि [1,3,2] बन जाता है [3,1,2], तो पिवट बहुत बाईं ओर है; सही परिणाम [2,1,3] है। यदि [1,1,5] समान मानों को स्वैप करता है, तो सख्त तुलना सीमा गलत है।
प्रोडक्शन कार्यान्वयन
एक म्यूटेबल रैंडम-एक्सेस अनुक्रम स्वीकार करें और दो पॉइंटर्स के साथ रिवर्स करें। यदि तुलना में ओवरफ्लो हो सकता है या भाषा का क्रम भिन्न है, तो इंटरफ़ेस सीमा पर तुलनित्र (comparator) और अमान्य-इनपुट नीति को परिभाषित करें।
सत्यापन चेकलिस्ट
खाली, एक तत्व, आरोही, अवरोही, डुप्लिकेट, अंत में एक पिवट, और कई समान ऑप्टिमा का परीक्षण करें। छोटे ऐरे के लिए, सभी अलग-अलग क्रमचय उत्पन्न करें, उन्हें शब्दकोश के अनुसार सॉर्ट करें, और सत्यापित करें कि फ़ंक्शन अगला आइटम लौटाता है या पहले वाले पर वापस जाता है।
फ़ॉलो-अप प्रश्न और उत्तर
पिवट सबसे दाईं ओर ही क्यों होना चाहिए?
अधिक दाईं ओर का पिवट निचले क्रम की स्थिति को बदलता है। इसलिए सबसे छोटे संभव बड़े मान को चुनना और उसके प्रत्यय को न्यूनतम करना मान्य क्रमों को छोड़े बिना आसन्न क्रमचय देता है।
प्रत्यय को सीधे क्यों उलटा जा सकता है?
दाएँ से बाएँ पिवट स्कैन यह साबित करता है कि प्रत्यय गैर-बढ़ता है। स्वैप के बाद, इसे उलटने से बिना किसी सामान्य सॉर्ट के सबसे छोटा आरोही क्रम पुनर्स्थापित हो जाता है।
kth अगले क्रमचय के बारे में क्या?
ऑपरेशन को दोहराने में O(k n) की लागत आती है। बड़े k के लिए, रैंक/अन-रैंक या गिनती के तरीके सीधे छलांग लगा सकते हैं, लेकिन उन्हें कॉम्बिनेटरियल काउंटिंग और डुप्लिकेट हैंडलिंग की आवश्यकता होती है।
स्कोरिंग रूब्रिक
- पिवट: सबसे दाईं ओर की सख्त वृद्धि को ढूँढता है।
- स्वैप: दाईं ओर से पहला सख्त बड़ा मान चुनता है।
- प्रत्यय: इसे सबसे छोटे आरोही क्रम में उलटता है।
- सीमाएँ: अवरोही, डुप्लिकेट, खाली, और एक तत्व वाले ऐरे को कवर करता है।
- जटिलता: O(n) समय और O(1) अतिरिक्त स्पेस देता है।
अनुपालन जाँच (Compliance check)
पुष्टि करें कि तीनों चरण, सीमांत उदाहरण, और जटिलता का दावा सुसंगत बने रहें।
इंटरव्यू उत्तर चेकलिस्ट
दाईं ओर के सबसे छोटे बदलाव की व्याख्या करें, पिवट, स्वैप और रिवर्स लिखें, सख्त तुलनाओं के लिए डुप्लिकेट उदाहरण का उपयोग करें, फिर जटिलता और छोटे क्रमचयों का संपूर्ण परीक्षण दें।
एक पंक्ति का निष्कर्ष
अगला क्रमचय सबसे दाएँ पिवट, सबसे छोटे संभव बड़े स्वैप, और लीनियर समय में प्रत्यय के रिवर्सल द्वारा इन-प्लेस पाया जाता है।