कोडिंग इंटरव्यू: मर्ज और क्वेरी के साथ इंटरवल सेट को आप कैसे लागू करेंगे?

प्रॉम्प्ट और दायरा

add([l,r)), remove([l,r)), contains(x), और overlaps([l,r)) के साथ एक इंटरवल सेट लागू करें। आसन्न या ओवरलैपिंग इंटरवल्स स्वचालित रूप से मर्ज होने चाहिए, जबकि रिमूवल एक इंटरवल को विभाजित कर सकता है। ओपन और क्लोज्ड बाउंड्रीज़, खाली रेंज और जटिलता की व्याख्या करें।

यह ऑर्डर्ड कलेक्शन्स, इनवेरिएंट्स और बाउंड्री हैंडलिंग का परीक्षण करता है। Python का bisect दस्तावेज़ीकरण बताता है कि बाईसेक्शन एक इंसर्शन पॉइंट ढूंढता है जबकि लिस्ट इंसर्शन अभी भी O(n) हो सकता है। डेटा-साइज़ का अनुमान बताएं और यह भी स्पष्ट करें कि हर ऑपरेशन को O(log n) बताने के बजाय क्या ट्री (tree) की आवश्यकता है।

इंटरव्यूअर क्या जांच रहा है

पहला, क्या आप हाफ-ओपन सेमांटिक्स को तय कर सकते हैं और आसन्नता (adjacency) को संभाल सकते हैं? दूसरा, क्या इंसर्शन और रिमूवल प्रत्येक इंटरवल के बजाय केवल संभावित रूप से प्रतिच्छेद करने वाले पड़ोसियों को स्कैन कर सकते हैं? तीसरा, क्या आप स्केल के आधार पर ऐरे, बैलेंस्ड ट्री या इंटरवल ट्री चुन सकते हैं और इनवेरिएंट को सिद्ध कर सकते हैं?

उत्तर देने से पहले स्पष्ट करने योग्य प्रश्न

क्या इंटरवल्स क्लोज्ड, ओपन या हाफ-ओपन हैं? [l,r) मान लें, ताकि [0,1) और [1,2) प्रतिच्छेद न करें।
क्या एंडपॉइंट्स फ्लोटिंग पॉइंट हैं? तुलनीय पूर्णांक (comparable integers) मान लें; यदि नहीं, तो सटीकता और NaN नियम परिभाषित करें।
क्या आसन्न इंटरवल्स को मर्ज होना चाहिए? नॉर्मलाइज़्ड प्रतिनिधित्व बनाए रखने के लिए हाँ मान लें।
स्केल और रीड/राइट मिक्स क्या हैं? छोटे सेट्स सॉर्ट किए गए ऐरे का उपयोग कर सकते हैं; बड़े सेट्स को बैलेंस्ड या इंटरवल ट्री की आवश्यकता हो सकती है।
अनुपस्थित रेंज को हटाने पर क्या होता है? इसे आइडेम्पोटेंट मानें और केवल वही हिस्सा रखें जो मौजूद है।

30-सेकंड का उत्तर ढांचा

"मैं हाफ-ओपन इंटरवल्स का उपयोग करूंगा और उन्हें सॉर्टेड, डिसजॉइंट और गैर-आसन्न रखूंगा। add संभावित प्रतिच्छेदन खोजने के लिए बाइनरी सर्च का उपयोग करता है, फिर ओवरलैपिंग या आसन्न प्रविष्टियों को मर्ज करने के लिए दाईं ओर स्कैन करता है। remove प्रतिच्छेदनों को स्कैन करता है और गैर-खाली बाएं और दाएं अवशेषों को संरक्षित करता है। contains पूर्ववर्ती (predecessor) इंटरवल की जांच करता है; overlaps पहले ऐसे इंटरवल की जांच करता है जिसका अंत क्वेरी के प्रारंभ से अधिक हो। एक ऐरे में O(log n) सर्च लेकिन O(n) शिफ्ट्स होते हैं; बड़े सेट्स के लिए मैं एक बैलेंस्ड या इंटरवल ट्री का उपयोग करूंगा।"

चरण-दर-चरण गहन विश्लेषण

चरण 1: नॉर्मलाइज़्ड इनवेरिएंट को परिभाषित करें

सॉर्टेड, डिसजॉइंट, गैर-आसन्न हाफ-ओपन इंटरवल्स [l,r) को l < r के साथ स्टोर करें; खाली इंटरवल्स कभी दर्ज नहीं होते हैं। नॉर्मलाइज़ेशन के बाद, एक बिंदु अधिकतम एक इंटरवल से संबंधित होता है, इसलिए अपडेट स्थानीय पड़ोसियों पर ध्यान केंद्रित कर सकते हैं।

चरण 2: स्टोरेज चुनें

