कोडिंग इंटरव्यू: डायनामिक लाइन मिनिमम क्वेरीज़ के लिए आप Li Chao tree का उपयोग कैसे करेंगे?

समस्या और संदर्भ

एक ऑनलाइन सेवा आर्बिट्रेरी इंसर्शन ऑर्डर में लाइन्स y = m x + b प्राप्त करती है और उसे एक पूर्णांक क्वेरी बिंदु x पर न्यूनतम मान लौटाना होगा। क्वेरी बिंदु भी आर्बिट्रेरी हैं। एक एक्सटेंशन किसी लाइन को एक अंतराल (interval) [l, r] तक सीमित कर सकता है या इसके बजाय अधिकतम मान मांग सकता है।

यह समस्या डायनामिक-प्रोग्रामिंग ऑप्टिमाइज़ेशन, डिवाइड-एंड-कॉन्कर इनवेरिएंट्स और सेगमेंट-ट्री कार्यान्वयन का परीक्षण करती है। एक मजबूत उत्तर पहले यह बताता है कि क्वेरी डोमेन डिस्क्रीट और बाउंडेड है या नहीं, फिर यह बताता है कि प्रत्येक नोड एक ऐसी लाइन को क्यों रख सकता है जो कहीं न कहीं जीतती है, जबकि शेष किसी भी उम्मीदवार को ठीक एक चाइल्ड में भेजा जाता है।

इंटरव्यूअर क्या मूल्यांकन करता है

प्रति क्वेरी O(number_of_lines) में प्रत्येक लाइन को स्कैन करने की बाधा (bottleneck) का पता लगाना।
मिडपॉइंट तुलना, स्वैप और रिकर्सन इनवेरिएंट को समझना।
आर्बिट्रेरी स्लोप, डुप्लिकेट लाइनों, नेगेटिव निर्देशांकों (coordinates) और ओवरफ्लो को संभालना।
डिस्क्रीट पूर्णांक डोमेन, निरंतर (continuous) डोमेन और सेगमेंट-प्रतिबंधित लाइनों के बीच अंतर करना।
O(log C) इंसर्शन/क्वेरी और O(log^2 C) सेगमेंट इंसर्शन बाउंड्स देना।
यह समझाना कि मोनोटोन स्लोप और मोनोटोन क्वेरीज़ मानक कॉन्वेक्स हल ट्रिक को कब सरल बनाती हैं।

पहले पूछे जाने वाले स्पष्टीकरण

क्या क्वेरी बिंदु पूर्णांक हैं या वास्तविक संख्याएँ (reals)? क्या डोमेन निश्चित [L, R] है या डायनामिक रूप से विस्तारित है? यह गहराई और कोऑर्डिनेट कम्प्रेशन निर्धारित करता है।
क्या ऑपरेशन न्यूनतम है या अधिकतम? क्या खाली सेट की अनुमति है, और कौन सा सेंटिनल वास्तविक उत्तर से टकरा नहीं सकता है?
स्लोप, इंटरसेप्ट और उत्तरों के अधिकतम परिमाण (magnitudes) क्या हैं? क्या एक व्यापक पूर्णांक या चेक किया गया गुणन आवश्यक है?
क्या कोई लाइन केवल [l, r] पर लागू होती है? अंतराल इंसर्शन एक लाइन को कई ट्री नोड्स में वितरित करता है।
क्या इंसर्शन स्लोप या क्वेरी बिंदु मोनोटोन हैं? यदि ऐसा है, तो डेक-आधारित (deque-based) कॉन्वेक्स हल ट्रिक छोटे स्थिरांकों (constants) का उपयोग कर सकती है।

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

