Insert, Search, Prefix और Delete के साथ एक Trie लागू करें

प्रांप्ट और लागू संदर्भ

चार ऑपरेशनों के साथ शब्दों के एक सेट को संग्रहीत करने वाला एक Trie लागू करें:

• insert(word) एक शब्द जोड़ता है और जब शब्द पहले से मौजूद होता है तो यह निष्क्रिय (idempotent) होता है।
• search(word) लौटाता है कि क्या वह पूरा शब्द संग्रहीत है।
• startsWith(prefix) लौटाता है कि क्या वह उपसर्ग पथ मौजूद है; एक गैर-रिक्त उपसर्ग के लिए, इसका मतलब है कि कम से कम एक संग्रहीत शब्द में यह है।
• delete(word) पूरे शब्द को हटा देता है और लौटाता है कि क्या वह मौजूद था।

मान लें कि insert, search, और delete गैर-रिक्त लोअरकेस अंग्रेजी शब्द प्राप्त करते हैं। startsWith खाली उपसर्ग को भी स्वीकार करता है, जो true लौटाता है क्योंकि यह API रूट पथ को किसी भी प्रविष्टि से पहले भी खाली उपसर्ग के रूप में परिभाषित करता है। कार्यान्वयन मेमोरी में, सिंगल-थ्रेडेड है, और सुझावों की गणना नहीं करता है, परिणामों को रैंक नहीं करता है, डेटा को स्थिर (persist) नहीं करता है, या यूनिकोड को सामान्यीकृत (normalize) नहीं करता है। इनपुट सत्यापन क्लास के बाहर स्थित है।

यह सॉफ्टवेयर इंजीनियरिंग भूमिकाओं के लिए एक प्रतिनिधि कोडिंग-इंटरव्यू समस्या है। मुख्य कार्य साझा उपसर्गों को मॉडल करना और "यह पथ मौजूद है" को "एक शब्द यहाँ समाप्त होता है" से अलग करना है। विलोपन (deletion) जोड़ना यह उजागर करता है कि क्या उम्मीदवार वास्तव में उस मॉडल को समझता है: app को हटाने पर apple सुरक्षित रहना चाहिए, जबकि अंतिम विशिष्ट प्रत्यय को हटाने पर उसके नोड्स को पुनः प्राप्त किया जा सकता है।

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

पहला संकेत ऑपरेशनों से संरचना प्राप्त करना है। एक हैश सेट सटीक सदस्यता को संभालता है, लेकिन एक उपसर्ग क्वेरी को संग्रहीत शब्दों का निरीक्षण करने या किसी अन्य इंडेक्स को बनाए रखने की आवश्यकता होगी। एक Trie प्रत्येक उपसर्ग को रूट से एक पथ बनाता है, इसलिए क्वेरी लागत संग्रहीत शब्दों की संख्या के बजाय इनपुट लंबाई पर निर्भर करती है।

दूसरा संकेत टर्मिनल मार्कर है। apple डालने के बाद app के लिए पथ मौजूद है, लेकिन search("app") तब तक false रहता है जब तक कि उस नोड को एक पूर्ण शब्द के रूप में चिह्नित नहीं किया जाता है। startsWith("app") को केवल पथ की आवश्यकता होती है। एक ट्रैवर्सल हेल्पर दोनों ऑपरेशनों की सेवा कर सकता है जबकि उनकी अंतिम स्थितियां अलग रहती हैं।

तीसरा संकेत विलोपन सुरक्षा है। तार्किक विलोपन (logical deletion) के लिए टर्मिनल मार्कर को हटाना पर्याप्त है। भौतिक प्रूनिंग (physical pruning) वैकल्पिक है और केवल तभी ऊपर की ओर बढ़ सकती है जब चाइल्ड गैर-टर्मिनल और चाइल्डलेस हो। यह नियम हटाए गए पथ को साझा करने वाले लंबे शब्दों और छोटे शब्दों दोनों को सुरक्षित रखता है।

