कोडिंग इंटरव्यू: ओवरलैप को अस्वीकार करने वाला कैलेंडर कैसे लागू करें?

प्रॉम्प्ट और संदर्भ

एक कैलेंडर लागू करें जहां book(start, end) केवल तभी true लौटाता है और इंटरवल को स्टोर करता है जब यह किसी मौजूदा इंटरवल के साथ ओवरलैप नहीं करता है। इंटरवल हाफ-ओपन होते हैं और उनके लिए start < end आवश्यक है; [10, 20) और [20, 30) आसन्न हैं। यह समस्या ऑर्डर्ड स्ट्रक्चर्स, सीमाओं, इंसर्शन टाइमिंग और जटिलता का परीक्षण करती है।

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

मुख्य बात एक सिद्ध करने योग्य ओवरलैप स्थिति है: स्टार्ट्स के सॉर्ट होने पर, केवल तत्काल प्रिडिसेसर (पूर्ववर्ती) और सक्सेसर (उत्तराधिकारी) की जांच करने की आवश्यकता होती है। एक मजबूत उत्तर स्कैन, बैलेंस्ड ट्री और सॉर्टेड ऐरे की तुलना करता है, और फिर नोट करता है कि मल्टी-थ्रेडेड या पर्सिस्टेंट सेवाएं एटॉमिजिटी और लॉकिंग आवश्यकताएं जोड़ती हैं।

स्पष्ट करने के लिए प्रश्न

क्या समय पूर्णांक (integers) हैं या टाइमस्टैम्प, और क्या वे नकारात्मक हो सकते हैं?
क्या start < end को मान्य (validate) किया जाना चाहिए, और अमान्य इनपुट पर क्या होता है?
क्या इंटरवल कड़ाई से हाफ-ओपन हैं, जो समान एंडपॉइंट्स को स्पर्श करने की अनुमति देते हैं?
कितनी बुकिंग और क्या सीमा है; क्या रद्दीकरण या प्रश्नों (queries) की आवश्यकता है?
क्या यह मेमोरी में सिंगल-थ्रेडेड है या एक पर्सिस्टेंट मल्टी-प्रोसेस सेवा है?

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

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

चरण-दर-चरण विस्तृत उत्तर

चरण 1: ओवरलैप को परिभाषित करें

हाफ-ओपन [a, b) और [c, d) सटीक रूप से तब ओवरलैप होते हैं जब a < d && c < b होता है। एक बार स्टार्ट्स क्रमबद्ध हो जाने के बाद, प्रत्यक्ष प्रिडिसेसर और सक्सेसर पर्याप्त होते हैं क्योंकि आगे के इंटरवल्स पहले समाप्त होते हैं या बाद में शुरू होते हैं।

चरण 2: एक ऑर्डर्ड स्ट्रक्चर चुनें

एक बैलेंस्ड ट्री या जावा TreeMap प्रिडिसेसर और सक्सेसर लुकअप प्रदान करता है। एक सॉर्टेड ऐरे में O(log n) सर्च लेकिन O(n) इंसर्शन होता है; एक स्कैन O(n) होता है। बुकिंग वॉल्यूम और ऑपरेशन मिक्स के अनुसार चुनाव का मिलान करें।

चरण 3: इंसर्ट करने से पहले जांचें

सक्सेसर का निरीक्षण करें, फिर प्रिडिसेसर का, और दोनों के पास होने के बाद ही लिखें। पहले इंसर्ट करना और बाद में रोलबैक करना एक अमान्य मध्यवर्ती स्थिति (invalid intermediate state) को उजागर कर सकता है।

java

boolean book(int start, int end) {
  if (start >= end) return false;
  var next = events.ceilingEntry(start);
  if (next != null && next.getKey() < end) return false;
  var prev = events.floorEntry(start);
  if (prev != null && prev.getValue() > start) return false;
  events.put(start, end);
  return true;
}

चरण 4: सीमा व्यवहार को सिद्ध करें

next.start == end और prev.end == start ओवरलैप नहीं होते हैं। समान स्टार्ट्स किसी प्रतिच्छेद करने वाले पुराने इंटरवल को प्रतिस्थापित नहीं कर सकते क्योंकि सक्सेसर जांच इसे अस्वीकार कर देती है। यदि टाइमस्टैम्प ओवरफ्लो हो सकते हैं तो सुरक्षित संख्यात्मक प्रकारों (safe numeric types) का उपयोग करें।