मैं एक सेगमेंट-ट्री डोमेन [L, R] बनाता हूँ और प्रत्येक नोड पर एक उम्मीदवार लाइन संग्रहीत करता हूँ। एक नई लाइन सम्मिलित करते समय, मैं एंडपॉइंट्स और मिडपॉइंट पर नोड लाइन के साथ इसकी तुलना करता हूँ। यदि नई लाइन मिडपॉइंट पर जीतती है, तो मैं इसे नोड में स्वैप कर देता हूँ। विस्थापित लाइन अभी भी केवल बाएं या दाएं आधे हिस्से में ही जीत सकती है, इसलिए मैं एक चाइल्ड में रिकर्स करता हूँ। एक पॉइंट क्वेरी अपने रूट-टू-लीफ पाथ पर प्रत्येक लाइन का मूल्यांकन करती है और न्यूनतम मान लेती है। डोमेन लंबाई C के साथ, इंसर्शन और क्वेरी O(log C) हैं; किसी लाइन को एक अंतराल तक सीमित करने की लागत O(log^2 C) है। अधिकतम क्वेरीज़ कंपैरेटर को उलट देती हैं।

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

1. ब्रूट फ़ोर्स और बाधा

लाइनों की एक सूची बनाए रखें और प्रत्येक क्वेरी के लिए प्रत्येक m x + b का मूल्यांकन करें। इसमें प्रति क्वेरी O(number_of_lines) की लागत आती है। एक डायनामिक-प्रोग्रामिंग ट्रांजिशन में, इंसर्शन और क्वेरीज़ इंटरलीव होती हैं, इसलिए समस्या को बदले बिना न तो स्लोप और न ही क्वेरी बिंदुओं को सॉर्ट किया जा सकता है। डेटा संरचना को वैल्यू डोमेन पर तुलनाओं को वितरित करना चाहिए।

2. नोड इनवेरिएंट

एक नोड एक बंद अंतराल [lo, hi] का प्रतिनिधित्व करता है और एक लाइन cur को संग्रहीत करता है। उन लाइनों में जो पहले से ही चिल्ड्रन में नहीं धकेली गई हैं, cur इस अंतराल में कम से कम एक उम्मीदवार स्थिति पर बदतर नहीं है। कोई भी अन्य लाइन जो अभी भी इष्टतम बन सकती है, वह केवल बाएं या दाएं चाइल्ड में ही ऐसा कर सकती है। एक लीफ पर, नोड को केवल उस लाइन की आवश्यकता होती है जो एक बिंदु पर सबसे अच्छी हो।

3. मिडपॉइंट स्वैप और रिकर्सन दिशा

मान लीजिए कि nw नई लाइन है, cur नोड लाइन है, और mid मिडपॉइंट है। यदि mid पर नई लाइन का मान छोटा है, तो उन्हें स्वैप करें ताकि नोड मिडपॉइंट विजेता को बनाए रखे। स्वैप के बाद, तुलना करें कि lo पर कौन सी लाइन जीतती है। यदि विस्थापित लाइन बाएं एंडपॉइंट पर जीतती है, तो यह केवल बाएं आधे हिस्से में फिर से दिखाई दे सकती है; अन्यथा दाएं एंडपॉइंट की तुलना करें और दाईं ओर रिकर्स करें। दो लाइनों का अंतर रैखिक (linear) होता है, इसलिए उनका क्रम अधिक से अधिक एक बार बदलता है।

text

add(node, lo, hi, nw):
  mid = (lo + hi) // 2
  left = nw(lo) < cur(lo)
  middle = nw(mid) < cur(mid)
  if middle: swap(nw, cur)
  if lo == hi: return
  if left != middle: add(leftChild, lo, mid, nw)
  else: add(rightChild, mid + 1, hi, nw)

एक सुरक्षित मिडपॉइंट सूत्र का उपयोग करें। यदि m * x + b 64-बिट सीमा से अधिक हो सकता है, तो एक व्यापक प्रकार, जांची गई अंकगणित, या एक स्पष्ट संतृप्ति नीति (saturation policy) का उपयोग करें।

4. रूट-टू-लीफ पाथ को क्वेरी करना

बिंदु x के लिए, x वाले लीफ की ओर रिकर्स करें, प्रत्येक देखे गए नोड पर x पर संग्रहीत लाइन का मूल्यांकन करें, और न्यूनतम लौटाएं। अन्य सब-ट्रीज़ में वह बिंदु शामिल नहीं होता है। एक इम्प्लिसिट ट्री केवल इंसर्शन द्वारा छुए गए पाथ पर नोड्स आवंटित करता है; एक खाली नोड धनात्मक-अनंत (positive-infinity) सेंटिनल लौटाता है।