अंत में, साक्षात्कारकर्ता ईमानदार जटिलता और परीक्षणों की तलाश करता है। एक मैप-समर्थित नोड प्रत्येक विरल (sparse) नोड पर 26 चाइल्ड स्लॉट आवंटित करने से बचता है, लेकिन मैप ऑपरेशन उनके भाषा रनटाइम के औसत-प्रदर्शन मान्यताओं का उपयोग करते हैं। विलोपन एक O(L) पथ स्टैक भी रखता है; निरंतर सहायक स्थान का दावा करना कोड का खंडन करेगा।

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

• किन वर्णों की अनुमति है? लोअरकेस a-z 26-स्लॉट ऐरे की अनुमति देता है। यूनिकोड, मिश्रित केस, या एक विरल वर्णमाला मैप का पक्ष लेती है और इसके लिए सामान्यीकरण अनुबंध की आवश्यकता हो सकती है।
• क्या डुप्लिकेट प्रविष्टियों की गणना की जाती है? यह समस्या एक सेट संग्रहीत करती है, इसलिए दूसरी प्रविष्टि निष्क्रिय (idempotent) है। एक मल्टीसेट को टर्मिनल और उपसर्ग काउंटरों की आवश्यकता होगी।
• विलोपन को क्या रिपोर्ट करना चाहिए? यह गायब शब्द के लिए false और केवल तभी true लौटाता है जब एक संग्रहीत पूर्ण शब्द हटा दिया जाता है।
• क्या विलोपन द्वारा नोड्स को पुनः प्राप्त करना आवश्यक है? यहाँ यह सुरक्षित प्रूनिंग करता है। यदि विलोपन दुर्लभ हैं और मेमोरी सीमित नहीं है, तो टर्मिनल मार्कर को हटाना सरल और फिर भी सही है।
• क्या एक खाली शब्द मान्य है? नहीं। खाली उपसर्ग की अनुमति है, लेकिन इस अनुबंध में खाली स्ट्रिंग को शब्द के रूप में सम्मिलित या खोजा नहीं जा सकता है।
• क्या उपसर्ग परिणाम प्रगणित (enumerated) किए गए हैं या केवल पहचाने गए हैं? यह API एक बूलियन लौटाता है। मैचों को सूचीबद्ध करने से सबट्री ट्रैवर्सल और आउटपुट-संवेदनशील लागत जुड़ जाती है।
• क्या समवर्तीता (concurrency) आवश्यक है? नहीं। समवर्ती रीड्स और राइट्स के लिए एक सिंक्रोनाइज़ेशन या इम्यूटेबल-स्नैपशॉट डिज़ाइन की आवश्यकता होगी।

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

"मैं प्रत्येक उपसर्ग को एक रूट से एक पथ के रूप में प्रस्तुत करूँगा। प्रत्येक नोड अगले वर्ण को एक चाइल्ड से मैप करता है और उसमें एक isWord ध्वज होता है। Insert लापता नोड्स बनाता है और अंतिम नोड को चिह्नित करता है। Search पथ पर चलता है और उस ध्वज की जाँच करता है; उपसर्ग खोज के लिए केवल पथ की आवश्यकता होती है। Delete पहले पथ को रिकॉर्ड करता है, अंतिम ध्वज को साफ़ करता है, फिर नोड्स को पीछे की ओर केवल तभी हटाता है जब उनके पास कोई चाइल्ड न हो और वे किसी अन्य शब्द का अंत न हों। मैप-समर्थित बच्चों के साथ प्रत्येक ऑपरेशन अपेक्षित O(L) है, कुल भंडारण O(C) है, और delete O(L) सहायक स्थान का उपयोग करता है।"

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

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

इस इनवेरिएंट का उपयोग करें:

प्रत्येक संग्रहीत शब्द के लिए, उसके वर्ण एक रूट-टू-नोड पथ बनाते हैं, और isWord एक नोड पर बिल्कुल तभी सत्य होता है जब उस नोड की वर्तनी वाला पथ एक संग्रहीत पूर्ण शब्द हो।

इनवेरिएंट सभी ऑपरेशनों की व्याख्या करता है। Insert एक पथ का विस्तार करता है और उसके अंतिम मार्कर को चालू करता है। Search के लिए पथ और मार्कर दोनों की आवश्यकता होती है। Prefix search के लिए केवल पथ की आवश्यकता होती है। Delete ठीक एक मार्कर को बंद कर देता है और केवल तभी एक प्रत्यय को हटाता है जब कोई शेष शब्द इसका उपयोग नहीं कर सकता है।

