टीएल;डीआर
- समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
- दृष्टिकोण: दो सिंगली लिंक्ड लिस्ट दी हों तो संदर्भ से पहला साझा नोड लौटाओ (मान से नहीं)। एक ही टेल मतलब मिलन; लंबाई मिलाओ, फिर साथ चलो।
- जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।
दो गाँव की सड़कें। हर एक अलग जगह से शुरू होती है। पहाड़ियों के बाद वे एक ही राजमार्ग में मिल जाती हैं और फिर नहीं टूटतीं। किसी भी सड़क से आने वाली गाड़ी मिलन बिंदु के बाद वही मील साझा करती है। लिंक्ड लिस्ट भी ऐसा कर सकती हैं: नोड्स की दो श्रृंखलाएँ, शुरू में अलग, फिर उन्हीं नोड ऑब्जेक्ट का एक साझा सफिक्स।
यह पोस्ट सीटीसीआई जावा सीरीज़ की समस्या २.७ इंटरसेक्शन है। मूल शिक्षण, किताब की नकल नहीं। पहला साझा नोड लौटाओ, या null अगर सड़कें कभी न मिलें।
रोज़मर्रा की उपमा
दो धागों पर चिपचिपे नोट सोचो। हर नोट मेमोरी में एक नोड ऑब्जेक्ट है। उसमें एक मान है और अगले नोट का पॉइंटर।
यहाँ इंटरसेक्शन यह नहीं कि "दोनों लिस्ट में एक ही संख्या दिखे"। दो नोट दोनों 7 कह सकते हैं और फिर भी अलग कागज़ हों। इंटरसेक्शन मतलब दोनों धागे कभी बिल्कुल उसी नोट तक पहुँचते हैं (हीप में वही ऑब्जेक्ट)। उस नोट से आगे दोनों लिस्ट बाकी श्रृंखला साझा करती हैं, क्योंकि next पॉइंटर भी वही ऑब्जेक्ट होते हैं।
संक्षेप: दो सड़कें, एक मिलन। पहला साझा मील का पत्थर ढूँढो।
समस्या सादे शब्दों में
इनपुट: दो सिंगली लिंक्ड लिस्ट के हेड, list1 और list2 (कोई भी null हो सकता है)।
आउटपुट: संदर्भ से पहला साझा नोड, या null अगर कोई साझा नोड न हो।
महत्वपूर्ण नियम
- नोड की तुलना
==से करो (वही ऑब्जेक्ट),data == dataसे नहीं। - अगर मिलन है तो पूरा सफिक्स साझा होता है: पॉइंटर जुड़ने के बाद अलग टेल में नहीं बँटते।
- मिलन से पहले लिस्ट की लंबाई अलग हो सकती है।
- लिस्ट को तब तक न बदलो जब तक वापस न सुधारो (यह समाधान नहीं बदलता)।
उदाहरण (संदर्भ से)
list1: a1 → a2 → c1 → c2 → c3
list2: b1 → b2 → b3 → c1 → c2 → c3
दोनों घूमने में c1 वही ऑब्जेक्ट है। उत्तर: नोड c1। पहले समान मान मायने नहीं रखते।
नोड का आकार
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
कोड से पहले कैसे सोचें
नोड का हैश सेट (सरल, मेमोरी लेता है)
१. list1 घूमो। हर नोड संदर्भ HashSet<Node> में डालो (पहचान, मान नहीं)।
२. list2 घूमो। हर नोड के लिए, अगर सेट में वही ऑब्जेक्ट पहले से है तो उसे लौटा दो।
३. list2 खत्म हो जाए और कुछ न मिले तो null लौटाओ।
समय ओ(ए + बी), अतिरिक्त जगह ओ(ए) जहाँ ए और बी लंबाइयाँ हैं। समझाना आसान। इंटरव्यू में अक्सर अगला सवाल स्थिर अतिरिक्त जगह माँगता है।
पसंदीदा: एक ही टेल + लंबाई मिलाना (ओ(१) जगह)
मुख्य बातें:
१. अगर दो सिंगली लिंक्ड लिस्ट मिलती हैं तो वे एक ही अंतिम नोड पर खत्म होती हैं। अलग टेल मतलब अलग अंत: कोई साझा सफिक्स नहीं।
२. अगर वे लंबाई एस का सफिक्स साझा करें, और पूरी लंबाइयाँ एल१ व एल२ हों, तो निजी प्रीफिक्स एल१ - एस और एल२ - एस हैं। लंबी लिस्ट का अतिरिक्त निजी प्रीफिक्स |एल१ - एल२| है।
एल्गोरिदम:
१. हर लिस्ट एक बार घूमो। लंबाई गिनो और टेल नोड याद रखो।
२. दोनों टेल एक ही ऑब्जेक्ट न हों तो null लौटाओ।
३. diff = |len1 - len2| लो। लंबी लिस्ट के पॉइंटर को diff कदम आगे बढ़ाओ ताकि दोनों के आगे बराबर नोड बचें।
४. दोनों को एक-एक कदम चलाओ। पहली बार जब p1 == p2, वही इंटरसेक्शन है।
५. अगर साथ-साथ null आ जाए तो टेल जाँच गलत थी; सही टेल जाँच से साझा शुरूआत पर मिलोगे या पहले ही साबित कर चुके होगे कि मिलन नहीं।
क्यों काम करता है: मिलाने के बाद दोनों घूमने की बाकी लंबाई बराबर है। हर कदम या तो निजी नोड पर रहता है (अलग ऑब्जेक्ट) या साझा सफिक्स पर एक ही शेष दूरी से गिरता है। पहली बराबर संदर्भ वही मिलन नोड हैं।
जावा समाधान
/**
* Finds the first node that appears in both lists by reference (same object).
* Returns null if the lists do not intersect.
*/
Node findIntersection(Node list1, Node list2) {
if (list1 == null || list2 == null) {
return null;
}
TailAndSize a = getTailAndSize(list1);
TailAndSize b = getTailAndSize(list2);
// Different last nodes => no shared suffix.
if (a.tail != b.tail) {
return null;
}
Node shorter = a.size <= b.size ? list1 : list2;
Node longer = a.size <= b.size ? list2 : list1;
int diff = Math.abs(a.size - b.size);
// Skip the extra private prefix on the longer list.
longer = getKthNode(longer, diff);
while (shorter != longer) {
shorter = shorter.next;
longer = longer.next;
}
return longer; // same as shorter; the merge node (or null if both empty, not our case)
}
static class TailAndSize {
Node tail;
int size;
TailAndSize(Node tail, int size) {
this.tail = tail;
this.size = size;
}
}
TailAndSize getTailAndSize(Node head) {
if (head == null) {
return new TailAndSize(null, 0);
}
int size = 1;
Node current = head;
while (current.next != null) {
size++;
current = current.next;
}
return new TailAndSize(current, size);
}
/** Returns the node k steps from head (0 = head). Assumes the list is long enough. */
Node getKthNode(Node head, int k) {
Node current = head;
for (int i = 0; i < k; i++) {
current = current.next;
}
return current;
}
ऊपर के चित्र का चरण-दर-चरण:
| चरण | विवरण |
|---|---|
list1 लंबाई |
५, टेल = c3 |
list2 लंबाई |
६, टेल = c3 |
| टेल बराबर? | हाँ (वही ऑब्जेक्ट) |
diff |
१; list2 को एक कदम b2 तक |
| जोड़ी में चलना | (a1,b2), (a2,b3), (c1,c1) रुक |
| परिणाम | नोड c1 |
तुलना के लिए हैश सेट वाला रूप:
import java.util.HashSet;
import java.util.Set;
Node findIntersectionWithSet(Node list1, Node list2) {
Set<Node> seen = new HashSet<>();
for (Node n = list1; n != null; n = n.next) {
seen.add(n);
}
for (Node n = list2; n != null; n = n.next) {
if (seen.contains(n)) {
return n;
}
}
return null;
}
HashSet नोड के लिए ऑब्जेक्ट पहचान इस्तेमाल करता है जब तक तुम equals/hashCode न बदलो। इस समस्या में उन्हें data पर आधारित मत बनाओ, वरना संदर्भ की जगह मान मिलेंगे।
जटिलता
| तरीका | समय | अतिरिक्त जगह | नोट |
|---|---|---|---|
| लंबाई मिलाना + साथ चलना | ओ(ए + बी) | ओ(१) | दो लंबाई पास, फिर एक साथ चलना |
| नोड का हैशसेट | ओ(ए + बी) | ओ(ए) | सरल; पहले ड्राफ्ट की तरह बताओ |
| नेस्टेड स्कैन (ए का हर नोड बनाम पूरा बी) | ओ(ए · बी) | ओ(१) | सही पर धीमा; मुख्य उत्तर न बनाओ |
सबसे खराब स्थिति में टेल और लंबाई जानने के लिए हर नोड कम से कम एक बार देखना पड़ता है, इसलिए कुल नोड पर रैखिक सही क्रम है।
किनारे के मामले जो इंटरव्यूअर छूते हैं
१. कोई मिलन नहीं। अलग टेल। लंबाई/टेल पास के बाद तुरंत null। हमेशा के लिए मत चलते रहो।
२. एक या दोनों null। साझा करने को नोड नहीं। null लौटाओ।
३. एक ही लिस्ट दो बार। findIntersection(head, head) को head लौटाना चाहिए (सब साझा; पहला साझा हेड है)। लंबाई बराबर; साथ चलना पहले कदम पर मिल जाता है।
४. सिर्फ अंतिम नोड पर मिलन। साझा सफिक्स लंबाई १। मिलान फिर भी काम करता है; उस अंतिम नोड पर मिलते हो।
५. छोटी लिस्ट के हेड पर मिलन। लंबी को diff से आगे बढ़ाओ, फिर पहली तुलना पहले से बराबर हो सकती है।
६. समान मान, अलग ऑब्जेक्ट। 3 → 4 → 5 और अलग से बनी दूसरी 3 → 4 → 5: टेल अलग ऑब्जेक्ट। उत्तर null। ज़ोर से बोलो "संदर्भ से"।
७. बहुत अलग लंबाई। बड़ा diff ठीक है; सावधानी से बढ़ाओ और अंत से मत गिरो (टेल समानता पहले ही साझा सफिक्स गारंटी करती है)।
८. साइकिल। क्लासिक २.७ बिना लूप मानता है। अगर लूप संभव हों तो पहले लूप जाँच (लूप डिटेक्शन)। धारणा साफ़ कहो।
आम गलतियाँ
- नोड पहचान की जगह मान जाँचना (
n1.data == n2.dataया खराबequals)। - टेल जाँच भूलकर सिर्फ लंबाई मिलाना। अलग-अलग समान लंबाई की लिस्ट नहीं मिलतीं; टेल जाँच जल्दी फेल होकर ज्यामिति साफ़ करती है।
- अंतर से छोटी लिस्ट बढ़ाना, लंबी की जगह।
- सेट में नोड संदर्भ की जगह पूर्णांक मान डालना।
- एक लिस्ट को दूसरी से जोड़कर हैक करना और इनपुट को चुपचाप बदलना; इंटरव्यूअर इसे नापसंद करते हैं।
- बिना लंबाई मिलाए साथ चलकर पहला समान मान मिलन मान लेना। प्रीफिक्स बग।
दोस्त को बताने लायक सार
दो एकतरफ़ा श्रृंखलाएँ। क्या वे कभी उसी नोड ऑब्जेक्ट पर पहुँचती हैं और बाकी सड़क साझा करती हैं?
अगर अंतिम नोड अलग हैं तो कभी नहीं मिलतीं। अगर अंतिम नोड वही ऑब्जेक्ट है तो सफिक्स साझा है। दोनों लंबाई मापो, लंबी श्रृंखला की अतिरिक्त शुरुआत छोड़ो, फिर कंधे से कंधा मिलाकर चलो जब तक पॉइंटर एक ही संदर्भ न हों। वही नोड इंटरसेक्शन है।
अगर अतिरिक्त मेमोरी ठीक है तो नोड का हैश सेट भी चलता है। इंटरव्यू में ओ(१) जगह वाली लंबाई-मिलान कहानी आगे रखो।
अभ्यास
१. याद से findIntersection लिखो: टेल + आकार, मिलाओ, चलो।
२. सिर्फ अंतिम नोड साझा करने वाली दो लिस्ट बनाकर पॉइंटर ट्रेस करो।
३. समान मान, बिना साझा ऑब्जेक्ट वाली दो लिस्ट बनाओ; पुष्टि करो कि null आता है।
४. समझाओ कि मानों का HashSet<Integer> गलत औज़ार क्यों है।
पिछला: पैलिंड्रोम। अगला: लूप डिटेक्शन। पूरी सीरीज़ का नक्शा: सीटीसीआई जावा।