चरण 5: जटिलता बताएं

बैलेंस्ड-ट्री प्रिडिसेसर, सक्सेसर और इंसर्शन O(n) स्पेस के साथ O(log n) हैं। एक सॉर्टेड ऐरे O(log n) में सर्च करता है लेकिन O(n) में इंसर्ट करता है; एक स्कैन सरल है लेकिन खराब तरीके से स्केल करता है। जटिलता चर्चा में अस्वीकृत कॉल्स को शामिल करें।

चरण 6: कॉनकरेंसी और पर्सिस्टेंस तक विस्तार करें

एक मशीन पर, जांच और इंसर्ट को एक साथ लॉक करें। सभी प्रोसेस में, ट्रांजेक्शन, यूनिक कन्स्ट्रेंट या रेंज लॉक का उपयोग करें; कैश अंतिम टकराव प्राधिकरण (conflict authority) नहीं हो सकता है।

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

हाफ-ओपन बनाम क्लोज्ड इंटरवल्स

हाफ-ओपन इंटरवल्स आसन्न स्लॉट्स को स्वाभाविक रूप से व्यक्त करते हैं, इनकी लंबाई end - start होती है, और सीमा दोहराव से बचते हैं। क्लोज्ड-इंटरवल व्यवसाय को ग्रैन्युलैरिटी को लगातार पुनर्परिभाषित करना चाहिए।

TreeMap बनाम एक इंटरवल ट्री

जब प्रत्येक ओवरलैप को अस्वीकार कर दिया जाता है तो प्रिडिसेसर और सक्सेसर पर्याप्त होते हैं। ओवरलैप क्वेरी, रद्दीकरण या रेंज सांख्यिकी एक इंटरवल ट्री या डेटाबेस रेंज इंडेक्स को उचित ठहरा सकती है।

रोलआउट योजना और साक्ष्य

टेस्ट मैट्रिक्स

पहले इंटरवल, कंटेनमेंट, आंशिक ओवरलैप, स्पर्श करने वाले एंडपॉइंट्स, समान स्टार्ट्स, खाली इनपुट, बड़े मान और डुप्लिकेट अनुरोधों को कवर करें। प्रत्येक स्वीकृत बुकिंग के बाद, सॉर्टेड इनवेरिएंट का दावा (assert) करें।

प्रोडक्शन सीमा

मल्टीपल इंस्टेंसेस के लिए ट्रांजेक्शन आइसोलेशन, टकराव त्रुटियां, पुनः प्रयास आइडेम्पोटेंसी कुंजियाँ और समय क्षेत्र नियम परिभाषित करें। समवर्ती बुकिंग के तहत पर्सिस्टेंट कन्स्ट्रेंट का लोड-टेस्ट करें।

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

गलती: केवल सक्सेसर की जाँच करना

नया इंटरवल प्रिडिसेसर के टेल के साथ ओवरलैप हो सकता है, इसलिए प्रिडिसेसर एंड की भी जांच की जानी चाहिए।

गलती: समान एंडपॉइंट्स को ओवरलैप मानना

हाफ-ओपन सेमेन्टिक्स [10, 20) और [20, 30) को स्पर्श करने की अनुमति देते हैं; सख्त तुलना बनाए रखें।

गलती: टकराव का पता लगाने से पहले इंसर्ट करना

इनवेरिएंट को बनाए रखने के लिए जांच और लेखन एक तार्किक एटॉमिक कदम होना चाहिए।

फॉलो-अप: दो ओवरलैप की अनुमति देना

सक्रिय-इंटरवल काउंट या स्वीप लाइन बनाए रखें; कन्स्ट्रेंट एक अधिकतम-ओवरलैप समस्या बन जाता है।

फॉलो-अप: समवर्ती बुकिंग

एक मशीन पर लॉक करें; प्रोसेस-लोकल मेमोरी के बजाय इंस्टेंसेस के बीच ट्रांजेक्शन, रेंज लॉक या सीरियलाइजेबल राइट्स का उपयोग करें।