class TrieNode {
  readonly children = new Map<string, TrieNode>()
  isWord = false
}

class Trie {
  private readonly root = new TrieNode()

  insert(word: string): void {
    let node = this.root

    for (const character of word) {
      let child = node.children.get(character)
      if (!child) {
        child = new TrieNode()
        node.children.set(character, child)
      }
      node = child
    }

    node.isWord = true
  }

  search(word: string): boolean {
    return this.walk(word)?.isWord ?? false
  }

  startsWith(prefix: string): boolean {
    return this.walk(prefix) !== undefined
  }

  delete(word: string): boolean {
    let node = this.root
    const path: Array<[TrieNode, string, TrieNode]> = []

    for (const character of word) {
      const child = node.children.get(character)
      if (!child) return false

      path.push([node, character, child])
      node = child
    }

    if (!node.isWord) return false
    node.isWord = false

    for (let index = path.length - 1; index >= 0; index -= 1) {
      const [parent, character, child] = path[index]
      if (child.isWord || child.children.size > 0) break
      parent.children.delete(character)
    }

    return true
  }

  private walk(text: string): TrieNode | undefined {
    let node = this.root

    for (const character of text) {
      const child = node.children.get(character)
      if (!child) return undefined
      node = child
    }

    return node
  }
}

विलोपन को दो विरोधी उदाहरणों (counterexamples) के साथ सत्यापित करना सबसे आसान है। यदि app और apple संग्रहीत हैं, तो app को हटाने से दूसरे p पर मार्कर साफ़ हो जाता है लेकिन प्रूनिंग बंद हो जाती है क्योंकि उस नोड का चाइल्ड l है। apple खोजने योग्य बना रहता है। यदि app और apt संग्रहीत हैं, तो app को हटाने से केवल अंतिम p हट जाता है; फिर साझा ap नोड पर प्रूनिंग बंद हो जाती है क्योंकि इसमें अभी भी चाइल्ड t है।

शुद्धता गणितीय आगमन (induction) द्वारा सिद्ध होती है। खाली Trie इनवेरिएंट को संतुष्ट करता है। Insert केवल एक पथ और उसके अंतिम मार्कर को बदलता है। Search और prefix search स्थिति को नहीं बदलते हैं। एक सफल delete पहले बिल्कुल लक्षित मार्कर को हटाता है। प्रत्येक काटा गया (pruned) नोड गैर-टर्मिनल और चाइल्डलेस होता है, इसलिए यह किसी संग्रहीत शब्द का प्रतिनिधित्व नहीं कर सकता है या किसी की ओर ले नहीं जा सकता है। इसे हटाने से प्रत्येक शेष संग्रहीत पथ सुरक्षित रहता है; पहले टर्मिनल या ब्रांचिंग नोड पर रुकने से साझा उपसर्ग सुरक्षित रहता है।

मान लें कि L इनपुट लंबाई है और C वर्तमान में आवंटित वर्ण नोड्स की संख्या है। औसत मैप लुकअप के तहत, insert, search, और prefix search अपेक्षित O(L) समय लेते हैं। Delete आगे की ओर ट्रैवर्स करता है और अधिक से अधिक समान L किनारों को काटता है, इसलिए यह अपेक्षित O(L) भी है। Trie O(C) स्थान का उपयोग करता है, जो विशिष्ट संग्रहीत-उपसर्ग वर्णों के योग से सीमित है; delete का पथ O(L) सहायक स्थान का उपयोग करता है।

एक निश्चित लोअरकेस वर्णमाला के लिए, TrieNode | undefined[26] प्रत्यक्ष अनुक्रमित पहुँच और प्रति-वर्ण अनुमानित कार्य प्रदान करता है, लेकिन प्रति नोड 26 संदर्भ सुरक्षित रखता है। एक मैप केवल मौजूदा किनारों को संग्रहीत करता है और हैशिंग और ऑब्जेक्ट ओवरहेड के साथ एक व्यापक वर्णमाला को संभालता है। उत्तर को वर्णमाला और घनत्व के आधार पर चुनना चाहिए, यह दावा नहीं करना चाहिए कि एक प्रतिनिधित्व हमेशा जीतता है।

