टीएल;डीआर
- समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
- दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ३.३: एक प्लेट-स्टैक बहुत ऊँचा हो जाए तो नया शुरू करो। सेटऑफ़स्टैक्स बनाओ ताकि पुश और पॉप एक ही स्टैक जैसे लगें, फिर पॉपएट(इंडेक्स) पर छोटी टिप्पणी।
- जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।
रात के खाने के बाद प्लेटें पोंछ रहे हो। काउंटर पर एक ढेर ठीक है जब तक वह डगमगाने न लगे। एक ऊँचाई पर तुम बगल में दूसरा ढेर शुरू करते हो, फिर तीसरा। बाहर से तुम अब भी सबसे नए ढेर के ऊपर से प्लेट लेते हो और साफ़ प्लेट उसी नए ढेर पर रखते हो। अंदर कई छोटे ढेर हैं, एक गगनचुंबी नहीं। यही सेटऑफ़स्टैक्स है।
यह पोस्ट जावा में बिल्कुल शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू वाली स्टैक-क्षमता सवालों का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ३, स्टैक और कतार।
१. रोज़मर्रा की उपमा
खाने की प्लेटें और एक नियम सोचो: कोई भी ढेर क्षमता से ऊँचा नहीं।
- हर भौतिक ढेर एक भीतरी स्टैक है जिसकी अधिकतम ऊँचाई तय है (मान लो ५ प्लेटें)।
- मौजूदा ढेर भर जाए तो दाईं ओर नया ढेर खोलो।
- पुश हमेशा उस सबसे दाएँ ढेर पर प्लेट रखता है जिसमें जगह बची हो (या अगर सबसे दायाँ भरा है तो नया ढेर बनाता है)।
- पॉप हमेशा सबसे दाएँ गैर-खाली ढेर से प्लेट लेता है।
- पॉप के बाद कोई ढेर खाली हो जाए तो उसे हटा दो, ताकि "सबसे दायाँ" ईमानदार रहे।
कॉलर ढेर के नंबर नहीं संभालते। वे push और pop ऐसे बुलाते हैं जैसे एक तार्किक स्टैक हो। बहु-स्टैक का हिसाब तुम छिपाते हो।
फ़ॉलो-अप ज़्यादा सख्त है: पॉपएट(इंडेक्स) किसी खास ढेर (उप-स्टैक इंडेक्स) के ऊपर से प्लेट हटाता है, सिर्फ़ सबसे नए से नहीं। बीच में खाली जगह छूट सकती है। तुम तय करते हो कि प्लेटें बाईं ओर रोल करके भरोगे या बिखरे उप-स्टैक छोड़ोगे। इंटरव्यूअर चाहते हैं कि तुम यह समझौता नाम से बताओ।
२. समस्या सादे शब्दों में
बनाओ एक संरचना SetOfStacks जिसमें हर भीतरी स्टैक की निश्चित capacity हो।
ऑपरेशन:
push(value): तार्किक स्टैक पर पुश (सबसे नया उप-स्टैक, या ज़रूरत पर नया)।pop(): तार्किक स्टैक से पॉप (सबसे नए गैर-खाली उप-स्टैक का टॉप)। लाइफ़ो क्रम में एक ही स्टैक जैसा व्यवहार।- वैकल्पिक फ़ॉलो-अप:
popAt(index): सिर्फ़ उप-स्टैकindexपर पॉप।
अटल नियम:
- कोई भी भीतरी स्टैक
capacityसे ज़्यादा तत्व न रखे। popके बाद खाली पिछलग्गू स्टैक न रहें।- पूरी तरह खाली संरचना पर
popसाफ़ तरीके से फेल हो (अपवाद या तय संकेत)।
उदाहरण (क्षमता = ३):
| क्रिया | भीतरी स्टैक (बायाँ = पुराना) | नोट |
|---|---|---|
| पुश १,२,३ | [1,2,3] |
पहला स्टैक भरा |
| पुश ४ | [1,2,3] [4] |
नया स्टैक बना |
| पुश ५,६ | [1,2,3] [4,5,6] |
दूसरा भरा |
| पॉप | [1,2,3] [4,5] |
६ लौटता है |
| पॉप, पॉप | [1,2,3] |
खाली होने पर दूसरा हटा |
| और पुश के बाद पॉपएट(०) | निर्भर | सिर्फ़ स्टैक ० के टॉप से पॉप |
कोड से पहले साफ़ करो:
- कंस्ट्रक्टर पर क्षमता तय? (इस पोस्ट में हाँ।)
- क्षमता ० या ऋणात्मक? (कंस्ट्रक्टर में ठुकराओ।)
- खाली पर पॉप: अपवाद, या नल? (हम
EmptyStackExceptionफेंकते हैं।) - पॉपएट: रोलओवर (शिफ्ट) या बीच में छेद छोड़ना? (दोनों की बात करो; साधारण बिना-भरने वाला लागू करो और रोलओवर का ज़िक्र करो।)
३. पहले सोचो
एक अकेला ऐरेडीक्यू काफ़ी नहीं
एक Stack या ArrayDeque पहले से पुश/पॉप देता है। इस समस्या का बिंदु है हर भौतिक स्टैक पर क्षमता की सीमा, जैसे गिरने वाली प्लेटें, या याददाश्त की कहानी में तय आकार के पेज।
स्टैकों की सूची
एक ArrayList रखो जिसमें ArrayDeque<Integer> हों, नाम stacks।
push(v): १. अगर
stacksखाली है, या आखिरी स्टैक का आकारcapacityके बराबर है, तो नया खाली स्टैक जोड़ो। २. आखिरी स्टैक परvपुश करो।pop(): १. कोई स्टैक न हो तो खाली-अपवाद फेंको। २. आखिरी स्टैक से पॉप। ३. अगर वह अब खाली है तो सूची से हटाओ। ४. मान लौटाओ।
हेल्पर
lastStack(): सबसे दायाँ स्टैक, या कोई न हो तो नल।
यही पूरा बेस डिज़ाइन है। कोई पेड़ नहीं। सिर्फ़ तय-क्षमता वाले लाइफ़ो बाल्टियों की बढ़ती सूची।
पॉपएट का मानसिक मॉडल
popAt(index) को सीमा जाँच चाहिए: इंडेक्स सही दायरे में, वह स्टैक गैर-खाली।
बीच के स्टैक से पॉप के बाद विकल्प:
१. छेद छोड़ो। स्टैक i क्षमता से छोटा रह सकता है जबकि i+1 में तत्व हों। कोड सरल। push अब भी सिर्फ़ आखिरी स्टैक छूता है (जब तक पुश पर भी संतुलन न करो, जो ज़्यादातर हल नहीं करते)।
२. रोलओवर / शिफ्ट। स्टैक i से पॉप के बाद i+1 का नीचे वाला तत्व लेकर i के ऊपर धकेलो, और श्रृंखला में आगे। आखिरी को छोड़ लगभग सब स्टैक भरे रहते हैं। ज़्यादा कोड, घना लेआउट, कई स्टैक हों तो पॉपएट प्रति O(N) तक।
दोनों ज़ोर से बोलो। जब तक वे रोलओवर न माँगें, साधारण वाला लागू करो।
४. जावा समाधान (सेटऑफ़स्टैक्स)
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.EmptyStackException;
import java.util.List;
/**
* Several fixed-capacity stacks that behave as one logical stack for push/pop.
* Capacity is per inner stack. New stacks open when the current one is full.
*/
class SetOfStacks {
private final int capacity;
private final List<Deque<Integer>> stacks = new ArrayList<>();
SetOfStacks(int capacity) {
if (capacity < 1) {
throw new IllegalArgumentException("capacity must be at least 1");
}
this.capacity = capacity;
}
void push(int value) {
Deque<Integer> last = lastStack();
if (last == null || last.size() == capacity) {
last = new ArrayDeque<>();
stacks.add(last);
}
last.push(value);
}
int pop() {
Deque<Integer> last = lastStack();
if (last == null) {
throw new EmptyStackException();
}
int value = last.pop();
if (last.isEmpty()) {
stacks.remove(stacks.size() - 1);
}
return value;
}
/**
* Pop only from sub-stack at index (0 = oldest).
* Leaves later stacks as-is (no rollover). See section 5.
*/
int popAt(int index) {
if (index < 0 || index >= stacks.size()) {
throw new IndexOutOfBoundsException("sub-stack index: " + index);
}
Deque<Integer> stack = stacks.get(index);
if (stack.isEmpty()) {
throw new EmptyStackException();
}
int value = stack.pop();
if (stack.isEmpty()) {
stacks.remove(index);
}
return value;
}
boolean isEmpty() {
return stacks.isEmpty();
}
int numberOfStacks() {
return stacks.size();
}
private Deque<Integer> lastStack() {
if (stacks.isEmpty()) {
return null;
}
return stacks.get(stacks.size() - 1);
}
}
क्षमता ३ के साथ चलकर देखो:
१. push(1..3) → एक भरा स्टैक [1,2,3] (टॉप ३)।
२. push(4) → दूसरा आता है: [1,2,3] [4]।
३. pop() → ४; दूसरा खाली होकर हटता है → [1,2,3]।
४. pop() → ३ → [1,2]।
५. और पुश के बाद तीन स्टैक हों तो popAt(0) सिर्फ़ सबसे पुराने के टॉप को हटाता है। बाद वाले जस के तस (शिफ्ट नहीं)।
ArrayDeque क्यों, java.util.Stack क्यों नहीं? Stack पुरानी सिंक्रनाइज़्ड Vector उप-क्लास है। जावा इंटरव्यू में आधुनिक लाइफ़ो के लिए ArrayDeque आम है। हमारे काम के लिए व्यवहार एक जैसा।
५. पॉपएट पर नोट (फ़ॉलो-अप)
popAt(index) वही मोड़ है जो दिखाता है कि तुमने सिर्फ़ "स्टैकों की सूची" रटी है या संरचना सोची है।
साधारण संस्करण (ऊपर): stacks.get(index) से पॉप, खाली हो तो उप-स्टैक हटाओ। बीच के स्टैक क्षमता से कम रह सकते हैं जबकि नए भरे हों। अगर समस्या सिर्फ़ उस उप-स्टैक से वैध पॉप माँगे तो ठीक।
रोलओवर संस्करण (रेखाचित्र, कोड ज़रूरी नहीं):
- स्टैक
indexसे पॉप। - अगला स्टैक हो तो उसका नीचे वाला तत्व लो (नीचे दिखाने वाली संरचना चाहिए, या फिर से बनाओ) और मौजूदा पर पुश करो ताकि क्षमता लौटे।
- आखिरी स्टैक तक श्रृंखला दोहराओ।
रोलओवर प्लेट की उपमा कसी रखता है: पुराने ढेर से प्लेट निकालो तो नए ढेर से प्लेटें "बाईं ओर गिरें" ताकि बीच का कोई ढेर आधा खाली न रहे। लागत स्टैक गिनती और खिसके तत्वों के साथ बढ़ती है। ज़िक्र करो; लागू तभी जब माँगा जाए।
इंडेक्स का मतलब भी साफ़ करो: ० सबसे पुराना है या सबसे नया? एक चुनो और अड़े रहो। ऊपर के कोड में ० सबसे पुराना है।
६. जटिलता तालिका
| ऑपरेशन | समय | अतिरिक्त स्थान (तत्वों के अलावा) | नोट |
|---|---|---|---|
push |
ओ(१) औसत | ओ(१) | कभी-कभी नया स्टैक आवंटन |
pop |
ओ(१) | ओ(१) | खाली पिछलग्गू स्टैक हटा सकता है |
popAt (बिना रोलओवर) |
ओ(१) या ओ(एस) | ओ(१) | बीच का खाली स्टैक हटाते समय सूची शिफ्ट हो तो ओ(एस) |
popAt (रोलओवर सहित) |
ओ(एन) सबसे बुरा | ओ(१) | हर बाद वाले स्टैक को छू सकता है |
isEmpty |
ओ(१) | ओ(१) | खाली तभी जब कोई उप-स्टैक न बचे |
एन सभी स्टैक में कुल तत्व हैं। एस उप-स्टैकों की संख्या है। संरचना का स्थान मान रखने के लिए ओ(एन) है, एक बड़े स्टैक जैसा, प्लस कुछ स्टैक हेडर।
७. किनारे के मामले और आम गलतियाँ
इंटरव्यूअर ये छेड़ते हैं:
- क्षमता = १ → हर पुश नया स्टैक खोलता है (या आकार-१ भराकर अगला पुश नया खोलता है)। पॉप अब भी सबसे नया छीलता है। खास केस न बनाओ तो चलता है।
- अवैध क्षमता → कंस्ट्रक्टर में फेंको, पुश तक इंतज़ार मत करो।
- खाली पर पॉप → फेंको। जब तक समस्या सेंटीनेल न दे, ० या -१ मत लौटाओ।
- खाली होने तक पॉप, फिर फिर पुश → स्टैक सूची शून्य से साफ़ बढ़ती है।
- सीमा से बाहर पॉपएट → बाउंड्स अपवाद।
- बीच का स्टैक खाली करने वाला पॉपएट → वह प्रविष्टि हटाओ (बाद के इंडेक्स खिसकें) या कब्र छोड़ो। हटाना साफ़ है; लिखो कि बाद के इंडेक्स बदलते हैं।
- एक ही स्टैक, अधूरा → पुश उसी पर रहता है। जल्दी दूसरा मत बनाओ।
आम गलतियाँ:
१. पॉप के बाद खाली पिछलग्गू स्टैक न हटाना। तब lastStack() खाली ढेर दिखाता है और अगला पॉप फेल होता है या अतिरिक्त नल जाँच चाहिए।
२. भरे आखिरी स्टैक पर पुश। पुश से पहले हमेशा size() == capacity जाँचो।
३. पॉपएट को पॉप जैसा मानना। एपीआई अलग हैं। पॉपएट बुलाने वाला खास उप-स्टैक चुनता है।
४. क्षमता को सभी स्टैक की कुल क्षमता समझना। क्षमता प्रति उप-स्टैक है।
५. एक ऐरेलिस्ट और मॉड्यूलर अंकगणित से अनजाने रोलओवर। दूसरे डिज़ाइन में चल सकता है, पर तब "उप-स्टैक" काल्पनिक हो जाते हैं। व्हाइटबोर्ड पर प्लेट उपमा दिखे, इसके लिए डीक्यू की स्पष्ट सूची रखो।
८. दोस्त को समझाने वाला सार
स्टैक ऑफ़ प्लेट्स पूछता है: क्षमता सीमा के नीचे कई छोटे स्टैक रखो, पर पुश और पॉप एक स्टैक जैसे लगें।
१. भीतरी स्टैकों की क्रमबद्ध सूची रखो। सामान्य पुश सिर्फ़ आखिरी पर जाते हैं। २. आखिरी भरा हो तो नया खाली जोड़ो, फिर पुश। ३. आखिरी से पॉप। खाली हो जाए तो सूची से मिटाओ। ४. तार्किक स्टैक का लाइफ़ो क्रम सुरक्षित रहता है: सबसे नई प्लेट पहले निकलती है, ढेर की सीमा पार करके भी। ५. पॉपएट(इंडेक्स) सिर्फ़ उसी ढेर से पॉप करता है। या छेद छोड़ो या प्लेटें बाईं रोल करो। जो चुना वह बोलो।
अगर तीन स्टैक ऊँचाई ३ खींच सको, दसवीं प्लेट पुश करो, दो बार पॉप करो, और समझा सको कि दायाँ खाली ढेर क्यों गायब होता है, तो समस्या ३.३ तुम्हारी है।
श्रृंखला
- गाइड: सीटीसीआई श्रृंखला गाइड
- पिछला: स्टैक मिन
- अगला: कतार विया स्टैक्स