कुछ हज़ार इंटरवल्स और कम राइट्स के लिए, एक सॉर्टेड ऐरे सरल और विश्वसनीय है; बाइनरी सर्च एक स्थिति का पता लगाता है जबकि इंसर्शन और डिलीशन एलिमेंट्स को शिफ्ट करते हैं। उच्च राइट और क्वेरी वॉल्यूम के लिए, एक ऑर्डर्ड-की बैलेंस्ड ट्री का उपयोग करें। केवल तभी एक ऑगमेंटेड इंटरवल ट्री जोड़ें जब कवरेज काउंट्स या अधिकतम ओवरलैप गहराई की आवश्यकता हो।

चरण 3: इंसर्शन पड़ोसियों का पता लगाएं

l से कम नहीं होने वाले पहले स्टार्ट को खोजने के लिए bisect_left का उपयोग करें, फिर एक पूर्ववर्ती का निरीक्षण करें क्योंकि यह l तक विस्तारित हो सकता है। दाईं ओर तब तक स्कैन करें जब तक कि अगला स्टार्ट वर्तमान मर्ज किए गए अंत से अधिक न हो; आसन्न इंटरवल्स को मर्ज में शामिल किया जाता है।

text

add(l, r):
    i = first index with start >= l, then i = max(0, i - 1)
    while i < len(intervals) and intervals[i].end >= l:
        l = min(l, intervals[i].start)
        r = max(r, intervals[i].end)
        delete intervals[i]
    insert [l, r) at i

चरण 4: रिमूवल और विभाजन लागू करें

पहला इंटरवल खोजें जो [l,r) को प्रतिच्छेद कर सकता है और तब तक प्रोसेस करें जब तक कि अगला स्टार्ट कम से कम r न हो। प्रत्येक इंटरवल के लिए, [start,l) और [r,end) के गैर-खाली हिस्सों को बनाए रखें। चूंकि इनपुट नॉर्मलाइज़्ड है, रिमूवल से ऐसे आसन्न रेंज नहीं बनते जिन्हें दूसरे मर्ज की आवश्यकता हो।

चरण 5: पॉइंट और रेंज क्वेरीज़ लागू करें

contains(x) के लिए, start <= x वाला अंतिम इंटरवल खोजें और x < end की जांच करें। overlaps([l,r)) के लिए, end > l वाला पहला इंटरवल खोजें; यदि start < r है तो यह ओवरलैप होता है। एक खाली क्वेरी रेंज false लौटाती है। प्रत्येक तुलना हाफ-ओपन सेमांटिक्स का पालन करती है।

चरण 6: शुद्धता सिद्ध करें

इंसर्शन लूप केवल उन रेंजों को हटाता है जो नई रेंज को ओवरलैप करते हैं या स्पर्श करते हैं और उनके संघ (union) को एक इंटरवल से बदल देते हैं, इसलिए कवरेज सुरक्षित रहता है। रिमूवल केवल प्रतिच्छेदन को हटाता है और दो अंतरों को बनाए रखता है। प्रत्येक ऑपरेशन के बाद सॉर्टिंग और गैर-आसन्नता बहाल हो जाती है, और प्रत्येक क्वेरी को केवल एक उम्मीदवार पूर्ववर्ती या उत्तराधिकारी की आवश्यकता होती है।

चरण 7: जटिलता का विश्लेषण करें

ऐरे का पता लगाना O(log n) है, लेकिन मर्ज की गई प्रविष्टियों को शिफ्ट करना और हटाना O(n) हो सकता है, जहाँ n इंटरवल की संख्या है। k पड़ोसी इंटरवल्स को स्कैन करने से O(k) जुड़ता है। एक बैलेंस्ड ट्री अधिक कार्यान्वयन और मेमोरी लागत के साथ O(log n + k) स्थानीय अपडेट प्रदान कर सकता है। बाइनरी-सर्च लागत को पूर्ण-ऑपरेशन लागत के साथ भ्रमित न करें।

चरण 8: बाउंड्री टेस्ट डिज़ाइन करें

एक खाली सेट, खाली रेंज, आसन्न मर्ज, पूर्ण समावेश, आंशिक ओवरलैप, कई इंटरवल्स में फैलाव, मध्य डिलीशन, एंडपॉइंट डिलीशन, नेगेटिव्स, बार-बार संचालन और एक बड़ी क्वेरी रेंज का परीक्षण करें। बिंदुवार (pointwise) बूलियन-ऐरे मॉडल के विरुद्ध रैंडम ऑपरेशन्स का डिफरेंशियल-टेस्ट करें।

ट्रेड-ऑफ और सीमाएं

ट्रेड-ऑफ 1: हाफ-ओपन या क्लोज्ड इंटरवल्स

