कोडिंग साक्षात्कार: डायनेमिक निकटतम-चिह्नित-नोड दूरी के लिए सेंट्रॉइड डिकम्पोज़िशन का उपयोग करें

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

यह कठिन कोडिंग समस्या ट्री डिकम्पोज़िशन, दूरी प्रीप्रोसेसिंग और डायनेमिक क्वेरीज़ का परीक्षण करती है। ट्री में n शीर्ष (vertices) और n-1 किनारे (edges) हैं; ऑपरेशन्स ऑनलाइन प्राप्त होते हैं, प्रारंभिक अवस्था में एक काला शीर्ष होता है, और टॉगल मनमाने होते हैं। एक क्वेरी को पूरे ट्री को फिर से पार किए बिना वर्तमान निकटतम-काले नोड की दूरी लौटानी होगी।

साक्षात्कारकर्ता क्या मूल्यांकन करता है

• एक सही बेसलाइन के साथ शुरुआत करना और बार-बार ट्रैवर्सल को बाधा (bottleneck) के रूप में पहचानना।
• यह साबित करना कि प्रत्येक नोड में लघुगणकीय-लंबाई (logarithmic-length) वाली सेंट्रॉइड-पूर्वज श्रृंखला होती है और उसकी दूरियों को बनाए रखना।
• घटक बहिष्करण (component exclusion), डुप्लिकेट दूरियां, प्रारंभ में खाली काला सेट और पूर्णांक सीमाओं को संभालना।
• सेंट्रॉइड डिकम्पोज़िशन की तुलना मल्टी-सोर्स BFS, हेवी-लाइट डिकम्पोज़िशन और केवल-सम्मिलन (insertion-only) वाले वेरिएंट्स से करना।

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

पुष्टि करें कि ट्री स्थिर है, किनारे यूनिट हैं या सकारात्मक रूप से भारित (weighted) हैं, ऑपरेशन्स ऑनलाइन हैं, क्या क्वेरी को नोड आईडी की भी आवश्यकता है, और क्या पुनर्गठन (reordering) की अनुमति है। सकारात्मक किनारे के भार भारित दूरियों को संग्रहीत करके भी काम करते हैं; किनारे के अपडेट के लिए एक अलग डायनेमिक-ट्री डिज़ाइन की आवश्यकता होती है।

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

मैं सबसे पहले बेसलाइन दूंगा: u से BFS प्रति क्वेरी लीनियर है। फिर मैं एक सेंट्रॉइड डिकम्पोज़िशन बनाता हूँ। प्रत्येक नोड प्रत्येक सेंट्रॉइड पूर्वज के लिए अपनी दूरी संग्रहीत करता है, और प्रत्येक सेंट्रॉइड वर्तमान में काले नोड से न्यूनतम दूरी संग्रहीत करता है। एक क्वेरी u के सेंट्रॉइड पूर्वजों के साथ "u से सेंट्रॉइड तक की दूरी प्लस उस सेंट्रॉइड की सर्वश्रेष्ठ काली दूरी" को न्यूनतम करती है; एक टॉगल उसी श्रृंखला को अपडेट करता है। श्रृंखला लघुगणकीय है, इसलिए हीप लागतों को छोड़कर ऑपरेशन्स लघुगणकीय हैं, जिसमें लीनियर-लॉगरिदमिक प्रीप्रोसेसिंग होती है।

चरण-दर-चरण गहन उत्तर

1. बेसलाइन और बॉटलनेक स्थापित करें

u से BFS सही है, लेकिन एक क्वेरी लगभग हर शीर्ष पर जा सकती है। बार-बार टॉगल के बाद u के करीब कौन से काले शीर्ष हैं, इसका कोई पुन: प्रयोज्य सारांश नहीं है। एक वैश्विक मल्टी-सोर्स BFS केवल तभी मदद करता है जब काला सेट बैचों में बदलता है, ऑनलाइन फ़्लिप्स के साथ नहीं।

2. सेंट्रॉइड चुनें और पूर्वज श्रृंखलाएं बनाएं