सत्यापन को केवल एक लुकअप की नहीं, बल्कि स्थिति परिवर्तनों की जाँच करनी चाहिए। startsWith("") === true, search("") === false, और एक खाली Trie से विलोपन के साथ शुरू करें। app, apple, और apt सम्मिलित करें; app को फिर से सम्मिलित करें; search("ap") को startsWith("ap") से अलग करें; apple को संरक्षित करते हुए app को हटाएं; दूसरे विलोपन को अस्वीकार करें; फिर शेष शब्दों को हटाएं और पुष्टि करें कि उनके उपसर्ग गायब हो गए हैं। एक यादृच्छिक परीक्षण सभी ऑपरेशनों की तुलना एक साधारण Set<string> संदर्भ के साथ कर सकता है और उपसर्ग प्रश्नों के लिए सेट को स्कैन कर सकता है।

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

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

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

प्रत्येक Trie नोड अपने आउटगोइंग कैरेक्टर किनारों और एक टर्मिनल ध्वज को संग्रहीत करता है। रूट-टू-नोड पथ एक उपसर्ग है; ध्वज बताता है कि क्या वही पथ एक पूर्ण संग्रहीत शब्द भी है। Insert लापता बच्चों को बनाता है और केवल अंतिम नोड को चिह्नित करता है। Search अंतिम ध्वज की जाँच करता है, जबकि startsWith केवल यह जाँचता है कि क्या ट्रैवर्सल सफल होता है।

Delete के लिए, मैं शब्द पर चलते समय प्रत्येक पैरेंट, एज और चाइल्ड को रिकॉर्ड करता हूँ। यदि पथ गायब है या अंतिम नोड टर्मिनल नहीं है, तो मैं स्थिति बदले बिना false लौटाता हूँ। अन्यथा मैं मार्कर को साफ़ करता हूँ और पीछे की ओर चलता हूँ। मैं एक एज को केवल तभी हटाता हूँ जब उसके चाइल्ड के पास कोई चाइल्ड न हो और वह टर्मिनल न हो, किसी अन्य शब्द द्वारा आवश्यक पहले नोड पर रुकता हूँ। यही वह चीज़ है जो app को हटाते समय apple को बरकरार रखती है।

मैप-समर्थित बच्चों के साथ, सभी ऑपरेशन अपेक्षित O(L) हैं। कुल भंडारण O(C) वर्ण नोड है, और delete एक O(L) पथ स्टैक का उपयोग करता है। मैं खाली और लापता मामलों, डुप्लिकेट प्रविष्टि, एक शब्द जो दूसरे शब्द का उपसर्ग है, दो शब्द जो शाखाबद्ध होते हैं, और अंतिम शब्द को हटाने के बाद पूर्ण प्रूनिंग का परीक्षण करूँगा। यदि सटीक लुकअप एकमात्र ऑपरेशन होता, तो मैं इसके बजाय हैश सेट का उपयोग करता।"

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