5. एक अंतराल तक सीमित लाइन को इंसर्ट करना

यदि कोई लाइन केवल [ql, qr] पर मान्य है, तो एक मानक सेगमेंट ट्री के साथ उस अंतराल को विघटित (decompose) करें। प्रत्येक पूरी तरह से कवर किए गए नोड में लाइन को एक बार इंसर्ट करें और आंशिक कवरेज के लिए रिकर्स करें। यह अपघटन O(log C) नोड्स को छूता है और प्रत्येक Li Chao इंसर्शन की लागत O(log C) होती है, जिससे कुल O(log^2 C) मिलता है; पॉइंट क्वेरी O(log C) ही रहती है।

6. डिस्क्रीट निर्देशांक और निरंतर क्वेरीज़

यदि क्वेरीज़ एक ज्ञात परिमित (finite) सेट से आती हैं, तो x-मानों को सॉर्ट करें और डिडुप्लिकेट करें और उनके इंडेक्स को लीफ के रूप में उपयोग करें। यह एक विशाल खाली डोमेन बनाने से बचाता है। वास्तविक-मूल्य वाली (real-valued) क्वेरीज़ के लिए, सटीकता और रुकने की शर्तों को स्पष्ट रूप से बताएं। पूर्णांक-डोमेन प्रमाण स्वचालित रूप से एक अनबाउंडेड निरंतर डोमेन पर लागू नहीं होता है; अंतराल को बाउंड करें और फ़्लोटिंग-पॉइंट तुलना सहनशीलता (tolerance) को परिभाषित करें।

7. ट्रेड-ऑफ और परीक्षण

जब स्लोप और क्वेरी बिंदु दोनों मोनोटोन होते हैं, तो डेक-आधारित कॉन्वेक्स हल ट्रिक में छोटे स्थिरांक होते हैं। Li Chao अधिक नोड्स और रिकर्सन की कीमत पर आर्बिट्रेरी ऑर्डर के लिए अधिक मजबूत है। एक खाली सेट, एक-बिंदु डोमेन, डुप्लिकेट स्लोप, समान लाइनों, नेगेटिव निर्देशांकों, मिडपॉइंट पर प्रतिच्छेदन (intersection), एक एंडपॉइंट को कवर करने वाली लाइन, बड़े गुणनफल और अधिकतम क्वेरीज़ का परीक्षण करें; ब्रूट-फ़ोर्स मूल्यांकन के साथ प्रत्येक परिणाम की तुलना करें।

उच्च-गुणवत्ता वाला मॉडल उत्तर

मैं पहले पुष्टि करूंगा कि क्या क्वेरी डोमेन एक बाउंडेड पूर्णांक अंतराल है या कोऑर्डिनेट कम्प्रेशन की आवश्यकता है। [L, R] के लिए, मैं एक Li Chao tree बनाता हूँ जिसके नोड्स उम्मीदवार लाइनों को संग्रहीत करते हैं। इंसर्शन एंडपॉइंट्स और मिडपॉइंट की तुलना करता है; मिडपॉइंट विजेता नोड पर रहता है, और दूसरी लाइन उस आधे हिस्से में रिकर्स करती है जहाँ दो लाइनें क्रम बदल सकती हैं। उनका अंतर रैखिक होता है, इसलिए विस्थापित लाइन दो अलग-अलग दिशाओं में बेहतर नहीं हो सकती है। एक पॉइंट क्वेरी एक रूट-टू-लीफ पाथ पर न्यूनतम मान लेती है, जिससे इंसर्शन और क्वेरी के लिए O(log C) प्राप्त होता है। यदि स्लोप और क्वेरीज़ मोनोटोन हैं, तो मैं एक कॉन्वेक्स हल ट्रिक का उपयोग करूंगा; अंतराल-प्रतिबंधित लाइनों के लिए सेगमेंट अपघटन और O(log^2 C) इंसर्शन की आवश्यकता होती है।

सामान्य गलतियाँ

