कोडिंग इंटरव्यू: वर्ज़न वाले रेंज प्रश्नों के लिए एक परसिस्टेंट सेगमेंट ट्री लागू करें

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

इतिहास (history) के साथ एक पूर्णांक (integer) एरे संरचना लागू करें। प्रत्येक अपडेट एक स्थिति को बदलता है, और एक क्वेरी किसी भी पुराने वर्ज़न में बंद अंतराल (closed-interval) के योग की मांग कर सकती है। पुराने वर्ज़न अपरिवर्तनीय (immutable) रहने चाहिए। निर्देशांक सीमाओं (coordinate bounds), समय और स्थान जटिलता (time and space complexity), शाखाओं वाले वर्ज़न (branching versions) और परीक्षणों की व्याख्या करें।

यह डिवाइड-एंड-कॉन्कर, स्ट्रक्चरल शेयरिंग, इम्यूटिएबल अपडेट, सीमाओं और जटिलता प्रमाणों के बारे में एक कठिन डेटा-स्ट्रक्चर प्रश्न है। मान लें कि एरे की लंबाई निश्चित है, पॉइंट असाइनमेंट अपडेट हैं, और बंद-अंतराल रेंज सम [l, r] हैं। रेंज अपडेट, डिलीशन या वर्ज़न मर्ज करना अलग एक्सटेंशन हैं और लागू करने से पहले उनका उल्लेख किया जाना चाहिए।

साक्षात्कारकर्ता क्या जांच रहा है

साक्षात्कारकर्ता यह स्पष्ट करवाना चाहता है कि पर्सिस्टेंस पुराने रूट्स को क्वेरिएबल बनाए रखती है; यह प्रत्येक अपडेट के लिए पूरे ट्री को कॉपी नहीं करती है। एक मजबूत कार्यान्वयन अपडेट पाथ के साथ नए नोड्स बनाता है, अछूते सबट्रीज का पुन: उपयोग करता है, और प्रति वर्ज़न एक रूट संग्रहीत करता है। यह अंतराल परिपाटी (interval convention), खाली क्वेरी व्यवहार, वर्ज़न नंबरिंग, ऋणात्मक मान, सीमाओं और स्पेस सीमा को भी स्पष्ट करता है।

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

• क्या एरे की लंबाई और निर्देशांक स्पेस निश्चित हैं, या निर्देशांकों को पहले कंप्रेस किया जा सकता है?
• क्या अपडेट एक असाइनमेंट है या इन्क्रीमेंट, और क्या एक ही स्थिति को बार-बार अपडेट किया जा सकता है?
• क्या रेंज बंद हैं या अर्ध-खुली (half-open), और एक खाली रेंज को क्या लौटाना चाहिए?
• क्या कोई वर्ज़न किसी भी पुराने रूट से शाखा (branch) बना सकता है, या केवल नवीनतम वर्ज़न से ही जोड़ा जा सकता है?
• क्या थ्रेड सुरक्षा, डिस्क पर्सिस्टेंस, या क्रॉस-प्रोसेस शेयरिंग की आवश्यकता है?
• क्या हमें सटीक पूर्णांक योग, ओवरफ्लो जांच या बड़े पूर्णांकों (big integers) की आवश्यकता है?
• वर्ज़न और कुल ऑपरेशनों की सीमाएं क्या हैं?

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

“मैं प्रत्येक वर्ज़न को एक इम्यूटिएबल सेगमेंट ट्री के रूट द्वारा दर्शाऊंगा। एक पॉइंट अपडेट रूट से लीफ तक O(log n) नोड्स को कॉपी करता है, प्रत्येक अछूते सिबलिंग सबट्री को शेयर करता है, और एक क्वेरी अनुरोधित रूट से नीचे उतरती है, पूर्ण कवरेज के लिए नोड सम लौटाती है। रूट्स का एक एरे किसी भी पुराने वर्ज़न से शाखा बनाने की अनुमति देता है। निर्माण O(n) है; प्रत्येक अपडेट और क्वेरी O(log n) है; कुल स्पेस प्रारंभिक ट्री प्लस प्रति अपडेट O(log n) नए नोड्स है। मैं फोर्क्स, सीमाओं, ऋणात्मक मानों और रैंडम डिफरेंशियल मामलों का परीक्षण करूंगा।”

चरण-दर-चरण उत्तर

पहले इनवेरिएंट बताएं: एक नोड एक विशिष्ट बंद अंतराल [lo, hi] को कवर करता है, sum उसके वर्ज़न में उस अंतराल का योग है, एक लीफ एक स्थिति को कवर करती है, एक आंतरिक योग उसके बच्चों के योग के बराबर होता है, और निर्माण के बाद एक नोड को कभी भी म्यूटेट नहीं किया जाता है। प्रत्येक वर्ज़न एक रूट पॉइंटर संग्रहीत करता है।