वर्तमान कनेक्टेड घटक का एक सेंट्रॉइड खोजें ताकि इसे हटाने पर प्रत्येक घटक मूल आकार के अधिकतम आधे आकार का रह जाए। सेंट्रॉइड ट्री बनाने के लिए उन घटकों पर रिकर्सन लागू करें। एक मूल शीर्ष u की एक सेंट्रॉइड-पूर्वज श्रृंखला होती है; प्रत्येक लिंक के लिए एक जोड़ी (centroid, distance) प्रीप्रोसेस करें। घटक का आकार प्रत्येक स्तर पर आधा हो जाता है, इसलिए श्रृंखला की लंबाई लघुगणकीय होती है।

3. अपडेट और क्वेरी इनवेरिएंट्स बनाए रखें

प्रत्येक सेंट्रॉइड c के लिए, वर्तमान में सभी काले शीर्षों v पर न्यूनतम dist(v,c) बनाए रखें। लेज़ी विलोपन (lazy deletion) वाला एक मिन-हीप या मल्टीसेट इसका समर्थन करता है। update(u), u की सेंट्रॉइड श्रृंखला के साथ dist(u,c) को सम्मिलित या हटाता है। query(u) उस श्रृंखला पर dist(u,c) + best[c] को न्यूनतम करता है। u से किसी काले v तक का कोई भी पथ किसी डिकम्पोज़िशन स्तर पर उनके साझा सेंट्रॉइड से होकर गुजरता है, इसलिए एक उम्मीदवार इष्टतम पथ का प्रतिनिधित्व करता है; कोई भी शाखा छोड़ी नहीं जाती है।

4. डुप्लिकेट दूरियों और हीप विलोपन को संभालें

दो हीप्स के साथ, लाइव हीप में डालें और डेड हीप में विलोपन रिकॉर्ड करें; शीर्ष को पढ़ने से पहले, समान जोड़ों को हटा दें। समान दूरियों के लिए दूरी और नोड आईडी दोनों को संग्रहीत करने की आवश्यकता होती है, अन्यथा एक नोड को हटाने से दूसरा नोड हटाया जा सकता है। प्रारंभिक काले नोड के लिए एक अपडेट लागू करें, और सेट खाली होने पर -1 जैसा प्रलेखित सेंटिनल लौटाएं।

5. जटिलता और विकल्प

प्रीप्रोसेसिंग प्रत्येक डिकम्पोज़िशन स्तर को पार करती है, जिससे O(n log n) समय और O(n log n) संग्रहीत लिंक प्राप्त होते हैं। प्रत्येक ऑपरेशन एक लघुगणकीय श्रृंखला को स्कैन करता है और हीप ऑपरेशन्स करता है, जिससे एक लघुगणकीय हीप कारक जुड़ता है। यदि नोड्स केवल डाले जाते हैं, तो एक हीप सरल होता है; यदि ऑपरेशन एक सहयोगी पथ समुच्चय (associative path aggregate) है, तो सेगमेंट ट्री के साथ हेवी-लाइट डिकम्पोज़िशन अधिक सीधा है; ऑफ़लाइन ऑपरेशन्स समय डिवाइड-एंड-कॉन्कर का उपयोग कर सकते हैं।

6. C++ कार्यान्वयन कंकाल (skeleton)

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

