ऑक्सफोर्ड इंग्लिश डिक्शनरी

Question

मैं एक साक्षात्कार कैसे मैं ऑक्सफोर्ड इंग्लिश डिक्शनरी डिजाइन हैं में कहा गया था डिजाइनिंग।

मैंने उससे कहा कि मैं एक पेड़ डेटा संरचना का उपयोग करते हैं, लेकिन उन्होंने जवाब दिया कि यह स्मृति का एक बहुत ले जाएगा। तो कौन सी अन्य डेटा संरचना का उपयोग किया जाना चाहिए?

Answer 1

एक डेटा संरचना मैंने सुना T9 शब्दकोशों के भंडारण के लिए मोबाइल फोन में अतीत में इस्तेमाल किया गया था है निम्नलिखित (अच्छी तरह से, यह केवल प्रमुख मुद्दे को संबोधित नहीं, बल्कि परिभाषा संग्रहण):

प्रविष्टियां हल कर रहे हैं, और प्रत्येक प्रविष्टि को पिछली प्रविष्टि में ऑफ़सेट के साथ शुरू करना चाहिए जहां से इसे जारी रखा जाना चाहिए, और निरंतरता भी। उदाहरण के लिए:

apple 
4icable 
7tion 

सेब, लागू, एप्लिकेशन को डीकोड करेगा। हालांकि इस विलय श्रृंखला के साथ की कोशिश करता से अलग नहीं हो सकता है, को देखने के

appl -> e 
    -> ica -> ble 
      -> tion 

विकिपीडिया Directed acyclic word graph पर्दाफाश किया है, जो पेड़ है कि यह न केवल शाखाओं, लेकिन शाखाओं विलय कर सकते हैं, जहां शब्द ही प्रत्यय है से अलग है। यह वास्तव में एक बेहतर भंडारण हो सकता है।

 a 
    /\ 
    pplic utom 
     \/
     ation 

Answer 2

यह स्मृति का एक बहुत का उपयोग नहीं होता। आपका जवाब ठीक था। शायद 1 99 5 में। अपने आप को भाग्यशाली मानें।

Answer 3

के रूप में अन्य लोगों, का उल्लेख किया है अगर वहाँ पर्याप्त छत एक अच्छी तरह से डिजाइन trie के लिए नहीं है, वहाँ शायद नहीं सूचकांक के किसी भी अन्य प्रकार के लिए कमरे, या तो है। चूंकि यह एक साक्षात्कार प्रश्न के बारे में है, यह लग रहा है जैसे वह बी पेड़ की तरह क्लासिक आउट-ऑफ-कोर datastructures की ओर चलाने की कोशिश कर रहा था।

वैकल्पिक रूप से, अधिक जानकारी के लिए एक अच्छी प्रतिक्रिया हो सकती है, जैसे कि "इस डेटास्ट्रक्चर पर आप किस प्रकार के संचालन करना चाहते हैं, और आपको किस तरह के प्रदर्शन की आवश्यकता है?" तुम सिर्फ एक वर्तनी जाँच चाहते हैं, तो एक ब्लूम फिल्टर सबसे कारगर "आंकड़ा संरचना" ...