एरे इंडेक्स 0..n-1 के लिए, रिकर्सिव रूप से निर्माण करें। यदि इनपुट विरल (sparse), बड़े पूर्णांक निर्देशांकों का उपयोग करता है, तो संभावित निर्देशांक एकत्र करें और निर्माण से पहले उन्हें कंप्रेस करें; एक विशाल निर्देशांक स्पेस को सीधे न बनाएं।

निम्नलिखित स्यूडोकोड असाइनमेंट अपडेट और बंद-अंतराल प्रश्नों का उपयोग करता है:

Node { left, right, sum }

build(lo, hi, values):
  if lo == hi: return Node(null, null, values[lo])
  mid = floor((lo + hi) / 2)
  left = build(lo, mid, values)
  right = build(mid + 1, hi, values)
  return Node(left, right, left.sum + right.sum)

set(node, lo, hi, index, value):
  if lo == hi: return Node(null, null, value)
  mid = floor((lo + hi) / 2)
  if index <= mid:
    nextLeft = set(node.left, lo, mid, index, value)
    nextRight = node.right
  else:
    nextLeft = node.left
    nextRight = set(node.right, mid + 1, hi, index, value)
  return Node(nextLeft, nextRight, nextLeft.sum + nextRight.sum)

sum(node, lo, hi, ql, qr):
  if qr < lo or hi < ql: return 0
  if ql <= lo and hi <= qr: return node.sum
  mid = floor((lo + hi) / 2)
  return sum(node.left, lo, mid, ql, qr)
       + sum(node.right, mid + 1, hi, ql, qr)

roots[0] प्रारंभिक ट्री को संग्रहीत करता है। वर्ज़न base से स्थिति i को अपडेट करने के लिए, roots[next] = set(roots[base], 0, n - 1, i, value) बनाएं। वर्ज़न ग्राफ रूट्स द्वारा संदर्भित एक निर्देशित एसाइक्लिक साझा संरचना (DAG) है, न कि एक लीनियर इतिहास श्रृंखला। ब्रांचिंग का अर्थ है किसी भी पुराने रूट को अपडेट इनपुट के रूप में चुनना।

सीमाओं को स्पष्ट रूप से संभालें: n == 0 के लिए, रूट न बनाएं; सीमा से बाहर के इंडेक्स और ql > qr को एक संरचित त्रुटि लौटानी चाहिए या बताए गए अनुबंध का पालन करना चाहिए; किसी क्वेरी को क्लिप करने से कॉलर की त्रुटि छिपनी नहीं चाहिए। जब पूर्णांक सीमाएं बड़ी हो सकती हैं, तो lo + floor((hi - lo) / 2) की गणना करके lo + hi ओवरफ्लो से बचें।

प्रारंभिक निर्माण में O(n) नोड्स और समय का उपयोग होता है। एक पॉइंट अपडेट एक रूट-टू-लीफ पाथ को कॉपी करता है, इसलिए यह O(log n) नोड्स बनाता है; एक रेंज क्वेरी O(log n) कैनोनिकल सेगमेंट पर जाती है और O(log n) समय लेती है। u अपडेट के बाद, कुल स्पेस O(n + u log n) है, न कि O(nu)। रेंज असाइनमेंट या जोड़ भी पाथ कॉपी करने का उपयोग कर सकते हैं, लेकिन लेज़ी टैग (lazy tags), नोड संयोजन और स्पेस सीमाएं बदल जाती हैं।

इम्यूटिएबिलिटी शुद्धता की सीमा है। अपडेट के दौरान कभी भी किसी पुराने नोड के sum या चाइल्ड पॉइंटर को संशोधित न करें। कचरा संग्रहण (Garbage collection) या संदर्भ गणना (reference counting) नोड्स को पुनः प्राप्त कर सकती है; मैन्युअल रिक्लेमेशन को पता होना चाहिए कि कौन से वर्ज़न रूट्स सक्रिय हैं, क्योंकि एक वर्ज़न को हटाने से उन नोड्स को मुक्त नहीं किया जा सकता जो अभी भी दूसरे वर्ज़न द्वारा साझा किए गए हैं।

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

छोटे एरे के साथ परीक्षण शुरू करें। प्रत्येक अपडेट के बाद, एक साधारण एरे कॉपी करें और परसिस्टेंट संरचना के साथ रैंडम वर्ज़न और रेंज की तुलना करें। वर्ज़न 0 से ब्रांचिंग, एक ही स्थिति में बार-बार अपडेट, ऋणात्मक मान, एकल तत्व, पूर्ण रेंज, एकल बिंदु, खाली रेंज और दोनों सीमाओं को कवर करें। शेयरिंग की भी जांच करें: एक स्थिति को अपडेट करने के बाद, अछूते सबट्री को समान ऑब्जेक्ट पहचान बनाए रखनी चाहिए।

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

उच्च गुणवत्ता वाला नमूना उत्तर

“मैं एक निश्चित लंबाई वाले एरे, पॉइंट असाइनमेंट अपडेट, बंद-अंतराल योग और किसी भी पुराने वर्ज़न से ब्रांचिंग मानूंगा। प्रत्येक नोड [lo, hi] को कवर करता है और अपना योग संग्रहीत करता है; निर्माण के बाद नोड्स अपरिवर्तनीय होते हैं। roots[v] वर्ज़न v के लिए रूट संग्रहीत करता है।