हाफ-ओपन रेंज स्वाभाविक रूप से संयोजित होती हैं, उनकी लंबाई r-l होती है, और वे समय तथा ऐरे-इंडेक्स उपयोग के मामलों में उपयुक्त बैठती हैं। एक क्लोज्ड-इंटरवल व्यवसाय को आसन्नता, लंबाई और पूर्णांक-ओवरफ्लो नियमों को लगातार बदलना होगा; केवल तुलना ऑपरेटरों को बदलना सुरक्षित नहीं है।

ट्रेड-ऑफ 2: ऐरे या बैलेंस्ड ट्री

ऐरे संक्षिप्त होते हैं और रीड-हैवी, छोटे-से-मध्यम सेट्स के लिए कैश-फ्रेंडली होते हैं। ट्रीज़ कई इंसर्शन्स और डिलीशन्स को संभालते हैं लेकिन उन्हें ऑर्डर्ड कीज़ और इटरेटर-अमान्यीकरण नियमों की आवश्यकता होती है। वास्तविक n, राइट अनुपात और लेटेंसी बजट के आधार पर चयन करें।

ट्रेड-ऑफ 3: आसन्न रेंजों को मर्ज करना या स्रोत (provenance) को बनाए रखना

मर्ज करने से प्रविष्टियां कम होती हैं और क्वेरीज़ सरल होती हैं। यदि इंटरवल्स अनुमतियों, आरक्षणों या लेखांकन अवधियों का प्रतिनिधित्व करते हैं जिनकी मूल सीमाएं मायने रखती हैं, तो स्रोत मेटाडेटा बनाए रखें या ऐसे प्रतिनिधित्व का उपयोग करें जो खंडों को छोड़ता नहीं है।

विफलता अभ्यास और विकास योजना

अभ्यास 1: कई आसन्न इंसर्शन

उल्टे क्रम में 10,000 आसन्न इंटरवल्स इन्सर्ट करें। सत्यापित करें कि बिना किसी लापता एंडपॉइंट के एक नॉर्मलाइज़्ड इंटरवल बचता है, फिर यह तय करने के लिए ऐरे शिफ्ट्स को मापें कि क्या ट्री की आवश्यकता है।

अभ्यास 2: रैंडम इंसर्शन और रिमूवल

रैंडम add, remove, contains, और overlaps ऑपरेशन्स उत्पन्न करें और एक बिंदुवार मॉडल से तुलना करें। विशेष रूप से जांचें कि एक इंटरवल के मध्य को हटाने और बाद में इन्सर्ट करने पर दोनों पक्ष सही ढंग से मर्ज होते हैं।

अभ्यास 3: बाउंड्री और अमान्य इनपुट

l == r, l > r, बहुत बड़े पूर्णांकों और NaN का परीक्षण करें। परिभाषित करें कि क्या खाली रेंज लौटती हैं, उल्टी रेंज त्रुटि देती हैं या स्वैप होती हैं, और क्या फ्लोटिंग इनपुट को अस्वीकार कर दिया जाता है।

सामान्य गलतियाँ और फॉलो-अप

गलती 1: आसन्न और ओवरलैपिंग को भ्रमित करना

हाफ-ओपन [0,1) और [1,2) प्रतिच्छेद नहीं करते हैं, हालांकि एक नॉर्मलाइज़्ड सेट फिर भी उन्हें मर्ज कर सकता है। प्रतिच्छेदन और मर्ज की शर्तों को अलग-अलग परिभाषित करें।

गलती 2: केवल दाएं पड़ोसी की जांच करना

पूर्ववर्ती नए बाएं एंडपॉइंट को पार कर सकता है। बाइनरी सर्च के बाद एक पूर्ववर्ती का निरीक्षण करें।

गलती 3: रिमूवल के बाद खाली इंटरवल्स छोड़ना

प्रत्येक अंतर को start >= end के साथ फ़िल्टर करें, अन्यथा contains एक फैंटम हिट की रिपोर्ट कर सकता है।

गलती 4: दावा करना कि bisect इंसर्शन को O(log n) बनाता है

Python स्पष्ट रूप से नोट करता है कि लिस्ट इंसर्शन शिफ्ट्स O(n) हैं। सर्च, शिफ्ट और स्कैन लागतों को अलग से बताएं।

गलती 5: फ्लोटिंग-पॉइंट सीमाओं को नज़रअंदाज़ करना

NaN सामान्य क्रम का पालन नहीं करता है, और अनुमानित समानता आसन्नता को अस्थिर बनाती है। फ़्लोट्स की अनुमति देने से पहले सटीकता सामान्यीकरण को परिभाषित करें।

गलती 6: स्रोत जानकारी (provenance) खोना

यदि इंटरवल्स अनुमतियों, आरक्षणों या लेखांकन अवधियों का प्रतिनिधित्व करते हैं, तो एक यूनियन स्रोत के अर्थ को खो सकता है। मेटाडेटा रखें या उन खंडों को मर्ज न करें।