• प्रत्येक पहुँच योग्य पथ को एक शब्द मानना → केवल apple डालने के बाद search("app") सत्य हो जाता है → सटीक खोज के लिए isWord की आवश्यकता होती है।
• startsWith को isWord की जाँच करवाना → मान्य उपसर्ग अस्वीकार कर दिए जाते हैं जब तक कि अलग से सम्मिलित न किए जाएं → पथ मौजूद होने पर सफलता लौटाएं।
• विलोपन के दौरान पूरे पथ को साफ़ करना या हटाना → app को हटाने से apple नष्ट हो जाता है → पहले टर्मिनल मार्कर को साफ़ करें और केवल गैर-टर्मिनल पत्तियों को काटें।
• ब्रांचिंग नोड से आगे प्रून करना → एक असंबंधित शब्द जैसे apt गायब हो जाता है → तब रुकें जब चाइल्ड के पास अभी भी बच्चे हों।
• किसी अन्य टर्मिनल नोड से आगे प्रून करना → एक लंबे शब्द को हटाने से उसका छोटा उपसर्ग शब्द हट जाता है → जब चाइल्ड टर्मिनल हो तब रुकें।
• केवल विलोपन पथ मौजूद होने पर true लौटाना → केवल apple डालने के बाद app को हटाना स्थिति को बदल देता है या गलत रिपोर्ट करता है → अंतिम नोड का टर्मिनल होना आवश्यक है।
• डुप्लिकेट प्रविष्टियों को गलती से गिनना → सेट सिमेंटिक्स एक छिपे हुए मल्टीसेट में बदल जाते हैं → एक बूलियन मार्कर का उपयोग करें या स्पष्ट रूप से अनुबंध को काउंटरों में बदलें।
• दावा करना कि सभी चार ऑपरेशन निरंतर समय का उपयोग करते हैं → कार्य इनपुट लंबाई के साथ बढ़ता है → अपेक्षित O(L) और मैप धारणा बताएं।
• दावा करना कि विलोपन किसी अतिरिक्त स्थान का उपयोग नहीं करता है → कार्यान्वयन पिछड़े प्रूनिंग के लिए पथ को संग्रहीत करता है → O(L) सहायक स्थान की रिपोर्ट करें या समान स्टैक सीमा के साथ एक उचित पुनरावर्ती विकल्प का उपयोग करें।
• हमेशा 26 बच्चों को आवंटित करना → विरल या यूनिकोड डेटा स्थान बर्बाद करता है या वर्णमाला अनुबंध को तोड़ता है → वर्ण सेट को स्पष्ट करने के बाद ऐरे बनाम मैप चुनें।
• केवल सटीक लुकअप के लिए Trie का उपयोग करना → नोड ओवरहेड एक उपसर्ग सुविधा खरीदता है जिसका उत्पाद कभी उपयोग नहीं करता है → अकेले सटीक सदस्यता के लिए हैश सेट को प्राथमिकता दें।

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

फॉलो-अप 1: डुप्लिकेट शब्द और इरेज़-वन सिमेंटिक्स डिज़ाइन को कैसे बदलेंगे?

isWord को wordCount से बदलें, और यदि उपसर्ग गणनाओं के बारे में पूछताछ की जाती है तो नोड्स पर prefixCount रखें। Insert पथ के साथ काउंट बढ़ाता है। Erase पहले wordCount > 0 की पुष्टि करता है, उसी पथ को घटाता है, और केवल तभी प्रून करता है जब प्रासंगिक काउंट शून्य तक पहुँच जाती हैं। बूलियन कार्यान्वयन एक प्रविष्टि को पाँच से अलग नहीं कर सकता है।

फॉलो-अप 2: आप शीर्ष K स्वतः पूर्ण (autocomplete) परिणाम कैसे लौटाएंगे?

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

फॉलो-अप 3: यूनिकोड और केस-असंवेदनशील मिलान कैसे काम करेगा?

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

फॉलो-अप 4: आप Trie को थ्रेड-सुरक्षित कैसे बनाएंगे?

संपूर्ण Trie के चारों ओर एक रीड-राइट लॉक सबसे सरल सही उत्तर है: insert और delete राइट लॉक लेते हैं, जबकि search और prefix search रीड लॉक लेते हैं। महीन नोड लॉक के लिए एक निश्चित अधिग्रहण क्रम और प्रूनिंग के सावधानीपूर्वक संरक्षण की आवश्यकता होती है। जब अपडेट कम होते हैं तो अपरिवर्तनीय स्नैपशॉट या कॉपी-ऑन-राइट रूट्स पाठकों को सरल बनाते हैं।

फॉलो-अप 5: क्या होगा यदि मेमोरी सीमित संसाधन है?

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

फॉलो-अप 6: वाइल्डकार्ड या सबसे लंबा-उपसर्ग मिलान ट्रैवर्सल को कैसे बदलेगा?

सबसे लंबा-उपसर्ग मिलान सबसे गहरे टर्मिनल नोड को याद रखते हुए क्वेरी पर चलता है, जो क्वेरी लंबाई में रैखिक रहता है। . जैसा वाइल्डकार्ड उस स्थिति में प्रत्येक चाइल्ड तक शाखाबद्ध होता है, इसलिए सबसे खराब स्थिति वाला कार्य खोजे गए सबट्री के साथ विस्तारित हो सकता है। API को वाइल्डकार्ड सिंटैक्स बताना चाहिए और क्या यह अस्तित्व, एक परिणाम या सभी परिणाम लौटाता है।