रिकर्सिव रूप से निर्माण करें। अपडेट पर, लक्षित लीफ के पाथ को कॉपी करें: लक्षित तरफ एक नया चाइल्ड बनाएं, दूसरी तरफ पुराने पॉइंटर का पुन: उपयोग करें, और अपने बच्चों के योग से प्रत्येक नया पैरेंट बनाएं। अनुरोधित रूट से क्वेरी करें; कोई ओवरलैप न होने पर शून्य लौटाएं, पूर्ण कवरेज के लिए नोड सम लौटाएं, अन्यथा रिकर्स करें।

निर्माण O(n) समय और स्पेस है। प्रत्येक अपडेट O(log n) नोड्स बनाता है, और अपडेट और क्वेरी दोनों O(log n) हैं; u अपडेट के बाद, कुल स्पेस O(n + u log n) है। पुराने रूट्स अभी भी पुराने नोड्स की ओर इशारा करते हैं, इसलिए ऐतिहासिक वर्ज़न दूषित नहीं हो सकते। पहले एक बड़े निर्देशांक स्पेस को कंप्रेस करें; रेंज अपडेट के लिए, लेज़ी टैग और स्पेस का पुनर्मूल्यांकन करें।

मैं वर्ज़न 0 से फोर्क्स, बार-बार अपडेट, ऋणात्मक मान, खाली रेंज और प्रत्येक सीमा का एक प्लेन-एरे ऑरेकल के विरुद्ध परीक्षण करूंगा। मैं सत्यापित करूंगा कि अछूते सबट्रीज साझा किए गए हैं और नए अपडेट के बाद पुरानी क्वेरीज़ अपरिवर्तित रहती हैं। यदि केवल नवीनतम मान की आवश्यकता है, तो मैं एक नियमित सेगमेंट ट्री का उपयोग करूंगा और केवल तभी पर्सिस्टेंस चुनूंगा जब इतिहास या रोलबैक एक वास्तविक आवश्यकता हो।”

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

• पूरे ट्री को कॉपी करना → प्रत्येक अपडेट O(n) स्पेस बन जाता है → केवल रूट-टू-लीफ पाथ को कॉपी करें।
• एक पुराने नोड को म्यूटेट करना और एक नया रूट सहेजना → इसे साझा करने वाला प्रत्येक पुराना वर्ज़न बदल जाता है → नोड्स को अपरिवर्तनीय रखें।
• वर्ज़न को एक श्रृंखला मानना → आप किसी भी मनमाने रूट से प्रयोग या रोलबैक नहीं कर सकते → रूट एरे को ब्रांच करने की अनुमति दें।
• अंतराल परिपाटी को अंतर्निहित छोड़ना → बंद और अर्ध-खुली रेंज बाउंड्री बग बनाती हैं → इनवेरिएंट और हस्ताक्षरों में एक परिपाटी तय करें।
• विशाल निर्देशांकों को सीधे बनाना → स्पेस वास्तविक बिंदुओं की तुलना में बहुत बड़ा हो सकता है → निर्देशांक कंप्रेस करें या गतिशील नोड्स का उपयोग करें।
• O(n) कुल स्पेस का दावा करना → प्रत्येक अपडेट पाथ नोड्स जोड़ता है → O(n + u log n) बताएं।
• वर्ज़न हटाते समय नोड्स को रिकर्सिव रूप से मुक्त करना → दूसरा वर्ज़न अभी भी उन्हें साझा कर सकता है → रेफरेंस काउंटिंग या कचरा संग्रहण का उपयोग करें।

फॉलो-अप प्रश्न और उत्तर

फॉलो-अप 1: क्या यह संरचना रेंज जोड़ने (range addition) के लिए भी काम करती है?

अपडेट द्वारा छुए गए नोड्स को पाथ-कॉपी करें और प्रत्येक प्रासंगिक पाथ को कॉपी करें। यदि लेज़ी टैग का उपयोग किया जाता है, तो टैग एक नए नोड से संबंधित होता है और इसे कभी भी साझा किए गए नोड में नहीं लिखा जाना चाहिए। नए-नोड की संख्या O(log n) से O(log n प्लस कवर्ड नोड्स) तक हो सकती है, इसलिए पॉइंट-अपडेट दावे का पुन: उपयोग करने के बजाय वास्तविक कार्यान्वयन के लिए सीमाएं दें।

फॉलो-अप 2: आप दो वर्ज़न के बीच के अंतर की क्वेरी कैसे करेंगे?

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

फॉलो-अप 3: हर बार एरे को कॉपी करके प्रीफिक्स सम क्यों न बनाएं?

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

फॉलो-अप 4: आप वर्ज़न रूट्स को डिस्क पर कैसे परसिस्ट करते हैं?

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

फॉलो-अप 5: आप कैसे साबित करते हैं कि एक पुराना वर्ज़न दूषित नहीं हुआ है?

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