#include <bits/stdc++.h>
using namespace std;
struct Entry { int d, u; bool operator>(const Entry& o) const { return tie(d,u) > tie(o.d,o.u); } };
int n; vector<vector<int>> g; vector<int> sub, dead, black;
vector<vector<pair<int,int>>> chain;
vector<priority_queue<Entry, vector<Entry>, greater<Entry>>> liveHeap, deadHeap;
void calcSize(int u,int p){sub[u]=1;for(int v:g[u])if(v!=p&&!dead[v]){calcSize(v,u);sub[u]+=sub[v];}}
int findCentroid(int u,int p,int total){for(int v:g[u])if(v!=p&&!dead[v]&&sub[v]>total/2)return findCentroid(v,u,total);return u;}
void collect(int u,int p,int c,int d){chain[u].push_back({c,d});for(int v:g[u])if(v!=p&&!dead[v])collect(v,u,c,d+1);}
void decompose(int entry){calcSize(entry,-1);int c=findCentroid(entry,-1,sub[entry]);dead[c]=1;collect(c,-1,c,0);for(int v:g[c])if(!dead[v])decompose(v);}
void clean(int c){while(!liveHeap[c].empty()&&!deadHeap[c].empty()&&liveHeap[c].top().d==deadHeap[c].top().d&&liveHeap[c].top().u==deadHeap[c].top().u){liveHeap[c].pop();deadHeap[c].pop();}}
void update(int u){black[u]^=1;for(auto [c,d]:chain[u]){if(black[u])liveHeap[c].push({d,u});else deadHeap[c].push({d,u});}}
int query(int u){const int INF=1e9;int ans=INF;for(auto [c,d]:chain[u]){clean(c);if(!liveHeap[c].empty())ans=min(ans,d+liveHeap[c].top().d);}return ans==INF?-1:ans;}

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

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

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

• प्रत्येक क्वेरी के लिए BFS → सही है लेकिन ऑनलाइन बहुत धीमा है → बेसलाइन बताएं, फिर सेंट्रॉइड श्रृंखला का उपयोग करें।
• केवल निकटतम सेंट्रॉइड को अपडेट करना → एक पथ उच्च सेंट्रॉइड को पार कर सकता है → प्रत्येक सेंट्रॉइड पूर्वज को संग्रहीत करें।
• केवल दूरी द्वारा लेज़ी विलोपन → समान दूरी वाले नोड्स टकराते हैं → हीप कुंजी में नोड आईडी शामिल करें।
• सेंट्रॉइड डिकम्पोज़िशन को LCA मानना → वे अलग-अलग कार्यों को हल करते हैं → बताएं कि यह नोड से डायनेमिक सेट तक की दूरी बनाए रखता है।
• खाली काले सेट की उपेक्षा करना → एक अप्रारंभीकृत बड़ा मान लौटाता है → -1 सेंटिनल को परिभाषित और समझाएं।

अनुवर्ती प्रश्न और उत्तर

सकारात्मक किनारे के भार एल्गोरिदम को कैसे बदलते हैं?

प्रत्येक सेंट्रॉइड श्रृंखला एकत्र करते समय किनारे के भार को संचित करें और हीप्स में भारित दूरियों को संग्रहीत करें। डिकम्पोज़िशन अभी भी घटक शीर्ष गणनाओं का उपयोग करता है; गैर-नकारात्मक भार के लिए न्यूनतम-दूरी इनवेरिएंट अपरिवर्तित रहता है।

यदि क्वेरी को निकटतम काले नोड की आईडी लौटानी हो तो क्या होगा?

(distance, nodeId) संग्रहीत करें और लेक्सिकोग्राफ़िक रूप से तुलना करें। जब दूरियां बराबर हों तो यह एक नियतात्मक (deterministic) आईडी देता है; क्वेरी सर्वोत्तम दूरी और आईडी दोनों रखती है।

केवल u के मूल (parent) सेंट्रॉइड को ही क्यों न बनाए रखें?

निकटतम काला नोड एक अलग चाइल्ड घटक में हो सकता है, जिसका पथ उच्च सेंट्रॉइड पर u से मिलता है। केवल एक पैरेंट की जाँच करने से क्रॉस-कंपोनेंट ऑप्टिमा छूट जाता है, इसलिए पूरी पूर्वज श्रृंखला की आवश्यकता होती है।

हेवी-लाइट डिकम्पोज़िशन कब बेहतर होता है?

सहयोगी पथ समुच्चयों (associative path aggregates), मनमाने दो-शीर्ष पथ क्वेरीज़, या एक ऐसे ब्लैक-सेट ऑपरेशन के लिए इसका उपयोग करें जो "एक शीर्ष से डायनेमिक सेट तक की न्यूनतम दूरी" नहीं है। सेंट्रॉइड डिकम्पोज़िशन तब सबसे मजबूत होता है जब प्रत्येक क्वेरी एक शीर्ष पर केंद्रित होती है और बदलते सेट पर एकत्रित होती है।