की मैट्रिक्स में शब्द कैसे मिल सकता है यह एक और सवाल मैं टेलीफोन पर साक्षात्कार में कहा गया था है पहेलीमैं पत्र
सब मुझे लगता है कि हश शब्दकोश था, क्रॉसवर्ड में हर संभव शब्द ढूंढें और हैश खोजें। मैं इसे सब अनुकूलित नहीं कर सका।
स्वीकार करना होगा माइक्रोसॉफ्ट साक्षात्कार प्रश्न कठिन :(
मुझे तर्ज पर सोचने के लिए दे रहे हैं
कैसे के बारे में:।
मुझे नहीं लगता कि हैश यहां एक बहुत ही उपयोगी अनुकूलन होगा।
लेकिन सवाल आपको एक शब्दकोश का उपयोग करने के लिए कहता है। रचनात्मकता के लिए +1 – mustafabar
हां, और उसने एक शब्दकोश का उपयोग किया। इससे एक खोज पेड़ बनाने के लिए :) +1 –
खोज पेड़ को परिभाषित करें? किस प्रकार? – marcog
मान लीजिए शब्दकोश औसत लंबाई कश्मीर की n शब्द हैं, और मैट्रिक्स मीटर ² वर्ण हैं।
कुल समय: हे (अधिकतम (के.एन., मीटर ³))
यथार्थवादी शब्द-खोज में, मैट्रिक्स में शब्द की औसत लंबाई अधिक की तरह कश्मीर की तरह से मीटर है, इसलिए समय लिया हे होगा (कश्मीर अधिकतम (n, मीटर ²))।
प्रत्यय पेड़ तेजी से लुकअप पैदा करते हैं। मेरा जवाब देखें – marcog
@marcog, चूंकि कई मामलों में हम पिछली बार देखे गए एक शब्द से अधिक एक शब्द देख रहे हैं, लुकअप समय संभवतः उपसर्ग प्रयासों के लिए 'औसत' से बेहतर है। मुझे यकीन नहीं है कि इसके असम्बद्ध व्यवहार क्या है। –
क्या आप खोज के काम के बारे में थोड़ा और विवरण दे सकते हैं? मैं बिल्कुल नहीं देख सकता कि कैसे क्रॉसवर्ड खोज को कुशल प्रत्यय वृक्ष संचालन में से एक में बदलना है। –
आपके उत्तर में क्या गलत था?
एक शब्दकोश क्रमबद्ध हो जाता है तो मुझे लगता है मैं एक prefix trie में शब्दों को शब्दकोश की व्यवस्था चाहते हैं। इससे मदद मिलेगी क्योंकि शायद ऐसे कई शब्द हैं जहां उपसर्ग भी एक शब्द है। सॉर्टिंग बिल्ड समय के साथ (न्यूनतम) मदद करता है।
फिर सभी संभावित शब्दों को देखकर क्रॉसवर्ड पर चलें।जैसे ही आप एक संभावित शब्द के पात्रों को निकालते हैं, आप त्रिभुज पर चल रहे हैं - इसलिए आपको अक्षर के एक निश्चित सेट से शुरू होने वाला पहला शब्द मिल जाएगा, लेकिन साथ ही साथ शुरू होने वाले दूसरे शब्दों को ढूंढने के लिए सही जगह पर भी जाना चाहिए पात्र
सबसे उपयुक्त समाधान उन बाधाओं पर निर्भर करता है जिनसे आप अपेक्षा कर सकते हैं। आपका शब्दकोश कितना बड़ा है? आपका क्रॉसवर्ड कितना बड़ा है।
मैं Suffix trees पर एक नज़र डालने का सुझाव दूंगा। आप सभी शब्दकोष शब्दों को एक में सम्मिलित कर सकते हैं। फिर पंक्तियों, स्तंभों और विकर्णों के लिए प्रत्यय पेड़ की खोज करें। पंक्तियों के लिए, प्रत्येक पंक्ति में पहले अक्षर के लिए पेड़ की जड़ से एक खोज शुरू करें और जब आप पंक्ति से गुजरते हैं तो पेड़ के माध्यम से फिर से शुरू करें। यदि आवश्यक हो तो दाएं से बाएं से वही करें। कॉलम और विकर्णों के लिए इसी तरह की कहानी।
वृक्ष निर्माण ओ (एन) है और ओ (एन) अंतरिक्ष का उपभोग करता है, जहां एन वर्णों में आपके शब्दकोश का आकार है। खोज तब ओ (पीक्यू) समय लेगा, जहां आपका क्रॉसवर्ड आकार PxQ का आकार है। ओ (एन + पीक्यू) और ओ (एन) की एक समग्र रनटाइम देना।
बात यह है कि, प्रत्यय पेड़ लागू करने के लिए एक दर्द है। वे वास्तव में हैं। तो तुम एक साधारण Trie, जो आप हे की कुल क्रम (N + पीक्यू (अधिकतम (पी, क्यू)) दे देंगे के लिए बसने से पसंद कर सकते हैं।
क्या आप कृपया मुझे बता सकते हैं कि आपने एम्सटोटिक रनटाइम कैसे प्राप्त किया? – Edward
विकी लेखों की जांच करें, वे पेड़ों के लिए रनटाइम की व्याख्या करते हैं। प्रत्यय वृक्ष खोज के लिए, प्रत्येक पंक्ति/कॉलम/विकर्ण के लिए आप प्रति चरित्र एक प्रश्न करते हैं क्योंकि यह गतिशील रूप से एक नए आंशिक शब्द के लिए बहुत कुशलता से लपेटता है - जो 3 पीक्यू है, इसलिए ओ (पीक्यू)। प्रयासों के लिए, आपको प्रत्येक 6 दिशाओं में से प्रत्येक के लिए त्रिभुज को खोजना शुरू करना होगा। चूंकि पीक्यू वर्ण हैं, और एक शब्द लंबाई में सबसे खराब अधिकतम (पी, क्यू) हो सकता है, आपके पास 6 पीक्यू (अधिकतम (पी, क्यू) है) इसलिए पीक्यू (अधिकतम (पी, क्यू))। – marcog
यह सवाल वास्तव में कैसे एक बौगल अदा कर सकता है।
अतः पर्याप्त रूप से ज्यादा ANSWERS THIS QUESTION में यह पिछले सवाल।
मज़े ...
असली अच्छी खोज! –
मैं एक DFA शब्दकोश में शब्द स्वीकार करता है कि में शब्दकोश संकलन होता है, तो यह पंक्तियों और स्तंभों और विकर्णों पर चलाया पत्र मैट्रिक्स का।होना चाहिएजहां m अक्षरों में शब्दकोश की लंबाई है और n मैट्रिक्स का क्षेत्र (डब्ल्यू * एच) है।
एक हैश? तुम्हारा मतलब हैश ट्राई? –
बाधाएं क्या हैं - क्या प्रत्येक चरित्र को क्रॉसवर्ड में पिछले के समीप होना चाहिए? – Andy
इग्नियो: मेरा मतलब सामान्य हैश टेबल था। – Edward