समस्या और लागू संदर्भ
आपको ऐरे A और B प्राप्त होते हैं। प्रत्येक आइटम एक क्लोज्ड इंटरवल [start, end] है; दोनों ऐरे गैर-घटते start द्वारा सॉर्ट किए गए हैं, और एक ऐरे के अंदर इंटरवल ओवरलैप नहीं होते हैं। दोनों सूचियों द्वारा कवर किए गए प्रत्येक इंटरवल को लौटाएं, जो स्टार्ट के आधार पर भी क्रमित हों।
A = [[1,5],[10,14]] और B = [[2,3],[4,12]] के लिए, प्रतिच्छेदन [[2,3],[4,5],[10,12]] हैं। समान एंडपॉइंट्स गिने जाते हैं, इसलिए [1,2] और [2,4], [2,2] पर प्रतिच्छेद करते हैं।
साक्षात्कारकर्ता क्या परीक्षण कर रहा है
साक्षात्कारकर्ता यह देखना चाहता है कि क्या आप प्रत्येक युग्म की तुलना करने के बजाय दो सॉर्टेड अनुक्रमों को एक मोनोटोनिक टू-पॉइंटर स्कैन में बदल सकते हैं। एक मजबूत उत्तर क्लोज्ड-इंटरवल सिमेंटिक्स को परिभाषित करता है, max(start) और min(end) की गणना करता है, और यह साबित करता है कि केवल पहले समाप्त होने वाले इंटरवल को ही क्यों छोड़ा जा सकता है।
कोडिंग से पहले स्पष्टीकरण
- क्या इंटरवल क्लोज्ड हैं या हाफ-ओपन? इससे यह बदलता है कि समान एंडपॉइंट्स आउटपुट उत्पन्न करते हैं या नहीं।
- क्या दोनों सूचियां सॉर्टेड और आंतरिक रूप से गैर-अतिव्यापी हैं? यदि नहीं, तो उन्हें पहले सॉर्ट करें या प्रत्येक सूची को मर्ज करें।
- क्या इनपुट खाली हो सकता है, पॉइंट इंटरवल शामिल हो सकते हैं, या
start > endशामिल हो सकता है? यह वैलिडेशन निर्धारित करता है। - क्या शून्य-लंबाई वाले प्रतिच्छेदनों को रखा जाना चाहिए? यह समस्या उन्हें रखती है क्योंकि इंटरवल क्लोज्ड हैं।
30-सेकंड उत्तर ढांचा
"मैं पॉइंटर्स i और j रखता हूँ। वर्तमान प्रतिच्छेदन बड़े स्टार्ट से शुरू होता है और छोटे एंड पर समाप्त होता है; जब बायां एंडपॉइंट दाएं एंडपॉइंट से बड़ा नहीं होता है, तो मैं इसे उत्सर्जित (emit) करता हूँ। फिर मैं छोटे एंड वाले इंटरवल को आगे बढ़ाता हूँ, क्योंकि बाद के स्टार्ट उस इंटरवल को ओवरलैप नहीं कर सकते जो पहले ही समाप्त हो चुका है। यदि एंड्स टाई होते हैं, तो मैं दोनों को आगे बढ़ाता हूँ। प्रत्येक पॉइंटर अपनी सूची में एक बार चलता है, इसलिए स्कैन आउटपुट के अलावा O(1) वर्किंग स्पेस के साथ O(m+n) है।"
चरण-दर-चरण गहन विश्लेषण
चरण 1: इंटरवल सिमेंटिक्स तय करें
प्रत्येक इंटरवल को [start,end] के रूप में मानें। मान लें left = max(A[i].start, B[j].start) और right = min(A[i].end, B[j].end)। एक प्रतिच्छेदन तब मौजूद होता है जब बायां एंडपॉइंट दाएं एंडपॉइंट से बड़ा नहीं होता है; समान एंडपॉइंट्स एक मान्य बिंदु बनाते हैं।
चरण 2: पॉइंटर मूवमेंट प्राप्त करें
यदि A[i].end, B[j].end से कम है, तो A[i] पहले समाप्त होता है। B में प्रत्येक बाद का इंटरवल B[j] से पहले शुरू नहीं होता है, इसलिए A[i], B[j+1] या उसके बाद के किसी भी इंटरवल को प्रतिच्छेद नहीं कर सकता है। i को आगे बढ़ाएं। वह स्थिति जहां B[j] पहले समाप्त होता है, सममित (symmetric) है।
चरण 3: समान एंड्स को संभालें
जब एंड्स समान होते हैं, तो वर्तमान इंटरवल में से किसी के पास भी ऐसा शेष समय नहीं होता है जो बाद के इंटरवल को ओवरलैप कर सके। दोनों पॉइंटर्स को आगे बढ़ाएं। केवल एक तरफ को आगे बढ़ाने से समाप्त हो चुके इंटरवल की दोबारा जांच होती है और अनावश्यक तुलनाएं हो सकती हैं या प्रमाण अस्पष्ट हो सकता है।
चरण 4: एक निष्पादन योग्य कंकाल (Skeleton) लिखें
function intersect(A: number[][], B: number[][]): number[][] {
const out: number[][] = [];
let i = 0;
let j = 0;
while (i < A.length && j < B.length) {
const left = Math.max(A[i][0], B[j][0]);
const right = Math.min(A[i][1], B[j][1]);
if (left <= right) out.push([left, right]);
if (A[i][1] < B[j][1]) i++;
else if (B[j][1] < A[i][1]) j++;
else { i++; j++; }
}
return out;
}चरण 5: शुद्धता के लिए अपरिवर्तनीय (Invariant) बताएं
प्रत्येक लूप की शुरुआत में, i और j उस सबसे शुरुआती युग्म की पहचान करते हैं जिसके प्रतिच्छेद न कर पाने का प्रमाण अभी तक नहीं मिला है। [left,right] उस युग्म का एकमात्र संभावित प्रतिच्छेदन है, इसलिए इसे उत्सर्जित करना युग्म के लिए पूर्ण है। पहले समाप्त होने वाले इंटरवल को हटाने के बाद, छोड़े गए प्रत्येक युग्म का स्टार्ट पहले ही समाप्त हो चुके इंटरवल से बाद का होता है, इसलिए कोई भी प्रतिच्छेदन नहीं छूटता है।
चरण 6: जटिलता और इनपुट सुरक्षा का विश्लेषण करें
पॉइंटर्स केवल आगे बढ़ते हैं, अधिकतम m+n बार, इसलिए समय O(m+n) है। वर्किंग स्पेस आउटपुट को छोड़कर O(1) है, या k उत्सर्जित इंटरवल्स सहित O(k) है। यदि सॉर्टिंग और मान्य एंडपॉइंट्स की गारंटी नहीं है, तो पहले मान्य या सामान्यीकृत (normalize) करें; रैखिक प्रमाण मनमाने इनपुट पर लागू नहीं होता है।
उच्च-गुणवत्ता वाला नमूना उत्तर
मैं पहले क्लोज्ड इंटरवल्स, सॉर्टेड स्टार्ट्स और किसी भी सूची के भीतर कोई ओवरलैप न होने की पुष्टि करूँगा। A[i] और B[j] के लिए, प्रतिच्छेदन बड़े स्टार्ट और छोटे एंड का उपयोग करता है; क्लोज्ड एंडपॉइंट्स के साथ, एक एंडपॉइंट जो दूसरे एंडपॉइंट से बड़ा नहीं है, तब भी एक बिंदु उत्सर्जित करता है। फिर मैं उस पॉइंटर को आगे बढ़ाता हूँ जिसका इंटरवल पहले समाप्त होता है, क्योंकि बाद के स्टार्ट उस इंटरवल को ओवरलैप नहीं कर सकते जो पहले ही समाप्त हो चुका है; समान एंड्स दोनों को आगे बढ़ाते हैं। प्रत्येक इंटरवल को एक बार संसाधित किया जाता है, जिससे O(m+n) समय मिलता है। मैं खाली इनपुट, कोई ओवरलैप नहीं, समान एंडपॉइंट्स, पॉइंट इंटरवल्स, समावेशन (containment), और कई लगातार प्रतिच्छेदनों का परीक्षण करूँगा।
सामान्य गलतियाँ
- गलती → केवल तब उत्सर्जित करना जब बायां एंडपॉइंट सख्ती से छोटा हो → यह क्यों विफल होता है: एक क्लोज्ड इंटरवल का पॉइंट प्रतिच्छेदन गायब हो जाता है → सुधार: अनुबंध की पुष्टि करें और समान एंडपॉइंट्स रखें।
- गलती → प्रत्येक
Aइंटरवल के लिए प्रत्येकBइंटरवल को स्कैन करना → यह क्यों विफल होता है: सॉर्टिंग को अनदेखा कर दिया जाता है और समयO(mn)हो जाता है → सुधार: मोनोटोनिक पॉइंटर्स बनाए रखें। - गलती → हमेशा
iको बढ़ाना → यह क्यों विफल होता है:B[j]पहले समाप्त हो सकता है, जिससे बार-बार तुलना हो सकती है या आउटपुट छूट सकता है → सुधार: एंड्स की तुलना करें और छोटे वाले को आगे बढ़ाएं, टाई होने पर दोनों को। - गलती → बिना सॉर्ट किए गए इनपुट के रैखिक समय का दावा करना → यह क्यों विफल होता है: पॉइंटर प्रमाण अब मान्य नहीं रहता → सुधार: पहले प्रत्येक सूची को सॉर्ट या मर्ज करें।
अनुवर्ती प्रश्न और उत्तर
हाफ-ओपन इंटरवल्स [start,end) के लिए क्या बदलता है?
आवश्यकता है कि बायां एंडपॉइंट सख्ती से छोटा हो; [1,2) और [2,4) का कोई पॉइंट प्रतिच्छेदन नहीं होता है। पॉइंटर मूवमेंट के लिए एंड तुलना समान रह सकती है, लेकिन एंडपॉइंट अनुबंध को स्पष्ट रूप से बताएं।
यदि प्रत्येक सूची अनसॉर्टेड और ओवरलैपिंग है तो क्या आप O(m+n) रख सकते हैं?
सीधे तौर पर नहीं। पहले प्रत्येक सूची को सॉर्ट और मर्ज करें, जिसकी लागत कम से कम O(m log m+n log n) होगी, फिर लीनियर टू-पॉइंटर स्कैन चलाएं।
क्या होगा यदि आउटपुट कुल प्रतिच्छेदन लंबाई होना चाहिए?
स्कैन को बनाए रखें और एंडपॉइंट परंपरा के लिए समायोजित प्रत्येक right-left को संचित (accumulate) करें। पूर्णांक क्लोज्ड इंटरवल्स के लिए, फॉर्मूला लिखने से पहले स्पष्ट करें कि लंबाई का अर्थ ज्यामितीय विस्तार (geometric span) है या शामिल बिंदुओं की संख्या।
क्या होगा यदि दोनों सूचियां ऐसे स्ट्रीम्स हैं जिन्हें रिवाइंड नहीं किया जा सकता है?
जब तक प्रत्येक स्ट्रीम स्टार्ट-सॉर्टेड रहती है, तब तक वर्तमान इंटरवल और अगली-पढ़ी जाने वाली स्थिति को पॉइंटर स्थिति के रूप में बनाए रखें। प्रतिच्छेदन उत्सर्जित करने के बाद, समाप्त हो चुके इंटरवल को हटा दें; आउट-ऑफ-ऑर्डर डेटा के लिए बफरिंग और एक अलग डिज़ाइन की आवश्यकता होती है।