प्रॉम्प्ट और संदर्भ
यह लॉग फ़िल्टरिंग, संवेदनशील-शब्द पहचान, या एडिटर हाइलाइटिंग के लिए एक मल्टी-पैटर्न मैचिंग समस्या है। मान लें कि कुल कीवर्ड लंबाई M है और टेक्स्ट की लंबाई N है; प्रत्येक मैच की शुरुआत और कीवर्ड ID रिपोर्ट करें। प्रीप्रोसेसिंग के दौरान डिक्शनरी स्थिर (fixed) रहती है, टेक्स्ट लंबा हो सकता है, और इंटरव्यूअर प्रीप्रोसेसिंग, स्कैन जटिलता (scan complexity), और ओवरलैप हैंडलिंग की अपेक्षा करता है।
इंटरव्यूअर क्या मूल्यांकन करता है
इंटरव्यूअर यह देखना चाहता है कि आप ट्राई प्रीफिक्स शेयरिंग को एक फाइनाइट-स्टेट मशीन में कैसे विस्तारित करते हैं। एक मजबूत उत्तर फेल्योर लिंक्स बनाता है, फेल्योर लिंक्स के माध्यम से आउटपुट इनहेरिट करता है, और समझाता है कि प्रत्येक वर्ण (character) सीमित स्टेट ट्रांज़िशन का कारण क्यों बनता है। एक कमजोर उत्तर केवल "trie का उपयोग करें" कहता है, लेकिन प्रत्यय ओवरलैप (suffix overlap) या मिसमैच फॉलबैक को संभालने में असमर्थ होता है।
पहले पूछे जाने वाले स्पष्टीकरण
- क्या मैचिंग केस-सेंसिटिव है, यूनिकोड-सामान्यीकृत (Unicode-normalized) है, या बाइट-आधारित है? वर्ण की परिभाषा ट्राई और स्थिति की इकाई को बदल देती है।
- क्या ओवरलैप होने वाले मैच और एक ही स्थिति पर समाप्त होने वाले कई कीवर्ड्स को लौटाया जाना चाहिए? यह निर्धारित करता है कि आउटपुट चेन पूरी है या नहीं।
- क्या डिक्शनरी बार-बार बदलती है? एक स्थिर डिक्शनरी एक ऑटोमेटन के अनुकूल होती है; एक डायनेमिक डिक्शनरी को वर्ज़न किए गए पुनर्निर्माण (rebuilds) की आवश्यकता हो सकती है।
- क्या स्थितियां वर्णों, बाइट्स, या UTF-16 कोड यूनिट्स में गिनी जाती हैं? कॉलर के कॉन्ट्रैक्ट से मिलान करें।
- क्या टेक्स्ट चंक्स (chunks) में आता है? क्रॉस-चंक्स स्कैनिंग को प्रत्येक चंक को रीसेट करने के बजाय स्टेट को सुरक्षित रखना चाहिए।
30-सेकंड उत्तर फ्रेमवर्क
"मैं प्रत्येक कीवर्ड को एक ट्राई में सम्मिलित करूंगा, फिर प्रत्येक नोड के लिए एक फेल्योर लिंक बनाने के लिए BFS का उपयोग करूंगा: मिसमैच के बाद सबसे लंबा उपयोग करने योग्य प्रत्यय। प्रत्येक नोड अपने स्वयं के टर्मिनल आउटपुट को अपने फेल्योर टारगेट के आउटपुट के साथ जोड़ता है। स्कैनिंग के दौरान, ट्रांज़िशन या फेल्योर लिंक्स का अनुसरण करें और वर्तमान नोड के आउटपुट उत्सर्जित (emit) करें। प्रीप्रोसेसिंग कुल कीवर्ड लंबाई और एज रिप्रेजेंटेशन में लीनियर है; स्कैनिंग O(N + matches) है, और चंक्ड इनपुट को केवल वर्तमान ऑटोमेटन स्टेट की आवश्यकता होती है।"
चरण-दर-चरण गहन उत्तर
- ट्राई का निर्माण करें। प्रत्येक नोड चाइल्ड एजेस, एक फेल्योर लिंक और कीवर्ड IDs संग्रहीत करता है। एक टर्मिनल नोड एक ID जोड़ता है; इसे केवल एक ही ID नहीं रखनी चाहिए।
- फेल्योर आरंभ करें। रूट के प्रत्यक्ष चाइल्ड रूट पर फ़ेल होते हैं। शेष नोड्स को एक कतार (queue) के साथ गहराई (depth) के अनुसार प्रोसेस करें।
- फॉलबैक ट्रांज़िशन की गणना करें। किसी नोड से निकलने वाले एज के लिए, पैरेंट के फेल्योर लिंक्स का तब तक अनुसरण करें जब तक कि वही वर्ण एज न मिल जाए; अन्यथा रूट पर लौटें। इसके बाद स्कैनिंग कभी भी पहले के टेक्स्ट वर्णों की दोबारा तुलना नहीं करती है।
- आउटपुट एकत्रित करें। फेल्योर टारगेट से आउटपुट कॉपी करें या सूचियों को कॉपी करने से बचने के लिए आउटपुट लिंक स्टोर करें; मैच रिपोर्ट करते समय आउटपुट लिंक को पार (traverse) किया जाता है।
- टेक्स्ट स्कैन करें। प्रत्येक वर्ण के लिए चाइल्ड एज का प्रयास करें। मिसमैच होने पर, फेल्योर लिंक्स का अनुसरण तब तक करें जब तक कोई एज या रूट न मिल जाए। नए नोड पर प्रत्येक आउटपुट उत्सर्जित करें; प्रारंभ सूचकांक (start) वर्तमान इंडेक्स माइनस कीवर्ड लंबाई प्लस एक है।
- सीमाओं को संभालें। ओवरलैपिंग कीवर्ड स्वाभाविक रूप से उत्सर्जित होते हैं। चंक्ड इनपुट चंक्स के बीच स्टेट को आगे ले जाता है। यदि मैच बहुत अधिक हैं, तो सभी O(matches) परिणामों को बनाए रखने के बजाय कॉलबैक, कैप (सीमा), या पेजिनेशन का उपयोग करें।
सामान्य वर्णमाला के लिए हैश मैप का उपयोग करें और मेमोरी की अनुमति होने पर एक छोटी निश्चित वर्णमाला के लिए ऐरे का उपयोग करें। बदलती डिक्शनरी के लिए, बैकग्राउंड में एक नया संस्करण बनाएं और रीडर्स को एटॉमिक रूप से स्विच करें ताकि स्कैन कभी भी आंशिक ऑटोमेटन का निरीक्षण न करें।
मॉडल उत्तर
"मैं सभी कीवर्ड्स को सम्मिलित करूंगा और प्रत्येक टर्मिनल ID रिकॉर्ड करूंगा, फिर BFS के माध्यम से फेल्योर लिंक्स बनाऊंगा। रूट के चाइल्ड रूट पर फ़ेल होते हैं। अन्य एजेस के लिए, उसी ट्रांज़िशन को खोजने के लिए पैरेंट की फेल्योर चेन का अनुसरण करें या रूट पर वापस आएं। आउटपुट में नोड के अपने टर्मिनल IDs और फेल्योर आउटपुट शामिल होते हैं, इसलिए she को स्कैन करते समय he और she दोनों उत्सर्जित होते हैं। प्रत्येक टेक्स्ट वर्ण चाइल्ड या फेल्योर ट्रांज़िशन का अनुसरण करता है, जिससे O(N + Z) स्कैन समय मिलता है जहां Z मैचों की संख्या है; प्रीप्रोसेसिंग O(M) प्लस एज स्टोरेज है। चंक्ड टेक्स्ट स्टेट को सुरक्षित रखता है, और डिक्शनरी अपडेट स्विच करने से पहले एक नया संस्करण बनाते हैं।"
सामान्य गलतियाँ
- गलती: मिसमैच पर पॉइंटर और टेक्स्ट दोनों को पीछे ले जाना → यह क्यों विफल होता है: यह प्रत्येक कीवर्ड के लिए फिर से स्कैन करने में बदल जाता है → समाधान: फेल्योर लिंक्स टेक्स्ट इंडेक्स को मोनोटोनिक (monotonic) रखते हैं।
- गलती: प्रति नोड केवल एक आउटपुट रखना → यह क्यों विफल होता है: प्रत्यय कीवर्ड और साझा एंडपॉइंट्स गायब हो जाते हैं → समाधान: फेल्योर आउटपुट को मर्ज करें या आउटपुट लिंक्स बनाए रखें।
- गलती: यह दावा करना कि स्कैनिंग हमेशा O(N) होती है → यह क्यों विफल होता है: मैचों की रिपोर्टिंग में ही O(Z) की लागत आ सकती है → समाधान: O(N + Z) बताएं और आउटपुट को स्ट्रीम करें।
- गलती: प्रत्येक चंक पर रूट पर रीसेट करना → यह क्यों विफल होता है: चंक्स में फैले कीवर्ड मैच नहीं हो सकते → समाधान: ऑटोमेटन स्टेट को चंक्स के बीच आगे ले जाएं।
फॉलो-अप प्रश्न और उत्तर
प्रत्येक कीवर्ड के लिए अलग से KMP क्यों न चलाएं?
अलग-अलग KMP चलाने के लिए O(KN) टेक्स्ट स्कैन की आवश्यकता होती है। Aho–Corasick ट्राई प्रीफिक्स साझा करता है और टेक्स्ट को एक बार प्रोसेस करता है, जो एक निश्चित डिक्शनरी और लंबे टेक्स्ट के लिए उपयुक्त है।
फेल्योर लिंक्स हर मैच को क्यों ढूंढ लेते हैं?
वे सबसे लंबे उपयोग करने योग्य प्रत्यय की ओर संकेत करते हैं। फेल्योर चेन के साथ आगे बढ़ना प्रत्येक प्रत्यय की गणना करता है जो एक कीवर्ड प्रीफिक्स भी है, इसलिए आउटपुट एग्रीगेशन नेस्टेड और ओवरलैपिंग मैचों को ढूंढता है।
क्या होगा यदि चाइल्ड हैश मैप्स मेमोरी समाप्त कर दें?
एक छोटी वर्णमाला के लिए ऐरे, कॉम्पैक्ट एज टेबल, या एक डबल-ऐरे ट्राई चुनें, और सूचियों की प्रतिलिपि बनाने से बचने के लिए आउटपुट लिंक्स का उपयोग करें। कंप्रेस करने से पहले नोड और एज काउंट को मापें।
क्या डिक्शनरी बार-बार बदल सकती है?
डिक्शनरी का वर्ज़न बनाएं, बैकग्राउंड में एक नया ऑटोमेटन बनाएं, इसे सत्यापित करें, और रीडर पॉइंटर को एटॉमिक रूप से बदलें। पहले से प्रगति पर मौजूद स्ट्रीम्स के लिए पुराने संस्करण को कुछ समय के लिए बनाए रखें।