टीएल;डीआर
- समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
- दृष्टिकोण: सिंगली लिंक्ड लिस्ट के अंत से के-वाँ नोड निकालें। क्लासिक दो-पॉइंटर गैप के, फिर छोटा रिकर्सिव इंडेक्स रैपर, सादे जावा में।
- जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।
आप और एक दोस्त एक पगडंडी पर एक के पीछे एक चल रहे हैं। दोस्त के कदम आगे शुरू करता है। जब दोस्त पगडंडी के अंत पर पहुँचता है, आप अंत से के-वें पत्थर पर खड़े होते हैं। कुल लंबाई की ज़रूरत नहीं पड़ी। सिर्फ गैप चाहिए था।
यही रिटर्न केथ टू लास्ट है: सिंगली लिंक्ड लिस्ट के अंत से के जगहों पर बैठा नोड खोजो। हम के = १ को अंतिम तत्व मानते हैं।
यह सीटीसीआई-स्टाइल समस्या २.२ है, अध्याय २ (लिंक्ड लिस्ट)। मुख्य हल: इटरेटिव दो पॉइंटर। वैकल्पिक: छोटा इंडेक्स रैपर वाला रिकर्सिव। जावा में मूल शिक्षण, किताब की कॉपी नहीं।
सीरीज़: सीटीसीआई जावा। पिछला: २.१ रिमूव डप्स। अगला: २.३ डिलीट मिडिल नोड।
रोज़मर्रा की तस्वीर
डिब्बों की एक ट्रेन, सिर से पूँछ तक। आप सिर्फ आगे चलते हैं। रिवर्स गियर नहीं, डिब्बों पर गिनती भी नहीं लिखी।
कोई पूछता है: "पूँछ वाले डिब्बे से दूसरा डिब्बा दो।" अगर लंबाई एन पता होती, सिर से एन − २ कदम चलते। अभी एन पता नहीं। एक बार गिनकर एन निकालो, फिर फिर चलो: काम करता है। दो पूरे पास भी लगते हैं।
बेहतर: एक स्काउट के डिब्बे आगे भेजो। फिर स्काउट और आप साथ-साथ एक-एक डिब्बा चलो। जब स्काउट अंत से गिरे, आपका डिब्बा अंत से के-वाँ है।
समस्या सादे शब्दों में
इनपुट: सिंगली लिंक्ड लिस्ट का हेड, और धनात्मक पूर्णांक k।
आउटपुट: वह नोड जो अंत से के-वाँ है। हमारी कन्वेंशन में k = 1 अंतिम नोड देता है, k = 2 अंत से दूसरा, और आगे ऐसे ही।
उदाहरण (लिस्ट सिर → पूँछ):
| लिस्ट | के | नतीजा | क्यों |
|---|---|---|---|
1 → 2 → 3 → 4 → 5 |
१ | नोड 5 |
अंतिम तत्व |
1 → 2 → 3 → 4 → 5 |
२ | नोड 4 |
अंत से दूसरा |
1 → 2 → 3 → 4 → 5 |
५ | नोड 1 |
के = लंबाई |
1 → 2 → 3 |
४ | नल (या एरर) | के लंबाई से बड़ा |
7 |
१ | नोड 7 |
एक नोड, अंतिम वही |
कोड से पहले ज़ोर से साफ़ करो:
- क्या
k = 1अंतिम नोड है? (यहाँ हाँ। कुछ टीमें शून्य-आधारित रखती हैं। पूछो।) - अगर
kलंबाई से बड़ा हो तो? नल, थ्रो, या सेंटिनल? एक चुनो। हमnullलौटाते हैं। - नोड लौटाना है या सिर्फ वैल्यू? इंटरव्यू में अक्सर नोड चाहिए ताकि आगे चेन चल सके।
- नल हेड? खाली लिस्ट → नल।
कोड से पहले कैसे सोचें
ब्रूट फोर्स: लंबाई, फिर चलना
१. लिस्ट एक बार घूमो, n गिनो।
२. अगर k > n, फेल।
३. सिर से फिर n - k कदम चलो।
सही है। दो पास। अगर इंटरव्यूअर ओ(एन) समय और दो यात्रा से खुश हो तो ठीक। कई फिर पूछते हैं: एक पास में हो सकता है?
एक पास: के गैप वाले दो पॉइंटर
१. पॉइंटर p1 और p2 दोनों head से शुरू।
२. p1 को ठीक k कदम आगे बढ़ाओ। जल्दी गिर गए तो k बहुत बड़ा है।
३. p1 और p2 को साथ बढ़ाओ जब तक p1 नल न हो।
४. अब p2 अंत से के-वें नोड पर है।
क्यों चलता है: जब p1 बाकी सफिक्स पूरा चल चुका, p2 "अंत" से ठीक के नोड पीछे रहा। अंत अंतिम नोड के एक आगे है, इसलिए p2 अंत से के-वें पर है।
ट्रेस 1 → 2 → 3 → 4 → 5, k = 2:
| कदम | p1 |
p2 |
|---|---|---|
| शुरू | १ | १ |
p1 एक बार |
२ | १ |
p1 दो बार |
३ | १ |
| दोनों चले | ४ | २ |
| दोनों चले | ५ | ३ |
| दोनों चले | नल | ४ |
p2 है 4। हो गया।
रिकर्सिव आइडिया (वैकल्पिक)
अंत तक रिकर्स करो। लौटते समय गिनो कितने नोड पार किए। जब गिनती k पर पहुँचे, वही नोड जवाब है। साझा काउंटर (या छोटा रैपर ऑब्जेक्ट) चाहिए, क्योंकि जावा में सादा int रिटर्न एक साथ "गिनती" और "जवाब नोड" साफ़ नहीं ले जा सकता बिना हेल्पर टाइप के।
रिकर्शन इंटरव्यू में सुंदर लगता है अगर स्टैक समझा सको। मुख्य जवाब इटरेटिव दो-पॉइंटर रखो: अतिरिक्त स्पेस ओ(१), लंबी लिस्ट पर स्टैक जोखिम नहीं।
जावा समाधान
नोड टाइप
/** Singly linked list node. Original teaching model for this series. */
public class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
}
}
मुख्य जवाब: इटरेटिव दो-पॉइंटर
/**
* Returns the kth node from the end of the list.
* k = 1 means the last node. Returns null if the list is too short
* or inputs are invalid.
*/
public static Node kthToLast(Node head, int k) {
if (head == null || k < 1) {
return null;
}
Node p1 = head;
Node p2 = head;
// Open a gap of k between p1 and p2.
for (int i = 0; i < k; i++) {
if (p1 == null) {
// k is larger than the number of nodes.
return null;
}
p1 = p1.next;
}
// When p1 walks off the end, p2 is k nodes from the end.
while (p1 != null) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
छोटी लिस्ट बनाकर कॉल करो:
// 1 → 2 → 3 → 4 → 5
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
Node ans = kthToLast(head, 2); // data == 4
वैकल्पिक: इंडेक्स रैपर वाला रिकर्सिव
/** Mutable counter so recursion can share one index on the way back. */
static class Index {
int value = 0;
}
/**
* Recursive kth-to-last. Same k convention: k = 1 is the last node.
* Uses O(n) stack space. Prefer kthToLast for production-sized lists.
*/
public static Node kthToLastRecursive(Node head, int k) {
if (k < 1) {
return null;
}
return kthToLastRecursive(head, k, new Index());
}
private static Node kthToLastRecursive(Node head, int k, Index idx) {
if (head == null) {
return null;
}
Node candidate = kthToLastRecursive(head.next, k, idx);
idx.value += 1;
if (idx.value == k) {
return head;
}
return candidate;
}
अनवाइंड पर अंतिम नोड को गिनती १ मिलती है, उससे पहले वाले को २, और आगे। जब गिनती k के बराबर हो, वही नोड लौटाओ। सिर के करीब के नोड पहले मिला उम्मीदवार लौटाते रहते हैं (या नल अगर k बहुत बड़ा था)।
जटिलता
| तरीका | समय | अतिरिक्त स्पेस | नोट |
|---|---|---|---|
| लंबाई फिर चलना | ओ(एन) | ओ(१) | दो पास |
| दो-पॉइंटर गैप | ओ(एन) | ओ(१) | एक पास, मुख्य जवाब |
| रिकर्सिव इंडेक्स | ओ(एन) | ओ(एन) स्टैक | बताना अच्छा, डिफ़ॉल्ट शिप नहीं |
सबसे बुरे मामले में हर नोड देखना पड़ता है (या दोनों पॉइंटर रखने जितना), इसलिए लीनियर समय सही क्रम है।
किनारे के केस जो इंटरव्यूअर छेड़ते हैं
१. नल हेड। खाली लिस्ट। नल लौटाओ।
२. के १ से छोटा। अमान्य। नल (या थ्रो)। कॉन्ट्रैक्ट बोलो।
३. के लंबाई से बड़ा। के एडवांस पूरे होने से पहले p1 नल। नल लौटाओ।
४. के = लंबाई। के एडवांस के बाद p1 नल। साथ वाला लूप नहीं चलता। p2 हेड पर रहता है। सही: हेड ही अंत से के-वाँ है।
५. के = १। अंतिम नोड। एक का गैप: p1 एक कदम आगे, दोनों चलें जब तक p1 नल, p2 आखिरी असली नोड पर।
६. एक नोड, के = १। चलता है। एक नोड, के = २: फेल।
७. लिस्ट म्यूटेट मत करो। समस्या रीड-ओनली है। next मत छेड़ो।
८. गैप पर ऑफ-बाय-वन। क्लासिक बग: गलती से k - 1 या k + 1 एडवांस। बोलने से पहले कागज़ पर के = १ और के = एन ट्रेस करो।
आम गलतियाँ
- सामने से "के-वाँ नोड" गिनना, अंत से के-वाँ नहीं।
- शून्य-आधारित मॉडल (
k = 0अंतिम) बिना बताए। कमरा उलझ जाता है। - रनर को
k - 1बार बढ़ाना जबकि परिभाषा के = १ अंतिम है। "के बार बढ़ाओ, फिर रनर नल होने तक साथ चलो" पर टिके रहो। - गैप खोलते समय नल चेक भूलना, फिर बड़ा
kपर एनपीई। - इंटरव्यूअर ने नोड माँगा हो और
p2.dataलौटा देना।
दोस्त को सुनाने वाला सार
अंत से के-वाँ डिब्बा चाहिए, और आप सिर्फ आगे चलते हो।
स्काउट को के डिब्बे आगे भेजो। साथ-साथ चलो। जब स्काउट ट्रेन से गिरे, आप अंत से के-वें डिब्बे पर हो। लंबाई वाले वेरिएबल की ज़रूरत नहीं।
रिकर्सिव संस्करण: अंत तक जाओ, लौटते गिनो, गिनती के पर नोड पकड़ो। वही आइडिया, दूसरे पॉइंटर की जगह स्टैक।
दो-पॉइंटर संस्करण शिप करो। दूसरा कोण माँगें तो रिकर्शन बताओ।
अभ्यास
१. याद से kthToLast लिखो। 1 → 2 → 3 → 4 → 5 पर के = १, के = २, के = एन ट्रेस करो।
२. लंबाई-फिर-चलना वाला संस्करण भी लिखो और साबित करो दोनों एक ही नोड देते हैं।
३. रिकर्सिव रैपर लिखो और समझाओ जावा में साझा Index (या int[]) क्यों चाहिए।
४. के = ०, खाली लिस्ट, और लंबाई से बड़ा के से अपना कोड तोड़ो।
पिछला: २.१ रिमूव डप्स। अगला: २.३ डिलीट मिडिल नोड। पूरी सीरीज़: सीटीसीआई जावा।