टीएल;डीआर
- समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
- दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ३.५: स्टैक को ऐसे क्रमबद्ध करो कि सबसे छोटे मान ऊपर हों। सिर्फ एक अतिरिक्त स्टैक। साफ जावा में इन्सर्शन-सॉर्ट जैसी सोच।
- जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।
आपके पास थालियों का बिखरा ढेर है। सिर्फ सबसे ऊपर वाली थाली उठा सकते हो, और एक खाली साइड टेबल मिलती है। खत्म होने पर सबसे हल्की थाली ऊपर चाहिए (सबसे छोटा मान ऊपर)। फर्श पर पंक्ति नहीं बना सकते। तीसरा ढेर नहीं। यही पाबंदी सॉर्ट स्टैक की पूरी पहेली है।
यह पोस्ट जावा में बिल्कुल शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू वाली स्टैक-सॉर्ट समस्याओं का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ३, स्टैक और कतार।
१. रोज़मर्रा की उपमा
दो ढेर गिने-हुए कार्ड सोचो:
- स्रोत स्टैक
s: बिखरा ढेर जिसे क्रमबद्ध छोड़ना है (आखिर में जवाब फिरsमें भरते हो)। - अस्थायी स्टैक
r: तुम्हारी एकमात्र साइड टेबल। इसमें बढ़ता हुआ क्रमबद्ध क्रम रहता है। - सिर्फ पुश, पॉप और ऊपर झाँकना (
peek)। कोई ऐरे, लिस्ट या हैश मैप नहीं।
चाल इन्सर्शन सॉर्ट जैसी लगती है। s से एक कार्ड लो। r से बड़े कार्ड वापस s पर पार्क करो जब तक जगह न बने। उसे r पर रखो। दोहराओ। जब s खाली हो, r को s पर उंडेलो ताकि वांछित क्रम मिल जाए।
२. समस्या सादे शब्दों में
इनपुट: पूर्णांकों (या तुलनीय मानों) का एक स्टैक। ऊपर वही है जो pop लौटाता है।
आउटपुट: वही स्टैक, ऐसा क्रमबद्ध कि सबसे छोटे मान ऊपर हों। बड़े मान नीचे की ओर बैठें।
नियम:
- एक अतिरिक्त अस्थायी स्टैक इस्तेमाल कर सकते हो।
- ऐरे, लिंक्ड लिस्ट, वृक्ष या अन्य संग्रह बफ़र के रूप में नहीं।
- स्थिरांक और कुछ स्थानीय चर (हाथ में पकड़ा मान) ठीक हैं।
उदाहरण (सबसे दायाँ मान ऊपर है):
| पहले (तल → ऊपर) | बाद (तल → ऊपर) | ऊपर अंतिम |
|---|---|---|
3, 1, 4, 2 |
4, 3, 2, 1 |
१ |
5 |
5 |
५ |
| खाली | खाली | लागू नहीं |
2, 2, 1 |
2, 2, 1 |
१ |
1, 2, 3 (ऊपर ३) |
3, 2, 1 |
१ |
अगर तल→ऊपर 1, 2, 3 है, ऊपर ३ (सबसे बड़ा) है। क्रम के बाद तल→ऊपर 3, 2, 1 हो ताकि ऊपर १ (सबसे छोटा) रहे।
कोड से पहले स्पष्ट करो:
- सबसे छोटा ऊपर, या सबसे बड़ा? (यहाँ: सबसे छोटा ऊपर।)
- डुप्लिकेट? (हाँ। बराबर मानों में स्थिर क्रम ज़रूरी नहीं।)
- रिकर्शन? रिकर्शन खुद एक छिपा स्टैक है। अक्सर सिर्फ स्पष्ट अस्थायी स्टैक वाली इटरेटिव विधि चाहिए।
- दी गई स्टैक बदलनी है या नई लौटानी? अंत में
sफिर से भरकर बदलो।
३. पहले सोचो (अस्थायी स्टैक से इन्सर्शन)
जो नहीं कर सकते
सब कुछ ऐरे में डालो, Arrays.sort चलाओ, वापस पुश करो। "कोई और संरचना नहीं" का नियम टूट जाता है।
इन्सर्शन का ख्याल
अस्थायी स्टैक r को ऐसे रखो कि सबसे बड़ा ऊपर हो (और सबसे छोटा r के तल पर)। फिर:
१. s से tmp पॉप करो।
२. जब तक r खाली न हो और r.peek() > tmp, r से पॉप कर उन मानों को s पर वापस पुश करो। वे tmp के नीचे r पर बैठने के लिए बहुत बड़े हैं।
३. tmp को r पर पुश करो। अब मौजूदा सामग्री में r का ऊपर अब भी सबसे बड़ा है।
४. जब तक s खाली न हो, दोहराओ।
५. r से सब कुछ s पर पॉप करो। हर पॉप अगला बड़ा मान s पर रखता है, इसलिए अंत में s के ऊपर सबसे छोटा रहता है।
बड़े मान क्यों वापस s पर पार्क? क्योंकि अस्थायी स्टैक एक ही है। स्रोत स्टैक ही कानूनी पार्किंग है। वे मान बाद में फिर घुसेंगे, जैसे इन्सर्शन सॉर्ट तत्वों को दोबारा देखता है।
चाल: तल → ऊपर 3, 1, 4, 2 (ऊपर २)
| चरण | tmp |
काम | s (तल → ऊपर) |
r (तल → ऊपर) |
|---|---|---|---|---|
| शुरू | 3, 1, 4, 2 |
खाली | ||
| १ | २ | r खाली, पुश २ |
3, 1, 4 |
2 |
| २ | ४ | 2 > 4? नहीं, पुश ४ |
3, 1 |
2, 4 |
| ३ | १ | 4 > 1, ४ को s पर; 2 > 1, २ को s पर; पुश १ |
3, 4, 2 |
1 |
| ४ | २ | 1 > 2? नहीं, पुश २ |
3, 4 |
1, 2 |
| ५ | ४ | 2 > 4? नहीं, पुश ४ |
3 |
1, 2, 4 |
| ६ | ३ | 4 > 3, ४ को s पर; 2 > 3? नहीं, पुश ३ |
4 |
1, 2, 3 |
| ७ | ४ | 3 > 4? नहीं, पुश ४ |
खाली | 1, 2, 3, 4 |
| कॉपी | r → s उंडेलो |
4, 3, 2, 1 |
खाली |
s का ऊपर १। काम पूरा।
४. जावा हल
सिखाने के लिए java.util.Stack, या push, pop, peek, isEmpty वाला कोई भी लीफो प्रकार।
import java.util.Stack;
/**
* Sorts stack so smallest values end on top.
* Uses one temporary stack. Insertion-sort style moves.
*/
void sortStack(Stack<Integer> s) {
Stack<Integer> r = new Stack<Integer>();
while (!s.isEmpty()) {
int tmp = s.pop();
// Park larger values back onto s so tmp can sit on r.
while (!r.isEmpty() && r.peek() > tmp) {
s.push(r.pop());
}
r.push(tmp);
}
// r has largest on top. Reverse onto s so smallest ends on top.
while (!r.isEmpty()) {
s.push(r.pop());
}
}
अगर समस्या सबसे बड़ा ऊपर माँगे, तुलना r.peek() < tmp कर दो और अंतिम कॉपी दोबारा सोचो, या छोटे-ऊपर वाले क्रम से सॉर्ट कर उन्हीं दो स्टैक से पलट दो। कोड से पहले ज़रूरी क्रम ज़ोर से कहो।
छोटा ड्राइवर:
Stack<Integer> s = new Stack<Integer>();
s.push(3);
s.push(1);
s.push(4);
s.push(2); // top is 2
sortStack(s);
// pop order: 1, 2, 3, 4
५. जटिलता तालिका
| तरीका | समय | अतिरिक्त जगह | नोट |
|---|---|---|---|
| अस्थायी स्टैक (इन्सर्शन अंदाज़) | सबसे खराब ओ(एन²) | अस्थायी स्टैक के लिए ओ(एन) | एन मान कई बार आ-जा सकते हैं |
| लगभग क्रमबद्ध (भाग्य) | ओ(एन) के पास | ओ(एन) | अनुकूल क्रम पर कम पार्किंग |
| ऐरे + सॉर्ट (यहाँ मना) | ओ(एन लॉग एन) | ओ(एन) | एक-अतिरिक्त-स्टैक नियम तोड़ता है |
एन = स्टैक के तत्वों की संख्या। सबसे खराब इनपुट उल्टे क्रम जैसा लगता है, बहुत पार्किंग के साथ। अतिरिक्त जगह दूसरी स्टैक (अधिकतम एन) और ओ(१) स्थानीय चर। सिर्फ लीफो नियमों में सब कुछ फिर से रखने पर ओ(एन) से कम अतिरिक्त स्टैक जगह मुश्किल है।
६. किनारे के मामले और आम गलतियाँ
इंटरव्यूअर ये छेड़ते हैं:
- खाली स्टैक → दोनों लूप कुछ नहीं करते। ठीक।
- एक तत्व →
rपर पॉप,sपर वापस। सही। - सभी बराबर → सख्त
>सेr.peek() > tmpकभी सच नहीं। डुप्लिकेट वहीं रहते हैं। अच्छा। - पहले से छोटा ऊपर → फिर भी
rसे गुज़र सकता है। पहले शुद्धता; जल्दी बाहर निकलना वैकल्पिक। - सख्ती से घटते ऊपर → बहुत पार्किंग। फिर भी ओ(एन²) और सही।
- ऋणात्मक और शून्य →
Integerपर तुलना वैसी ही चलती है।
आम गलतियाँ:
१. गलत तुलना। r.peek() < tmp r पर उल्टा क्रम बनाता है। कॉपी के बाद s पर सबसे बड़ा ऊपर आ सकता है, या शर्तें मिला दो तो अफ़रातफ़री।
२. अंतिम उंडेलना भूलना। जवाब r पर छोड़ दिया तो कॉलर अगर s देखे तो फेल।
३. दूसरी बफ़र क़िस्म। पार्किंग के लिए ArrayList नियम तोड़ता है, भले कोड "चल जाए"।
४. बिना पीक पॉप के बाद तुलना। r से s ले जाने से पहले हमेशा पीक (या मान रखो)।
५. अनंत लूप। बाहरी लूप में गलती से tmp फिर s पर बिना प्रगति के डाल दो तो घूमते रहोगे। tmp को स्थानीय चर में रखो जब तक वह r पर न बैठे।
अगर एपीआई नल स्टैक मानती हो:
void sortStackSafe(Stack<Integer> s) {
if (s == null) {
return;
}
sortStack(s);
}
७. दोस्त को समझाने वाला सार
सॉर्ट स्टैक पूछता है: स्टैक को ऐसे फिर क्रम दो कि सबसे छोटे मान ऊपर हों, सिर्फ एक अतिरिक्त स्टैक से।
१. अस्थायी स्टैक r रखो। उसे ऐसा बढ़ाओ कि r के ऊपर सबसे बड़ा हो।
२. इनपुट से एक मान tmp पॉप करो।
३. जब तक r का ऊपर tmp से बड़ा हो, उन बड़े मानों को इनपुट पर वापस पार्क करो।
४. tmp को r पर पुश करो। इनपुट खाली होने तक दोहराओ।
५. r को इनपुट पर उंडेलो। उलटाव से सबसे छोटा ऊपर रह जाता है।
यह स्टैक की पोशाक में इन्सर्शन सॉर्ट है। समय ओ(एन²), अतिरिक्त जगह सहायक स्टैक के लिए ओ(एन)। खाली, एक तत्व, डुप्लिकेट सब उन्हीं लूप से निकलते हैं।
तीस सेकंड में यह कह सको, पार्क-और-घुसाओ चाल खींच सको, और ऐरे से "धोखा" न दो, तो समस्या ३.५ तुम्हारी है।
सीरीज़
- गाइड: सीटीसीआई सीरीज़ गाइड
- पिछला: कतार दो स्टैक से
- अगला: एनिमल शेल्टर