कोडिंग इंटरव्यू: आप लिंक-कट ट्री (link-cut tree) की मदद से एक डायनामिक फ़ॉरेस्ट कैसे बनाए रखेंगे?

प्रश्न और दायरा

आपके पास एक डायनामिक फ़ॉरेस्ट है जिसके किनारों (edges) को जोड़ा या हटाया जा सकता है और जिसके शीर्षों (vertices) पर पूर्णांक (integers) मान हैं। link(u,v), cut(u,v), पाथ-मैक्सिमम क्वेरीज़ और पाथ एडिशन्स का समर्थन करें। इसके प्रतिनिधित्व, access, makeroot, लेज़ी टैग्स, शुद्धता और जटिलता को समझाएं।

Sleator और Tarjan की डायनामिक-ट्री संरचना दो पेड़ों को जोड़ती है और अमॉर्टाइज़्ड O(log n) ऑपरेशन्स के साथ एक किनारे को काटती है। इंटरव्यू में मुख्य संकेत किसी टेम्पलेट को दोहराने के बजाय, रिप्रजेंटेड-ट्री पाथ्स को सहायक स्प्ले ट्रीज़ में संग्रहीत पसंदीदा पाथ्स (preferred paths) से अलग करने की समझ दिखाना है।

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

यह समझना कि लिंक-कट ट्री एक रिप्रजेंटेड फ़ॉरेस्ट और पसंदीदा पाथ्स के लिए सहायक स्प्ले ट्रीज़ को बनाए रखता है।
isRoot, push, pull, रोटेशन्स और splay को सही ढंग से लागू करना।
यह समझाना कि access रिप्रजेंटेड रूट के पाथ को पसंदीदा पाथ में कैसे बदलता है।
प्रोपेगेशन क्रम को दूषित किए बिना अनरूटेड पाथ्स के लिए लेज़ी रिवर्सल टैग का उपयोग करना।
link से पहले कनेक्टिविटी और cut से पहले सटीक किनारे की पुष्टि करना।
अमॉर्टाइज़्ड O(log n) का उल्लेख करना और ऐरे, रिकर्शन गहराई व रैंडमाइज़्ड टेस्टिंग पर चर्चा करना।

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

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

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

मैं प्रत्येक रिप्रजेंटेड वर्टेक्स के लिए एक ऑक्जिलरी स्प्ले का उपयोग करता हूँ। ch स्प्ले चिल्ड्रन को स्टोर करता है और fa या तो एक ऑक्जिलरी पैरेंट है या एक रिप्रजेंटेड-पाथ पैरेंट है। access ऊपर की ओर बढ़ता है, प्रत्येक दाएँ चाइल्ड को पहले से संसाधित पाथ से बदलता है; makeroot ऑक्जिलरी ट्री को एक्सेस करता है और लेज़ी तरीके से रिवर्स करता है। link कनेक्टिविटी की जाँच करता है, एक एंडपॉइंट को makeroot करता है और उसे जोड़ता है। cut एक एंडपॉइंट को makeroot करता है, दूसरे को एक्सेस करता है, यह सत्यापित करता है कि बायाँ सबट्री बिल्कुल वही एज एंडपॉइंट है, और उसे डिस्कनेक्ट करता है। रोटेशन से पहले push करें और अपडेट के बाद pull करें; ऑपरेशन्स अमॉर्टाइज़्ड O(log n) होते हैं।

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

1. दो ट्री संबंधों का प्रतिनिधित्व करें

ऑक्जिलरी-स्प्ले चिल्ड्रन एक पसंदीदा पाथ पर क्रम का वर्णन करते हैं। जब कोई नोड ऑक्जिलरी रूट होता है, तो fa स्प्ले पैरेंट नहीं होता है; यह रिप्रजेंटेड ट्री में पाथ पैरेंट होता है। इसलिए isRoot(x) को यह जांचना चाहिए कि x, fa[x] का कोई भी चाइल्ड नहीं है, न कि केवल यह कि fa[x] शून्य है।

2. एग्रीगेट्स और लेज़ी टैग्स को बनाए रखें

