टीएल;डीआर
- समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
- दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ३.१: एक ऐरे से तीन स्टैक बनाओ। बराबर स्थिर हिस्सों, sizes[] ऐरे, और साफ FixedMultiStack जावा में।
- जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।
तुम्हारे पास एक लंबी शेल्फ है और तीन रूममेट। हर किसी को अपनी किताबों के स्टैक के लिए शेल्फ का एक स्थिर हिस्सा मिलता है। ए की किताबें बी के हिस्से में नहीं जातीं। जब किसी का हिस्सा भर जाता है, तो दूसरे के खाली स्पेस से उसे मदद नहीं मिलती। यही एक ऐरे में तीन स्टैक है, स्थिर विभाजन के साथ।
यह पोस्ट जावा में बिल्कुल शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू वाली मल्टी-स्टैक समस्याओं का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ३ (स्टैक और क्यू) यहीं से शुरू होता है।
१. रोज़मर्रा की उपमा
ऐसी पार्किंग पट्टी सोचो जिस पर तीन बराबर ज़ोन पेंट हों:
- ज़ोन ० स्टैक ० की गाड़ियाँ रखता है।
- ज़ोन १ स्टैक १ की गाड़ियाँ रखता है।
- ज़ोन २ स्टैक २ की गाड़ियाँ रखता है।
हर ज़ोन बाएँ किनारे से दाएँ भरता है। प्रति ज़ोन एक आकार काउंटर बताता है कितनी गाड़ियाँ पहले से हैं। अगर आकार रखो तो अलग टॉप पॉइंटर की जरूरत नहीं: स्टैक k का टॉप उस ज़ोन के आखिरी भरे स्लॉट पर होता है।
अगर ज़ोन ० भरा है, स्टैक ० की अगली गाड़ी ठुकरा दो। ज़ोन २ के खाली स्पेस काम नहीं आते। यही स्थिर विभाजन का समझौता है: आसान गणित, असमान लोड पर जगह बर्बाद।
एक कठिन संस्करण भी है जहाँ ज़ोन की दीवारें सरक सकती हैं (लचीला विभाजन)। संक्षेप में ज़िक्र करेंगे। शुरुआती इंटरव्यू के लिए डिफ़ॉल्ट स्थिर बराबर हिस्से ही हैं।
२. समस्या सादे शब्दों में
इनपुट / लक्ष्य: ऐसी डेटा संरचना डिज़ाइन करो जो एक अंतर्निहित ऐरे से तीन स्टैक लागू करे।
ऑपरेशन (हर एक में स्टैक नंबर 0, 1, या 2):
push(stackNum, value): उस स्टैक पर पुशpop(stackNum): टॉप हटाकर लौटाओpeek(stackNum): बिना हटाए टॉप लौटाओisEmpty(stackNum)/isFull(stackNum): क्षमता जाँच
इस पोस्ट का मुख्य तरीका: स्थिर विभाजन। ऐरे को stackCapacity क्षमता वाले तीन बराबर सटे ब्लॉकों में बाँटो। हर ब्लॉक कितना भरा है, sizes[3] से ट्रैक करो।
कोड से पहले साफ करो:
- स्टैक इंडेक्स
0,1,2(शून्य-आधारित)। - कुल ऐरे लंबाई
3 * stackCapacity। - भरा होने पर पुश? थ्रो (या एरर)। खाली पर पॉप भी वैसा ही।
- स्टैक स्वतंत्र? हाँ। स्टैक ० पर पुश स्टैक १ को खराब न करे।
चित्र: stackCapacity = 4 (ऐरे लंबाई १२):
| इंडेक्स | स्टैक | मतलब |
|---|---|---|
0..3 |
० | पहला हिस्सा |
4..7 |
१ | दूसरा हिस्सा |
8..11 |
२ | तीसरा हिस्सा |
अगर स्टैक १ का आकार २ है, मान इंडेक्स 4 और 5 पर हैं, टॉप इंडेक्स 5 पर।
३. पहले सोचो (स्थिर बनाम लचीला)
स्थिर विभाजन (पहले यही सिखाओ)
१. values = new int[stackCapacity * 3] आवंटित करो।
२. sizes = new int[3] रखो, शुरुआत में सब शून्य।
३. स्टैक stackNum का ऑफ़सेट है stackNum * stackCapacity।
४. सफल पुश के बाद (या पीक/पॉप के लिए) टॉप का इंडेक्स है offset + sizes[stackNum] - 1।
५. पुश: भरा हो तो फेल। नहीं तो आकार बढ़ाओ, नए टॉप इंडेक्स पर लिखो।
६. पॉप: खाली हो तो फेल। नहीं तो टॉप पढ़ो, स्लॉट साफ करो (वैकल्पिक), आकार घटाओ।
७. पीक: खाली हो तो फेल। नहीं तो values[indexOfTop] लौटाओ।
तीन टॉप पॉइंटर की जगह आकार क्यों? दोनों बराबर हैं। आकार जीवित तत्वों की संख्या है; टॉप इंडेक्स ऑफ़सेट और आकार का फलन है। तीन इंट का छोटा ऐरे इंटरव्यू में समझना आसान है।
लचीला / गतिशील विभाजन (वैकल्पिक कठिन विचार)
अगर एक स्टैक बहुत बढ़े और दूसरा खाली रहे, स्थिर हिस्से सेल बर्बाद करते हैं। लचीले डिज़ाइन में स्टैक खाली जगह में फैल सकते हैं: प्रति स्टैक स्टार्ट/एंड बाउंड रखो, पड़ोसी को जगह चाहिए तो तत्व शिफ्ट करो। सही है, पर कोड ज़्यादा (सीमाएँ, शिफ्टिंग, तीनों स्टैक मिलाकर भरा-पता)। अगर इंटरव्यूअर पूछे "जगह बेहतर यूज़ कर सकते हैं?" तो ज़िक्र करो। तब तक स्थिर ही दो, जब तक वे कठिन संस्करण न माँगें।
इस लेख में स्थिर ही भेजो।
याद रखने वाला इंडेक्स गणित
offset(stackNum) = stackNum * stackCapacity
indexOfTop(stackNum) = offset + sizes[stackNum] - 1
isEmpty = sizes[stackNum] == 0
isFull = sizes[stackNum] == stackCapacity
व्हाइटबोर्ड पर बारह बक्सों की एक पंक्ति खींचो और स्टैक १ पर पुश/पॉप चलाओ। इंडेक्स सही दिखें तो क्लास लगभग खुद लिख जाती है।
४. जावा समाधान
/**
* Three stacks packed into one array with fixed equal slices.
* stackNum is 0, 1, or 2.
*/
class FixedMultiStack {
private final int numberOfStacks = 3;
private final int stackCapacity;
private final int[] values;
private final int[] sizes;
FixedMultiStack(int stackCapacity) {
if (stackCapacity <= 0) {
throw new IllegalArgumentException("stackCapacity must be positive");
}
this.stackCapacity = stackCapacity;
this.values = new int[stackCapacity * numberOfStacks];
this.sizes = new int[numberOfStacks]; // all 0
}
void push(int stackNum, int value) {
assertValidStack(stackNum);
if (isFull(stackNum)) {
throw new IllegalStateException("stack " + stackNum + " is full");
}
sizes[stackNum]++;
values[indexOfTop(stackNum)] = value;
}
int pop(int stackNum) {
assertValidStack(stackNum);
if (isEmpty(stackNum)) {
throw new IllegalStateException("stack " + stackNum + " is empty");
}
int top = indexOfTop(stackNum);
int value = values[top];
values[top] = 0; // optional clear; helps debugging
sizes[stackNum]--;
return value;
}
int peek(int stackNum) {
assertValidStack(stackNum);
if (isEmpty(stackNum)) {
throw new IllegalStateException("stack " + stackNum + " is empty");
}
return values[indexOfTop(stackNum)];
}
boolean isEmpty(int stackNum) {
assertValidStack(stackNum);
return sizes[stackNum] == 0;
}
boolean isFull(int stackNum) {
assertValidStack(stackNum);
return sizes[stackNum] == stackCapacity;
}
/** Absolute index of the current top element for this stack. */
private int indexOfTop(int stackNum) {
int offset = stackNum * stackCapacity;
return offset + sizes[stackNum] - 1;
}
private void assertValidStack(int stackNum) {
if (stackNum < 0 || stackNum >= numberOfStacks) {
throw new IllegalArgumentException("stackNum must be 0, 1, or 2");
}
}
}
वॉकथ्रू: stackCapacity = 3 (ऐरे लंबाई ९):
| चरण | कॉल | sizes |
टॉप पर लिखना / पढ़ना |
|---|---|---|---|
| शुरू | (खाली) | [0,0,0] |
- |
| १ | push(0, 10) |
[1,0,0] |
लिखो values[0] = 10 |
| २ | push(0, 20) |
[2,0,0] |
लिखो values[1] = 20 |
| ३ | push(1, 99) |
[2,1,0] |
लिखो values[3] = 99 |
| ४ | peek(0) |
वही | इंडेक्स 1 पर 20 पढ़ो |
| ५ | pop(0) |
[1,1,0] |
20 लौटाओ, इंडेक्स 1 साफ |
| ६ | push(0, 30) |
[2,1,0] |
लिखो values[1] = 30 |
स्टैक ० कभी इंडेक्स 3..8 नहीं छूता। स्टैक १ कभी 0..2 या 6..8 नहीं छूता।
५. जटिलता तालिका
| ऑपरेशन | समय | साझा ऐरे के अलावा अतिरिक्त जगह | नोट |
|---|---|---|---|
push / pop / peek |
ओ(१) | ओ(१) | सिर्फ अंकगणित + ऐरे एक्सेस |
isEmpty / isFull |
ओ(१) | ओ(१) | sizes की एक एंट्री |
| निर्माण | ओ(एन) | ऐरे के अलावा ओ(१) | N = 3 * stackCapacity आवंटन |
| स्थिर मल्टी-स्टैक कुल | - | वैल्यूज़ पर ओ(एन) + साइज़ पर ओ(१) (३ इंट) | असमान लोड पर सेल बर्बाद |
| लचीला मल्टी-स्टैक (विचार) | शिफ्ट पर पुश ओ(एन) हो सकता है | ज़्यादा बहीखाता | जगह बेहतर, कोड कठिन |
इंटरव्यूअर ज्यादातर अचर समय वाले ऑपरेशन और सही इंडेक्स गणित चाहते हैं। लचीला शिफ्ट फॉलो-अप है, पहला हल नहीं।
६. किनारे के केस और आम गलतियाँ
इंटरव्यूअर ये छेड़ते हैं:
stackCapacity = 1: हर स्टैक एक मान रखता है। उसी स्टैक पर दूसरा पुश फेल होना चाहिए।- खाली पर पॉप / पीक: थ्रो (या अगर तय हो तो सेंटिनल)। आकार ० पर
indexOfTopमत पढ़ो; वह इंडेक्सoffset - 1बन जाता है, गलत, और दूसरे स्टैक में घुस सकता है। - भरे पर पुश: थ्रो। चुपचाप ओवरराइट मत करो।
- अमान्य
stackNum:{0,1,2}के बाहर ठुकराओ। - स्वतंत्रता: स्टैक २ भरने से स्टैक ० खाली और इस्तेमाल योग्य रहना चाहिए।
- शून्य या ऋणात्मक क्षमता: कंस्ट्रक्टर में ठुकराओ।
- पॉप फिर पुश: आकार घटता-बढ़ता है; वही इंडेक्स फिर से। सही स्टैक व्यवहार।
आम गलतियाँ:
१. offset + size को बिना १ घटाए टॉप मानना। आकार १ होने पर टॉप offset + 0 पर है, offset + 1 पर नहीं।
२. पुराने आकार से लिखने के बाद आकार बढ़ाना। क्रम मायने रखता है: या पहले बढ़ाओ फिर indexOfTop पर लिखो, या offset + size पर लिखो फिर बढ़ाओ। एक चुनो और अडिग रहो। ऊपर का कोड पहले बढ़ाता है।
३. तीनों स्टैक के लिए एक ही टॉप पॉइंटर। वह एक स्टैक है, तीन नहीं।
४. पुश से पहले isFull भूलना। अगला हिस्सा कुचल दोगे।
५. स्टैक ० को अपने हिस्से से आगे स्टैक १ में बढ़ने देना। स्थिर विभाजन मना करता है; प्रति स्टैक क्षमता लागू करो।
न्यूनतम स्मोक टेस्ट स्केच:
void demo() {
FixedMultiStack stacks = new FixedMultiStack(2);
stacks.push(0, 1);
stacks.push(0, 2);
// stacks.push(0, 3); // would throw: full
stacks.push(2, 9);
assert stacks.pop(0) == 2;
assert stacks.peek(0) == 1;
assert stacks.pop(2) == 9;
assert stacks.isEmpty(1);
}
७. दोस्त को समझाने वाला सार
थ्री इन वन पूछता है: क्या तीन स्वतंत्र स्टैक एक ऐरे में पैक कर सकते हो?
१. ऐरे को stackCapacity लंबाई के तीन बराबर हिस्सों में बाँटो।
२. sizes[3] रखो। स्टैक k का टॉप k * stackCapacity + sizes[k] - 1 पर रहता है।
३. भरा न हो तभी पुश: आकार बढ़ाओ, टॉप पर लिखो। खाली न हो तभी पॉप: टॉप पढ़ो, साफ करो, आकार घटाओ।
४. सारे ऑपरेशन ओ(१)। कीमत: एक स्टैक गरम और दूसरा बेकार हो तो जगह बर्बाद।
५. खाली सेल छीनने वाली लचीली दीवारें कठिन फॉलो-अप हैं। जब तक न कहा जाए, स्थिर हिस्से से शुरू करो।
तीन हिस्से खींच सको, टॉप इंडेक्स का सूत्र बोल सको, और स्टैक एक-दूसरे पर चढ़े बिना भरे पुश ठुकरा सको, तो समस्या ३.१ तुम्हारी है।
सीरीज़
- गाइड: सीटीसीआई सीरीज़ गाइड
- पिछला: लूप डिटेक्शन
- अगला: स्टैक मिन