केवल मिडपॉइंट की तुलना करना और रुक जाना → दूसरी लाइन एंडपॉइंट पर जीत सकती है → एक चाइल्ड चुनने के लिए एंडपॉइंट और मिडपॉइंट तुलना का उपयोग करें।
यह मान लेना कि स्लोप मोनोटोन होने चाहिए → आर्बिट्रेरी इंसर्शन गलत उत्तर देता है → Li Chao के अंतराल इनवेरिएंट का उपयोग करें या कॉन्वेक्स-हल की पूर्व शर्त बताएं।
अनियंत्रित 64-बिट अंकगणित में m * x + b की गणना करना → ओवरफ्लो तुलनाओं को बदल देता है → व्यापक या जांची गई अंकगणित का उपयोग करें।
एक अनबाउंडेड डायनामिक डोमेन की अनुमति देना → रिकर्सन की कोई समाप्ति नहीं होती है → पूर्णांक डोमेन को बाउंड करें, निर्देशांकों को कंप्रेस करें, या फ़्लोटिंग-पॉइंट सटीकता को परिभाषित करें।
एक अंतराल लाइन को प्रत्येक लीफ में कॉपी करना → जटिलता बिगड़ जाती है → अंतराल को विघटित करें और पूरी तरह से कवर किए गए नोड्स पर इंसर्ट करें।
एक खाली नोड के लिए शून्य लौटाना → न्यूनतम गलत तरीके से कम हो जाता है → उत्तर सीमा के बाहर एक धनात्मक-अनंत सेंटिनल का उपयोग करें।

फॉलो-अप्स और प्रतिक्रियाएं

अधिकतम क्वेरीज़ के लिए क्या बदलता है?

प्रत्येक तुलना को उलट दें, या m और b दोनों को नकारें (negate करें), एक न्यूनतम क्वेरी हल करें, और परिणाम को नकारें। केवल अंतिम रिटर्न मान बदलने के बजाय खाली-सेट और ओवरफ्लो शब्दार्थ (semantics) को लगातार उलटा जाना चाहिए।

क्या एक ऐरे-आधारित ट्री 10 की घात 18 के डोमेन को संभाल सकता है?

प्रत्येक नोड को प्री-एलोकेट करके नहीं। एक इम्प्लिसिट ट्री का उपयोग करें जो केवल इंसर्शन पाथ के साथ नोड्स बनाता है; गहराई लगभग डोमेन बिट्स की संख्या होती है। यदि क्वेरी निर्देशांक परिमित हैं, तो कोऑर्डिनेट कम्प्रेशन आमतौर पर अधिक मेमोरी बचाता है।

दो लाइनें मिडपॉइंट पर टाई होती हैं। आप गलत ब्रांच से कैसे बचते हैं?

एक नियतात्मक (deterministic) टाई नियम चुनें, जैसे पुरानी लाइन को रखना या किसी स्लोप ऑर्डर को प्राथमिकता देना। एंडपॉइंट्स और मिडपॉइंट पर लगातार सख्त असमानताओं (strict inequalities) का उपयोग करें ताकि समान लाइनें हमेशा के लिए रिकर्स न करें।

केवल एक रिकर्सिव पक्ष ही पर्याप्त क्यों है?

दो लाइनों का अंतर रैखिक होता है और इसमें अधिक से अधिक एक शून्य होता है। मिडपॉइंट विजेता को रखे जाने के बाद, विस्थापित लाइन केवल उस एंडपॉइंट की ओर ठीक हो सकती है जहाँ क्रम भिन्न होता है, जो विशिष्ट रूप से बाएं या दाएं चाइल्ड का चयन करता है।

कॉन्वेक्स हल ट्रिक कब बेहतर होती है?

यदि लाइनें मोनोटोन स्लोप ऑर्डर में आती हैं और क्वेरीज़ मोनोटोन हैं, तो एक हल डेक कम मेमोरी के साथ एमोर्टाइज्ड O(1) क्वेरीज़ या O(log n) बाइनरी-सर्च क्वेरीज़ प्रदान कर सकता है। आर्बिट्रेरी ऑर्डर, या सेगमेंट-प्रतिबंधित लाइनें, Li Chao की व्यापकता के पक्ष में हैं।