पाथ मैक्सिमम के लिए, pull(x), x के मान को दोनों ऑक्जिलरी सबट्रीज़ के साथ जोड़ता है। पाथ एडिशन के लिए add टैग का उपयोग किया जाता है; पाथ रिवर्सल rev टैग के तहत बच्चों की अदला-बदली करता है। push को एडिशन से पहले रिवर्सल को प्रोपेगेट करना चाहिए, या अन्यथा एक सिद्ध कंपोज़िशनल क्रम परिभाषित करना चाहिए।

text

pull(x): mx[x] = max(value[x], mx[ch[x][0]], mx[ch[x][1]])
applyAdd(x,d): value[x] += d; mx[x] += d; add[x] += d
applyRev(x): swap(ch[x][0], ch[x][1]); rev[x] ^= true

3. access को लागू करें

last = 0 सेट करें और x से fa के माध्यम से ऊपर बढ़ें: y को स्प्ले करें, y के दाएँ चाइल्ड को last पर सेट करें, y को pull करें, फिर last को y पर सेट करें और जारी रखें। अंत में मूल x को स्प्ले करें। x से रिप्रजेंटेड रूट तक का पाथ अब एक पसंदीदा पाथ है जिसका स्प्ले क्रम पाथ एग्रीगेट्स का उत्तर दे सकता है।

4. makeroot को लागू करें

makeroot(x), access(x) को कॉल करता है और x पर rev लागू करता है। x रिप्रजेंटेड-ट्री का रूट बन जाता है, जिससे link(x,y) दो पेड़ों को इच्छित दिशा में जोड़ सकता है। रिप्रजेंटेड ट्री को रिकर्सिव रूप से रिवर्स न करें; ऑक्जिलरी स्प्ले लेज़ी रिवर्सल को संभाल सकता है।

5. link और cut को लागू करें

link(x,y), makeroot(x) को कॉल करता है, findroot(y) == x को अस्वीकार करता है, फिर fa[x] = y सेट करता है। cut(x,y) के लिए, makeroot(x) और access(y) को कॉल करें। यदि किनारा मौजूद है, तो y का बायाँ चाइल्ड x है और x का कोई दायाँ चाइल्ड नहीं है; उस चाइल्ड को डिस्कनेक्ट करें और उसके पैरेंट को साफ़ करें। यह संरचनात्मक जाँच किसी भिन्न पाथ किनारे को काटने से रोकती है।

6. पाथ को क्वेरी और अपडेट करें

split(x,y), makeroot(x); access(y) है, जिससे y का ऑक्जिलरी स्प्ले x-से-y पाथ बन जाता है। मैक्सिमम के लिए mx[y] पढ़ें या पाथ अपडेट के लिए y पर applyAdd लागू करें। पसंदीदा पाथ्स को रीस्टोर करने की आवश्यकता नहीं है; अगला access उन्हें पुनर्गठित करेगा।

7. जटिलता और परीक्षण

Sleator–Tarjan का विश्लेषण link, cut, root और evert के लिए अमॉर्टाइज़्ड O(log n) और O(n) स्पेस देता है। एक सीधे एडजेसेंसी फ़ॉरेस्ट के विरुद्ध एक छोटे कार्यान्वयन की क्रॉस-चेक करें: मान्य लिंक्स और कट्स उत्पन्न करें, पाथ मैक्सिमा और एडिशन्स की तुलना करें, और सिंगलटन ट्रीज़, बार-बार makeroot, लगातार एक्सेस, अमान्य कट्स, समान मान और ऋणात्मक मानों को शामिल करें।

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

मैं रिप्रजेंटेड ट्री को एक साधारण बाइनरी ट्री के रूप में मानने के बजाय, fa को ऑक्जिलरी पैरेंट या रिप्रजेंटेड-पाथ पैरेंट मानूंगा और उन्हें isRoot से अलग करूंगा। प्रत्येक स्प्ले नोड अपना मान, सबट्री मैक्सिमम, रिवर्सल टैग और एडिशन टैग संग्रहीत करता है। access एक पसंदीदा पाथ को एक्सपोज़ करता है; makeroot इसे लेज़ी रूप से रिवर्स करता है; split(x,y), y के स्प्ले को x-से-y पाथ का प्रतिनिधित्व करने वाला बनाता है।

