समस्या और संदर्भ
एक स्ट्रीम s[0..n) दी गई है, जिसमें एक समय में एक कैरेक्टर अपेंड किया जाता है। प्रत्येक अपेंड के बाद, विशिष्ट पैलिंड्रोमिक सबस्ट्रिंग्स की संख्या, प्रत्येक पैलिंड्रोम के लिए ऑकरेंस काउंट, और वर्तमान प्रीफिक्स का सबसे लंबा पैलिंड्रोमिक सफिक्स बनाए रखें। समाधान प्रत्येक अपेंड के बाद सभी सबस्ट्रिंग्स को फिर से गिनने के बजाय ऑनलाइन होना चाहिए।
एक eertree (पैलिंड्रोमिक ट्री) प्रत्येक विशिष्ट पैलिंड्रोम के लिए एक नोड संग्रहीत करता है। एजेस दोनों सिरों पर समान कैरेक्टर जोड़ते हैं, जबकि एक सफिक्स लिंक सबसे लंबे प्रॉपर पैलिंड्रोमिक सफिक्स को इंगित करता है। एक उत्कृष्ट उत्तर दो सेंटिनल रूट्स, एक एक्सटेंडेबल सफिक्स कैसे खोजा जाता है, और प्रति स्थिति अधिकतम एक नोड क्यों बनाया जाता है, इसकी व्याख्या करता है।
इंटरव्यूअर क्या मूल्यांकन करता है
- लंबाई
-1और लंबाई0रूट्स को सही ढंग से अलग करना। last, सबसे लंबे पैलिंड्रोमिक सफिक्स और सफिक्स लिंक्स को समझना।- अपेंड के दौरान एक एक्सटेंडेबल नोड ढूंढना और एक ट्रांज़िशन बनाना।
- अपेंड मॉडल के तहत
O(n)नोड, समय और स्पेस बाउंड्स को जानना। - दोहराए गए कैरेक्टर्स, खाली स्ट्रिंग, अल्फाबेट रिप्रेजेंटेशन और काउंट प्रोपेगेशन को संभालना।
- स्ट्रक्चर को पैलिंड्रोम पार्टिशनिंग या स्लाइडिंग-विंडो वेरिएंट्स तक विस्तारित करना।
पहले पूछे जाने वाले स्पष्टीकरण
- क्या इनपुट एक बार में दी जाने वाली स्ट्रिंग है या केवल दाईं ओर अपेंड होने वाला स्ट्रीम है? क्या बाईं ओर से डिलीट करना आवश्यक है?
- क्या ऑकरेंस को अंतिम स्थिति द्वारा गिना जाना चाहिए या अंतिम कुल फ्रीक्वेंसी के रूप में?
- क्या अल्फाबेट लोअरकेस, यूनिकोड, या मनमाने पूर्णांक टोकन हैं?
- क्या आउटपुट में पैलिंड्रोम टेक्स्ट, एक नोड आईडी, या केवल लंबाई और काउंट्स शामिल होने चाहिए?
- क्या ऑनलाइन मिनिमम कट्स आवश्यक हैं, या केवल विशिष्ट-पैलिंड्रोम सेट को बनाए रखना पर्याप्त है?
30-सेकंड उत्तर फ्रेमवर्क
मैं दो रूट्स का उपयोग करता हूं: लंबाई -1 और लंबाई 0। प्रत्येक सामान्य नोड अपनी पैलिंड्रोम लंबाई, सबसे लंबे प्रॉपर पैलिंड्रोमिक सफिक्स के लिए एक सफिक्स लिंक, और कैरेक्टर ट्रांज़िशन्स संग्रहीत करता है। last वर्तमान प्रीफिक्स का सबसे लंबा पैलिंड्रोमिक सफिक्स है। जब कैरेक्टर c आता है, तो मैं सफिक्स लिंक्स का अनुसरण तब तक करता हूं जब तक कि दोनों सिरों को c द्वारा लपेटा (wrap) न जा सके; मैं मौजूदा ट्रांज़िशन का पुन: उपयोग करता हूं या एक नया बनाता हूं, फिर लिंक चेन से नए नोड के सफिक्स लिंक की गणना करता हूं। प्रति स्थिति अधिकतम एक विशिष्ट नोड जोड़ा जा सकता है, इसलिए निर्माण O(n) है, और रिवर्स सफिक्स-लिंक क्रम में ऑकरेंस काउंट्स को प्रोपेगेट करने से अंतिम फ्रीक्वेंसी मिलती हैं।
चरण-दर-चरण गहन विश्लेषण
1. दो रूट्स और नोड फील्ड्स
विषम रूट की लंबाई -1 होती है, जो एक सेंटिनल के रूप में कार्य करता है जिसे किसी भी कैरेक्टर द्वारा बढ़ाया जा सकता है। सम रूट की लंबाई 0 होती है और यह खाली पैलिंड्रोम का प्रतिनिधित्व करता है। सामान्य नोड्स len, link, next, occ, और वैकल्पिक रूप से एक अंतिम स्थिति संग्रहीत करते हैं। last सम रूट से शुरू होता है।
2. एक एक्सटेंडेबल सफिक्स खोजें
स्थिति pos पर c अपेंड करने के बाद, last से शुरू करें और परीक्षण करें कि क्या नोड के पैलिंड्रोम से ठीक पहले का कैरेक्टर c के बराबर है। यदि नहीं, तो v = link[v] सेट करें और जारी रखें। पहला मैच सबसे लंबा पैलिंड्रोमिक सफिक्स होता है जिसे बढ़ाया जा सकता है।
while s[pos - 1 - len[v]] != c:
v = link[v]कार्यान्वयन आमतौर पर अल्फाबेट के बाहर एक सेंटिनल को शुरुआत में जोड़ते हैं ताकि विषम-रूट जांच कभी भी ऋणात्मक इंडेक्स न पढ़े।
3. एक ट्रांज़िशन और नोड जोड़ें
यदि next[v][c] पहले से मौजूद है, तो यह नया last बन जाता है और इसका occ बढ़ जाता है। अन्यथा लंबाई len[v] + 2 का एक नोड बनाएं और ट्रांज़िशन असाइन करें। लंबाई-एक का नोड सीधे सम रूट से लिंक होता है। लंबे नोड्स के लिए, link[v] का तब तक अनुसरण करें जब तक कि c पर संबंधित ट्रांज़िशन न मिल जाए।
4. केवल एक नोड क्यों जोड़ा जाता है
एक अपेंड द्वारा नया बनाया गया प्रत्येक पैलिंड्रोम नए कैरेक्टर पर समाप्त होना चाहिए। केवल ऐसा सबसे लंबा पैलिंड्रोम ही नया होता है; इसके छोटे पैलिंड्रोमिक सफिक्स पहले से ही सफिक्स-लिंक चेन पर मौजूद होते हैं। इसलिए प्रत्येक स्थिति अधिकतम एक विशिष्ट नोड बनाती है, जिससे कुल संख्या अधिकतम n + 2 बनी रहती है।
5. ऑकरेंस काउंट्स प्रोपेगेट करें
ऑनलाइन पास के दौरान, प्रत्येक स्थिति पर समाप्त होने वाले सबसे लंबे पैलिंड्रोमिक सफिक्स के लिए occ को बढ़ाएं। इनपुट समाप्त होने के बाद, नोड्स को लंबे से छोटे क्रम में प्रोसेस करें और occ[v] को occ[link[v]] में जोड़ें। यह प्रत्येक ऑकरेंस को उसके सभी पैलिंड्रोमिक सफिक्स में स्थानांतरित करता है। केवल विशिष्ट काउंट के लिए, सामान्य नोड्स की संख्या लौटाएं।
6. पैलिंड्रोम पार्टिशनिंग तक विस्तारित करें
न्यूनतम पैलिंड्रोम कट्स के लिए, last सफिक्स-लिंक चेन पर चलकर प्रत्येक स्थिति पर समाप्त होने वाले पैलिंड्रोम की गणना करें और dp[pos] = min(dp[pos - len[v]] + 1) को अपडेट करें। एक सरल चेन वॉक O(n^2) बन सकता है। सीरीज़ लिंक्स समान लंबाई-अंतर वाले रन्स को समूहित कर सकते हैं, लेकिन इस ऑप्टिमाइज़ेशन को सीमाओं की पुष्टि करने के बाद ही चुना जाना चाहिए।
7. बाउंड्रीज़, अल्फाबेट और कॉम्प्लेक्सिटी
खाली इनपुट में केवल दो रूट्स होते हैं। दोहराए गए कैरेक्टर्स ट्रांज़िशन्स का पुन: उपयोग करते हैं और उन्हें डुप्लिकेट नोड्स नहीं बनाने चाहिए। एक छोटा अल्फाबेट O(n * alphabet) ट्रांज़िशन स्टोरेज के साथ फिक्स्ड एरेज़ का उपयोग कर सकता है; एक बड़े अल्फाबेट के लिए हैश मैप या ऑर्डर्ड मैप की आवश्यकता होती है, जो अपेक्षित O(n) या O(n log σ) व्यवहार देता है। केवल दाईं ओर अपेंड के तहत, अपेक्षित स्थिर-समय हैश ट्रांज़िशन्स के साथ निर्माण O(n) है, और स्पेस O(n) प्लस ट्रांज़िशन स्टोरेज है।
उच्च-गुणवत्ता वाला मॉडल उत्तर
मैं पहले केवल दाईं ओर अपेंड, अल्फाबेट, और ऑकरेंस काउंट के अर्थ की पुष्टि करूंगा। संरचना में लंबाई -1 और 0 रूट्स हैं; सामान्य नोड्स विशिष्ट पैलिंड्रोम का प्रतिनिधित्व करते हैं, और last वर्तमान प्रीफिक्स का सबसे लंबा पैलिंड्रोमिक सफिक्स है। प्रत्येक अपेंड किए गए c के लिए, मैं सबसे लंबे नोड तक सफिक्स लिंक्स का अनुसरण करता हूं जो c के दोनों ओर लपेट सकता है। यदि इसका ट्रांज़िशन अनुपस्थित है, तो मैं लंबाई len + 2 का एक नोड बनाता हूं; लंबाई-एक का नोड सम रूट से लिंक होता है, जबकि लंबे नोड्स पैरेंट की सफिक्स-लिंक चेन के माध्यम से अपना लिंक पाते हैं। प्रति स्थिति अधिकतम एक नोड बनाया जाता है, इसलिए निर्माण रैखिक है। प्रत्येक last को रिकॉर्ड करना और लंबे नोड्स से उनके लिंक्स पर काउंट्स को प्रोपेगेट करना कुल फ्रीक्वेंसी देता है। बाईं ओर से डिलीट करना, मनमाना इंसर्शन, या एक बड़े अल्फाबेट के लिए संरचना और कॉम्प्लेक्सिटी पर फिर से विचार करने की आवश्यकता होती है।
सामान्य गलतियाँ
- एक खाली रूट का उपयोग करना → विषम और सम बाउंड्रीज़ जटिल हो जाती हैं →
-1और0दोनों रूट्स को बनाए रखें। - प्रत्येक अपेंड के लिए रूट से पुनरारंभ करना → ऑनलाइन लीनियर प्रॉपर्टी खो देता है →
lastसे सफिक्स लिंक्स का अनुसरण करें। lastको कहीं भी मौजूद सबसे लंबे पैलिंड्रोम के रूप में मानना → यह केवल सबसे लंबा पैलिंड्रोमिक सफिक्स है।- एक नए नोड को उसके पैरेंट से लिंक करना → लिंक को सबसे लंबे प्रॉपर पैलिंड्रोमिक सफिक्स को लक्षित करना चाहिए।
- प्रत्येक अपेंड पर प्रत्येक पैलिंड्रोम को बढ़ाना → डुप्लिकेट काउंटिंग होती है → एंडिंग नोड्स रिकॉर्ड करें और रिवर्स लिंक क्रम में प्रोपेगेट करें।
- मनमाने यूनिकोड पर एक छोटा फिक्स्ड एरे लागू करना → कोलिज़न या ओवरफ्लो → एन्कोडिंग और मैपिंग को स्पष्ट रूप से परिभाषित करें।
फॉलो-अप्स और प्रतिक्रियाएं
इसके बजाय आप Manacher को कब चुनेंगे?
Manacher एक स्थिर स्ट्रिंग के लिए उपयुक्त है जब एकमात्र आवश्यकता प्रत्येक केंद्र पर सबसे लंबा रेडियस होती है। एक eertree प्रत्येक विशिष्ट पैलिंड्रोम का प्रतिनिधित्व करता है और स्वाभाविक रूप से ऑनलाइन अपेंड्स, नोड-स्तरीय काउंट्स और सफिक्स-लिंक प्रश्नों का समर्थन करता है।
आप वर्तमान सबसे लंबे पैलिंड्रोम टेक्स्ट को कैसे लौटाते हैं?
प्रत्येक नोड पर एक अंतिम स्थिति संग्रहीत करें। उस स्थिति और len की जोड़ी बनाए रखे गए इनपुट में एक स्लाइस की पहचान करती है। इनपुट को डिस्कार्ड करने वाले स्ट्रीम को रिंग बफर या बाहरी स्टोरेज की आवश्यकता होती है।
काउंट्स को रिवर्स क्रम में क्यों प्रोपेगेट करते हैं?
लंबे पैलिंड्रोम की प्रत्येक ऑकरेंस उसके लिंक पाथ पर प्रत्येक पैलिंड्रोमिक सफिक्स की भी एक ऑकरेंस होती है। पहले लंबे नोड्स को प्रोसेस करना यह सुनिश्चित करता है कि पैरेंट में जोड़े जाने से पहले प्रत्येक चाइल्ड का योगदान पूरा हो।
क्या संरचना बाईं ओर से डिलीट कर सकती है?
सामान्य eertree केवल दाईं ओर अपेंड का समर्थन करता है। एक स्लाइडिंग विंडो को डबल-एंडेड वेरिएंट या रीबिल्डिंग/ब्लॉकिंग की आवश्यकता होती है; चुनाव विंडो के आकार और डिलीशन रेट पर निर्भर करता है।
हैश-मैप ट्रांज़िशन्स के साथ क्या बदलता है?
हैश मैप्स अपेक्षित O(1) ट्रांज़िशन लुकअप और अपेक्षित O(n) निर्माण देते हैं। सबसे खराब स्थिति का व्यवहार हैश कार्यान्वयन पर निर्भर करता है। ऑर्डर्ड मैप्स O(log σ) कारक के साथ नियतात्मक (deterministic) बाउंड्स प्रदान करते हैं।