link makeroot करता है और पहले से जुड़े एंडपॉइंट्स को अस्वीकार करता है। cut makeroot और access करता है, फिर डिस्कनेक्ट करने से पहले सत्यापित करता है कि y का बायाँ सबट्री बिल्कुल x है। रोटेशन से पहले पूर्वजों (ancestors) को push करें और बदलाव के बाद pull करें। यह संरचना अमॉर्टाइज़्ड O(log n) समय और O(n) स्पेस का उपयोग करती है; एक सीधे फ़ॉरेस्ट के विरुद्ध रैंडमाइज़्ड क्रॉस-चेक एग्रीगेट्स, अमान्य ऑपरेशन्स और लेज़ी-टैग संयोजनों को कवर करते हैं।

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

ऑक्जिलरी रूट के लिए fa[x] == 0 की जाँच करना → पाथ पैरेंट गैर-शून्य हो सकता है → चाइल्ड-आधारित isRoot परीक्षण का उपयोग करें।
रोटेशन से पहले पूर्वजों के push को छोड़ना → रिवर्सल या एडिशन छिपा रह जाता है → पूर्वजों को इकट्ठा करें और उल्टे क्रम में push करें।
किनारे की जाँच किए बिना काटना → गलत पाथ किनारा हट जाता है → makeroot/access के बाद बाएँ सबट्री के आकार को सत्यापित करें।
कनेक्टिविटी जाँच के बिना लिंक करना → एक साइकल फ़ॉरेस्ट इनवेरिएंट को तोड़ देता है → पहले रूट्स की तुलना करें।
access के बाद के स्प्ले को पूरा रिप्रजेंटेड ट्री मानना → केवल एक पसंदीदा पाथ एक्सपोज़ होता है → भविष्य के access ऑपरेशन्स पर भरोसा करें।
क्वेरीज़ का परीक्षण करना लेकिन अपडेट्स का नहीं → लेज़ी-टैग बग्स छिपे रहते हैं → एक सीधे फ़ॉरेस्ट के साथ रैंडम पाथ एडिशन्स की तुलना करें।

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

आप पाथ मिनिमम या XOR को कैसे बनाए रखेंगे?

pull को आवश्यक मोनोइड एग्रीगेट से बदलें। XOR रिवर्सल के तहत क्रम-असंवेदनशील है; एक गैर-क्रमविनिमेय (non-commutative) एग्रीगेट को पाथ की दिशा और रिवर्सल क्रम को स्पष्ट रूप से परिभाषित करना चाहिए।

आप किनारे के भार (edge weights) को कैसे शामिल करते हैं?

प्रत्येक किनारे को एक वर्चुअल वर्टेक्स में विभाजित करें जिसका मान किनारे का भार हो, फिर सामान्य वर्टेक्स एग्रीगेशन का उपयोग करें। लिंक और कट करते समय उस वर्चुअल वर्टेक्स को प्रबंधित करें।

access एक पुराने दाएँ सबट्री को क्यों बदल सकता है?

पुराना सबट्री एक रिप्रजेंटेड-पाथ पैरेंट के रूप में fa के माध्यम से जुड़ा रहता है; यह केवल अब पसंदीदा नहीं रह जाता है। ऑक्जिलरी-चाइल्ड संबंध और पाथ-पैरेंट संबंध अलग-अलग हैं।

क्या पाथ असाइनमेंट समर्थित किया जा सकता है?

एक असाइनमेंट टैग जोड़ें जो पुराने एडिशन्स को ओवरराइट करता है, मान और मैक्सिमम को अपडेट करता है, और एक परिभाषित क्रम में रिवर्सल के साथ संयोजित होता है। टैग बीजगणित स्पष्ट और परीक्षण योग्य होना चाहिए।

findroot सही क्यों है?

access(x) के बाद, सबसे बाएँ ऑक्जिलरी नोड तक सबसे बाएँ चाइल्ड का अनुसरण करते हुए टैग्स को push करें। वह नोड रिप्रजेंटेड रूट है; बाद के ऑपरेशन्स को स्थिर करने के लिए इसे स्प्ले करें।

आपको लिंक-कट ट्री से कब बचना चाहिए?

एक स्थिर फ़ॉरेस्ट के लिए, DFS/Euler टूर्स या हैवी-लाइट डिकम्पोज़िशन (HLD) अधिक सरल हैं। सामान्य डायनामिक-ग्राफ़ कनेक्टिविटी, समवर्तीता या पर्सिस्टेंस के लिए, रखरखाव की सीमा और कार्यान्वयन का जोखिम इसके लाभ से अधिक हो सकता है।