गूगल जॉब इंटरव्यू पर्सिंग: रिलेशनशिप ढूंढना

पहेलियों की एक श्रृंखला में अगले लेख में आपका स्वागत है, जो मैंने Google साक्षात्कार में लीक होने के बाद प्रतिबंधित होने से पहले पूछा था। तब से, मैंने Google में एक सॉफ्टवेयर इंजीनियर के रूप में काम करना छोड़ दिया और Reddit में विकास प्रबंधक के पद पर आ गया, लेकिन मेरे पास अभी भी कुछ महान विषय हैं। आज तक, हमने गतिशील प्रोग्रामिंग की जांच की है , जिससे मैट्रिस को शक्ति और प्रश्नों का पर्याय बनाया गया है । इस बार एक बिल्कुल नया सवाल।

लेकिन पहले, दो अंक। सबसे पहले, Reddit में काम बहुत बढ़िया था। पिछले आठ महीनों से, मैंने नए विज्ञापन प्रासंगिकता टीम का निर्माण और नेतृत्व किया है और न्यूयॉर्क में एक नया विकास कार्यालय स्थापित किया है। कोई फर्क नहीं पड़ता कि यह कितना मजेदार हो सकता है, दुर्भाग्य से, मैंने पाया कि हाल ही में जब तक मेरे पास ब्लॉग के लिए समय या ऊर्जा नहीं बची थी। मुझे डर है कि मैंने इस श्रृंखला को थोड़ा छोड़ दिया। देरी के लिए क्षमा करें।

दूसरे, यदि आपने लेखों का अनुसरण किया है, तो अंतिम अंक के बाद आप सोच सकते हैं कि मैं प्रश्नों के पर्यायवाची विकल्पों में खुदाई शुरू करूंगा। हालाँकि मैं कुछ समय के लिए इस पर लौटना चाहूँगा, लेकिन मुझे यह स्वीकार करना होगा कि मैंने काम बदलने के कारण इस समस्या में रुचि खो दी और अब तक मैंने इसे स्थगित करने का फैसला किया। हालाँकि, संपर्क में रहें! मैं मुझ पर एहसान करता हूं, और मैं इसे वापस करने का इरादा रखता हूं। बस, आपको पता है, थोड़ी देर बाद ...

त्वरित अस्वीकरण: हालांकि उम्मीदवारों का साक्षात्कार करना मेरे पेशेवर कर्तव्यों में से एक है, यह ब्लॉग मेरी व्यक्तिगत टिप्पणियों, व्यक्तिगत कहानियों और व्यक्तिगत राय प्रस्तुत करता है। कृपया इसे Google, वर्णमाला, Reddit या किसी अन्य व्यक्ति या संगठन के किसी आधिकारिक बयान के लिए न लें।

एक नए प्रश्न की खोज करें

पिछले लेख में, मैंने अपने पसंदीदा प्रश्नों में से एक का वर्णन किया था जो मैंने अपरिहार्य रिसाव से पहले लंबे समय तक इस्तेमाल किया था। पिछले प्रश्न सैद्धांतिक दृष्टिकोण से आकर्षक थे, लेकिन मैं एक कंपनी के रूप में Google के लिए थोड़ी अधिक प्रासंगिक समस्या का चयन करना चाहता था। जब इस प्रश्न पर प्रतिबंध लगा दिया गया था, तो मैं एक प्रतिबंध को नए प्रतिबंध को ध्यान में रखते हुए खोजना चाहता था: प्रश्न को सरल बनाने के लिए।

अब Google पर बदनाम साक्षात्कार प्रक्रिया को देखते हुए यह थोड़ा आश्चर्यजनक लग सकता है। लेकिन उस समय एक सरल समस्या ने समझ में आया। मेरे तर्क में दो भाग शामिल थे। पहला व्यावहारिक है: उम्मीदवार आमतौर पर कई संकेतों और सरलीकरणों के बावजूद, पिछले प्रश्नों के साथ बहुत अच्छी तरह से सामना नहीं करते थे, और मुझे हमेशा पूरी तरह से यकीन नहीं था कि क्यों। दूसरा सैद्धांतिक एक: साक्षात्कार प्रक्रिया को उम्मीदवारों को "काम पर रखने के लायक" और "काम पर रखने के लायक नहीं" श्रेणियों में विभाजित करना चाहिए, और मैं उत्सुक था कि क्या यह प्रश्न के साथ थोड़ा आसान हो सकता है।

इन दो बिंदुओं को स्पष्ट करने से पहले, मैं इंगित करना चाहता हूं कि उनका क्या मतलब नहीं है। "मुझे हमेशा यकीन नहीं होता कि किसी व्यक्ति को समस्याएं क्यों होती हैं" का अर्थ प्रश्नों की व्यर्थता नहीं है और मैं इस कारण साक्षात्कार को सरल बनाना चाहता था। यहां तक ​​कि सबसे कठिन सवाल, कई अच्छी तरह से नकल करते हैं। मेरा मतलब है, जब उम्मीदवारों को समस्या थी, तो मेरे लिए यह समझना मुश्किल था कि वे क्या गायब थे।

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

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

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

मैंने अत्यधिक जटिल साक्षात्कार प्रश्नों के बारे में शिकायत करते हुए बहुत सारे रेडिट टिप्पणियां पढ़ीं। मैं उत्सुक था अगर एक सरल कार्य के लिए एक योग्य / अयोग्य सिफारिश करना अभी भी संभव था। मुझे संदेह था कि यह उम्मीदवार की नसों को अनावश्यक रूप से चिल्लाए बिना एक उपयोगी संकेत देगा। मैं आपको लेख के अंत में अपने निष्कर्ष के बारे में बताऊंगा ...

इन विचारों के साथ, मैं एक नए प्रश्न की तलाश में था। एक आदर्श दुनिया में, यह 45 मिनट में हल करने के लिए एक सरल पर्याप्त प्रश्न है, लेकिन अतिरिक्त प्रश्नों के साथ ताकि अधिक शक्तिशाली उम्मीदवार अपना कौशल दिखा सकें। इसे लागू करने में भी कॉम्पैक्ट होना चाहिए, क्योंकि कई उम्मीदवार अभी भी बोर्ड पर लिखते हैं। एक बड़ा प्लस यदि विषय किसी तरह Google उत्पादों से संबंधित है।

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

सवाल

दूरियों को मापने की बात करते हैं। हाथ आमतौर पर अंग्रेजी बोलने वाले देशों में घोड़े की ऊंचाई को मापने के लिए उपयोग की जाने वाली चार इंच की इकाई है। एक प्रकाश वर्ष , दूरी के बराबर माप की एक और इकाई है जो एक कण (या तरंग) प्रकाश की एक निश्चित संख्या में सेकंड में, लगभग एक पृथ्वी वर्ष के बराबर होती है। पहली नज़र में, वे एक-दूसरे के साथ बहुत कम हैं, सिवाय इसके कि वे दूरी को मापने के लिए उपयोग किए जाते हैं। लेकिन यह पता चला है कि Google उन्हें आसानी से परिवर्तित कर सकता है:



यह स्पष्ट लग सकता है: अंत में, वे दोनों दूरी को मापते हैं, इसलिए यह स्पष्ट है कि एक परिवर्तन है। लेकिन अगर आप इसके बारे में सोचते हैं, तो यह थोड़ा अजीब है: उन्होंने इस रूपांतरण दर की गणना कैसे की? स्पष्ट रूप से, किसी ने वास्तव में एक हल्के वर्ष में हाथों की संख्या नहीं गिना। वास्तव में, आपको इसे सीधे लेने की आवश्यकता नहीं है। आप केवल प्रसिद्ध रूपांतरणों का उपयोग कर सकते हैं:

• 1 हाथ = 4 इंच
  
• 4 इंच = 0.33333 फीट
  
• 0.33333 फीट = 6.3125e - 5 मील
  
• 6.3125e - 5 मील = 1.0737e - 17 प्रकाश वर्ष

कार्य का लक्ष्य एक प्रणाली विकसित करना है जो इस परिवर्तन का प्रदर्शन करेगा। विशेष रूप से:

इनपुट में आपके पास माप की प्रारंभिक इकाइयों के सेट के रूप में रूपांतरण कारकों (आपकी चुनी हुई भाषा में स्वरूपित) की एक सूची है, उदाहरण के लिए अंतिम इकाइयां और कारक:

  फूट १२
 फुट यार्ड 0.3333333
 और टी। डी। 

ताकि ORIGIN * MULTIPLIER = DESTINATION। एक एल्गोरिथ्म विकसित करें जो दो मनमाना इकाई मान लेता है और उनके बीच रूपांतरण कारक लौटाता है।

चर्चा

मुझे यह समस्या पसंद है क्योंकि इसका एक सहज और स्पष्ट उत्तर है: बस एक इकाई से दूसरी इकाई में परिवर्तित करें, फिर अगले तक, जब तक कि आप लक्ष्य न पा लें! मुझे एक भी उम्मीदवार याद नहीं है जो इस समस्या में भाग गया था और पूरी तरह से हैरान था कि इसे कैसे हल किया जाए। यह एक "सरल" समस्या की आवश्यकता के साथ अच्छी तरह से फिट बैठता है, क्योंकि पिछले वाले आमतौर पर लंबे अध्ययन और प्रतिबिंब की आवश्यकता के लिए कम से कम समाधान के लिए एक मूल दृष्टिकोण पाया गया था।

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

संदर्भ के लिए, फ्रेमिंग एक समस्या को एक गैर-स्पष्ट समाधान के साथ एक समकक्ष समस्या में अनुवाद करने का कार्य है, जहां समाधान को प्राकृतिक तरीके से घटाया जाता है। यदि यह पूरी तरह से अमूर्त और अभेद्य लगता है, तो मुझे खेद है, लेकिन यह है। मैं समझाता हूं कि जब मैं इस समस्या का प्रारंभिक समाधान प्रस्तुत करता हूं तो मेरा क्या मतलब है। समाधान का पहला भाग एल्गोरिथम ज्ञान को विकसित करने और लागू करने में एक अभ्यास होगा। दूसरा भाग एक नए और गैर-स्पष्ट अनुकूलन पर आने के लिए इस ज्ञान में हेरफेर करने के लिए एक अभ्यास होगा।

भाग 0. अंतर्ज्ञान

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

हम अपने जीवन के अधिकांश समय के लिए ऐसी चीजें लेकर आए हैं। अधिकांश इकाइयों के लिए, पहले से ही एक पूर्व-परिकलित रूपांतरण है, इसलिए आपको इसे संबंधित तालिका में देखने की आवश्यकता है। लेकिन अगर कोई प्रत्यक्ष रूपांतरण नहीं है (उदाहरण के लिए, हाथों से प्रकाश वर्ष तक), तो रूपांतरण पथ बनाने के लिए समझ में आता है, जैसा कि ऊपर बताया गया है:

• 1 हाथ = 4 इंच
  
• 4 इंच = 0.33333 फीट
  
• 0.33333 फीट = 6.3125e - 5 मील
  
• 6.3125e - 5 मील = 1.0737e - 17 प्रकाश वर्ष

यह बहुत सरल था, मैं सिर्फ अपनी कल्पना और एक मानक परिवर्तन तालिका का उपयोग करके इस तरह के परिवर्तन के साथ आया था! हालाँकि, कुछ प्रश्न शेष हैं। क्या कोई छोटा रास्ता है? गुणांक कितना सही है? क्या रूपांतरण हमेशा संभव है? क्या इसे स्वचालित करना संभव है? दुर्भाग्य से, यहाँ भोली दृष्टिकोण टूट जाता है।

भाग 1. भोला निर्णय

यह अच्छा है कि समस्या का एक सहज समाधान है, लेकिन वास्तव में, यह सरलता समस्या को हल करने के लिए एक बाधा है। एक नए तरीके से समझने की कोशिश करने से ज्यादा मुश्किल कुछ भी नहीं है जो आप पहले से ही समझते हैं - कम से कम नहीं क्योंकि आप अक्सर जितना सोचते हैं उससे कम जानते हैं। उदाहरण के लिए, कल्पना करें कि आप एक साक्षात्कार के लिए आए थे - और आपके पास यह सहज विधि आपके सिर में है। लेकिन वह कई महत्वपूर्ण समस्याओं को हल करने की अनुमति नहीं देता है।

उदाहरण के लिए, यदि कोई रूपांतरण नहीं है तो क्या होगा ? स्पष्ट दृष्टिकोण कुछ भी नहीं कहता है, क्या वास्तव में एक इकाई से दूसरे में बदलना संभव है। यदि वे मुझे एक हजार रूपांतरण दर देते हैं, तो यह निर्धारित करना मेरे लिए बहुत मुश्किल होगा कि क्या यह सिद्धांत रूप में संभव है। अगर मुझे एक पॉइंटर और एक जैब की अपरिचित (या आविष्कृत) इकाइयों के बीच रूपांतरण करने के लिए कहा जाता है, तो मुझे नहीं पता कि कहां से शुरू करना है। एक सहज दृष्टिकोण यहाँ कैसे मदद करता है?

मुझे यह स्वीकार करना चाहिए कि यह एक प्रकार का विरोधाभासी परिदृश्य है, लेकिन एक अधिक यथार्थवादी भी है। आप देखते हैं कि समस्या के मेरे बयान में केवल दूरी की इकाइयां शामिल हैं। यह उद्देश्य पर किया जाता है। अगर मैं सिस्टम को इंच से किलोग्राम में बदलने के लिए कहूं तो क्या होगा? आप और मैं दोनों जानते हैं कि यह संभव नहीं है क्योंकि वे विभिन्न प्रकारों को मापते हैं, लेकिन इनपुट "प्रकार" के बारे में कुछ भी नहीं कहता है जो प्रत्येक इकाई को मापता है।

यह यहां है कि प्रश्न का सावधानीपूर्वक सूत्र मजबूत उम्मीदवारों को खुद को साबित करने की अनुमति देता है। एल्गोरिथ्म को विकसित करने से पहले , वे सिस्टम के चरम मामलों पर सोचते हैं। और समस्या का ऐसा बयान उद्देश्यपूर्ण तरीके से मुझे यह पूछने का अवसर देता है कि क्या हम विभिन्न इकाइयों का अनुवाद करेंगे। प्रारंभिक अवस्था में होने पर यह इतनी बड़ी समस्या नहीं है, लेकिन यह हमेशा एक अच्छा संकेत है जब कोई मुझसे अग्रिम में पूछता है: "यदि रूपांतरण संभव नहीं है तो कार्यक्रम को क्या लौटना चाहिए?" प्रश्न को इस तरह से रखने से मुझे कम से कम एक पंक्ति कोड लिखने से पहले उम्मीदवार की क्षमताओं का पता चलता है।

ग्राफ दृश्य

जाहिर है, भोली दृष्टिकोण उपयुक्त नहीं है, इसलिए हमें यह सोचने की ज़रूरत है कि इस तरह के रूपांतरण कैसे करें? इसका उत्तर इकाइयों को एक ग्राफ के रूप में मानना ​​है। यह इस समस्या को हल करने के लिए आवश्यक समझ की पहली छलांग है।

विशेष रूप से, कल्पना करें कि प्रत्येक इकाई एक ग्राफ में एक नोड है, और नोड A से नोड B तक एक किनारा है यदि A को चलाया जा सकता है:



किनारों को रूपांतरण दर के साथ लेबल किया जाता है जिसके द्वारा आपको B प्राप्त करने के लिए A को गुणा करना चाहिए B

मैंने लगभग हमेशा उम्मीद की थी कि उम्मीदवार इस तरह के फ्रेमिंग के साथ आएंगे, और शायद ही कभी उसे गंभीर संकेत दिए। मैं उस उम्मीदवार को क्षमा कर सकता हूं जो असहमति सेट का उपयोग करने की समस्या का समाधान नहीं देखता है या रैखिक बीजगणित से बहुत गहराई से परिचित नहीं है एक समाधान का एहसास करने के लिए जो आसन्न मैट्रिक्स की शक्ति को कम करने के लिए कम करता है, लेकिन ग्राफ़ को किसी भी पाठ्यक्रम या प्रोग्रामिंग पाठ्यक्रम में सिखाया जाता है। यदि उम्मीदवार के पास उपयुक्त ज्ञान नहीं है, तो यह "नो हायरिंग" संकेत है।

किसी भी मामले में,

एक ग्राफ प्रतिनिधित्व शास्त्रीय ग्राफ खोज समस्या के समाधान को कम करता है। विशेष रूप से, दो एल्गोरिदम यहां उपयोगी हैं: विस्तृत खोज (बीएफएस) और गहरी खोज (डीएफएस)। चौड़ाई में खोज करते समय, हम मूल से उनकी दूरी के अनुसार नोड्स की जांच करते हैं:


गहरे रंग के ब्लूज़ का मतलब बाद की पीढ़ियों से है

और गहराई से खोज करने पर, हम उस क्रम में नोड्स की जांच करते हैं जिसमें वे होते हैं:



गहरे रंग के ब्लूज़ का मतलब बाद की पीढ़ियों से भी है। कृपया ध्यान दें कि हम वास्तव में सभी साइटों पर नहीं जाते हैं

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

लेकिन रुकिए, कुछ याद आ रहा है। हम कोई रास्ता नहीं देखना चाहते हैं, हम एक रूपांतरण दर खोजना चाहते हैं! यह वह जगह है जहां उम्मीदवार को कूदना चाहिए: यह पता चला है कि आप किसी भी खोज एल्गोरिथ्म को संशोधित कर सकते हैं कि रूपांतरण दर की गणना केवल अतिरिक्त राज्य को बचाते हुए आप कर सकते हैं। यही कारण है कि चित्र अब समझ में नहीं आते हैं, तो चलो कोड में सही गोता लगाएँ।

सबसे पहले, आपको ग्राफ़ की डेटा संरचना निर्धारित करने की आवश्यकता है, इसलिए हम इसका उपयोग करते हैं:

 class RateGraph(object): def __init__(self, rates): 'Initialize the graph from an iterable of (start, end, rate) tuples.' self.graph = {} for orig, dest, rate in rates: self.add_conversion(orig, dest, rate) def add_conversion(self, orig, dest, rate): 'Insert a conversion into the graph.' if orig not in self.graph: self.graph[orig] = {} self.graph[orig][dest] = rate def get_neighbors(self, node): 'Returns an iterable of the nodes neighboring the given node.' if node not in self.graph: return None return self.graph[node].items() def get_nodes(self): 'Returns an iterable of all the nodes in the graph.' return self.graph.keys() 

तो चलिए DFS पर शुरू करते हैं। इसे लागू करने के कई तरीके हैं, लेकिन अब तक सबसे आम एक पुनरावर्ती समाधान है। आइए इसकी शुरुआत करें:

 from collections import deque def __dfs_helper(rate_graph, node, end, rate_from_origin, visited): if node == end: return rate_from_origin visited.add(node) for unit, rate in rate_graph.get_neighbors(node): if unit not in visited: rate = __dfs_helper(rate_graph, unit, end, rate_from_origin * rate, visited) if rate is not None: return rate return None def dfs(rate_graph, node, end): return __dfs_helper(rate_graph, node, end, 1.0, set()) 

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

यह एक महान कार्यान्वयन है, लेकिन यह दो मुख्य दोषों से ग्रस्त है। सबसे पहले, यह पुनरावर्ती है। अगर यह पता चला कि वांछित पथ में एक हजार से अधिक छलांग शामिल हैं, तो हम एक गड़बड़ के साथ बाहर निकलेंगे। बेशक, यह संभावना नहीं है, लेकिन अगर दीर्घकालिक सेवा के लिए कुछ अस्वीकार्य है, तो यह एक विफलता है। दूसरे, भले ही हम सफलतापूर्वक पूर्ण हों, उत्तर में कुछ अवांछनीय गुण हैं।

मैंने वास्तव में पहले ही पोस्ट की शुरुआत में एक संकेत दिया था। क्या आपने देखा है कि Google 1.0739e-17 की रूपांतरण दर कैसे दिखाता है, लेकिन मेरी मैन्युअल गणना 1.0737e-17 देता है? यह पता चला है कि ये सभी फ़्लोटिंग पॉइंट गुणन एक पहले से ही त्रुटि को फैलाने के बारे में सोचते हैं। इस लेख के लिए बहुत अधिक बारीकियां हैं, लेकिन नीचे की रेखा यह है कि आपको त्रुटियों को जमा करने और समस्याओं का कारण बनने से बचने के लिए फ्लोटिंग पॉइंट गुणा को कम करना होगा।

डीएफएस एक महान खोज एल्गोरिथ्म है। यदि कोई समाधान मौजूद है, तो वह उसे खोज लेगा। लेकिन उसके पास एक महत्वपूर्ण संपत्ति का अभाव है: जरूरी नहीं कि वह सबसे छोटा रास्ता खोजे। यह हमारे लिए महत्वपूर्ण है क्योंकि एक छोटा रास्ता कम कूदता है और अस्थायी बिंदु गुणन के कारण कम त्रुटि है। समस्या को हल करने के लिए, हम BFS की ओर मुड़ते हैं।

भाग 2. बीएफएस समाधान

इस स्तर पर, यदि कोई उम्मीदवार सफलतापूर्वक एक पुनरावर्ती डीएफएस समाधान लागू करता है और उस पर रुक जाता है, तो मैं आमतौर पर इस उम्मीदवार को काम पर रखने के लिए कम से कम एक कमजोर सिफारिश देता हूं। उन्होंने समस्या को समझा, उपयुक्त फ्रेमिंग को चुना और कार्यशील समाधान को लागू किया। यह एक भोला निर्णय है, इसलिए मैं उसे काम पर रखने पर जोर नहीं देता, लेकिन अगर वह अन्य साक्षात्कारों में अच्छी तरह से नकल करता है, तो मैं मना करने की सलाह नहीं दूंगा।

यह दोहराने के लायक है: यदि संदेह है, तो एक भोली समाधान लिखें! यहां तक ​​कि अगर यह पूरी तरह से इष्टतम नहीं है, तो बोर्ड पर कोड की उपस्थिति पहले से ही एक उपलब्धि है, और अक्सर इसके आधार पर सही समाधान पाया जा सकता है। मैं अलग तरीके से कहूंगा: कभी भी किसी काम के लिए नहीं। सबसे अधिक संभावना है, आपने एक भोली समाधान के बारे में सोचा था, लेकिन इसे पेश नहीं करना चाहते थे, क्योंकि आप जानते हैं कि यह इष्टतम नहीं है। यदि आप अभी सबसे अच्छा समाधान तैयार करने के लिए तैयार हैं, तो ठीक है, लेकिन यदि नहीं, तो अधिक जटिल चीजों पर जाने से पहले की गई प्रगति को रिकॉर्ड करें।

अब से, आइए एल्गोरिदम में सुधार के बारे में बात करते हैं। एक पुनरावर्ती डीएफएस समाधान का मुख्य नुकसान यह है कि यह पुनरावर्ती है और गुणन की संख्या को कम नहीं करता है। जैसा कि हम जल्द ही देखेंगे, बीएफएस गुणा की संख्या को कम करता है, और इसे पुनरावर्ती रूप से लागू करना भी बहुत मुश्किल है। दुर्भाग्य से, हमें पुनरावर्ती डीएफए समाधान को छोड़ना होगा, क्योंकि इसे सुधारने के लिए हमें कोड को पूरी तरह से फिर से लिखना होगा।

आगे की हलचल के बिना, मैं बीएफएस पर आधारित एक पुनरावृत्त दृष्टिकोण प्रस्तुत करता हूं:

 from collections import deque def bfs(rate_graph, start, end): to_visit = deque() to_visit.appendleft( (start, 1.0) ) visited = set() while to_visit: node, rate_from_origin = to_visit.pop() if node == end: return rate_from_origin visited.add(node) for unit, rate in rate_graph.get_neighbors(node): if unit not in visited: to_visit.appendleft((unit, rate_from_origin * rate)) return None 

यह कार्यान्वयन पिछले एक से कार्यात्मक रूप से बहुत अलग है, लेकिन यदि आप बारीकी से देखते हैं, तो यह लगभग एक ही है, एक महत्वपूर्ण बदलाव के साथ: पुनरावर्ती डीएफएस कॉल स्टैक में आगे के मार्ग की स्थिति को बचाता है, प्रभावी ढंग से एलआईएफओ स्टैक को लागू करते हुए, पुनरावृत्ति समाधान इसे कतार में संग्रहीत करता है फीफो।

इसका मतलब है कि संपत्ति "सबसे छोटा रास्ता / कम से कम संख्या में गुणा" है। हम उस क्रम में नोड्स का दौरा करते हैं जिसमें वे होते हैं, और इस तरह से हमें पीढ़ियों के नोड मिलते हैं। पहला नोड अपने पड़ोसियों को सम्मिलित करता है, और फिर हम हर समय और इतने पर अपने पड़ोसियों को चिपकाने के लिए इन पड़ोसियों का दौरा करते हैं। सबसे छोटी पथ संपत्ति इस तथ्य से अनुसरण करती है कि स्रोत से उनकी दूरी के क्रम में नोड्स का दौरा किया जाता है। इसलिए, जब हम एक गंतव्य का सामना करते हैं, तो हम जानते हैं कि कोई भी पुरानी पीढ़ी नहीं है जो इसे आगे बढ़ा सकती है।

इस समय, हम लगभग हो चुके हैं। पहले आपको कुछ सवालों के जवाब देने की जरूरत है, और वे समस्या के मूल सूत्रीकरण पर लौटने के लिए मजबूर हैं।

सबसे पहले, सबसे तुच्छ बात अगर मूल इकाई मौजूद नहीं है? यही है, हम दिए गए नाम के साथ नोड नहीं पा सकते हैं। व्यवहार में, आपको स्ट्रिंग्स के कुछ सामान्यीकरण करने की आवश्यकता है ताकि पाउंड, पाउंड और एलबी एक ही "पाउंड" नोड (या कुछ अन्य कैनोनिकल प्रतिनिधित्व) को इंगित करें, लेकिन यह हमारे प्रश्न के दायरे से बाहर है।

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

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

 def add_conversion(self, orig, dest, rate): 'Insert a conversion into the graph. Note we insert its inverse also.' if orig not in self.graph: self.graph[orig] = {} self.graph[orig][dest] = rate if dest not in self.graph: self.graph[dest] = {} self.graph[dest][orig] = 1.0 / rate 

भाग 3. मूल्यांकन

हो गया! यदि उम्मीदवार इस बिंदु पर पहुंच गया है, तो मैं सबसे अधिक संभावना उसे भाड़े के लिए सुझाऊंगा। यदि आपने कंप्यूटर विज्ञान का अध्ययन किया है या एल्गोरिदम में एक कोर्स किया है, तो आप पूछ सकते हैं: "क्या यह वास्तव में इस आदमी के साथ साक्षात्कार प्राप्त करने के लिए पर्याप्त है?", जिसके लिए मैं जवाब दूंगा: "अनिवार्य रूप से, हाँ।"

इससे पहले कि आप यह तय करें कि प्रश्न बहुत सरल है, आइए देखें कि इस बिंदु तक पहुँचने के लिए उम्मीदवार को क्या करना चाहिए:

• प्रश्न को समझें
  
• एक ग्राफ के रूप में परिवर्तनों का एक नेटवर्क बनाएँ
  
• यह समझें कि गुणांक की तुलना ग्राफ के किनारों से की जा सकती है
  
• इसे प्राप्त करने के लिए खोज एल्गोरिदम का उपयोग करने की संभावना देखें।
  
• अपना पसंदीदा एल्गोरिदम चुनें और इसे ऑड्स ट्रैक करने के लिए बदलें
  
• यदि उन्होंने डीएफएस को एक भोले समाधान के रूप में लागू किया, तो उसकी कमजोरियों को पहचानें।
  
• BFS को लागू करें
  
• वापस कदम और चरम मामलों का अध्ययन करने के लिए:
  
  • क्या होगा यदि हमें एक नोड के बारे में पूछा जाए जो मौजूद नहीं है?
    
  • यदि रूपांतरण कारक मौजूद नहीं है तो क्या होगा?
• पहचानें कि उलटा रूपांतरण संभव है और शायद आवश्यक है

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

"लेकिन रुको!" आप पूछ सकते हैं। - क्या Google रनटाइम जटिलता से ग्रस्त नहीं है? आपने इस समस्या के अस्थायी या स्थानिक जटिलता के बारे में भी नहीं पूछा। ओह ठीक है! ” आप यह भी पूछ सकते हैं: "एक मिनट रुको, आपने रेटिंग दी" किराया के लिए अत्यधिक अनुशंसा "? इसे कैसे प्राप्त करें? ” बहुत अच्छे सवाल, दोनों। यह हमें हमारे अंतिम अतिरिक्त बोनस दौर में लाता है ...

भाग 4. क्या बेहतर करना संभव है?

इस बिंदु पर, मैं एक अच्छे उत्तर के साथ उम्मीदवार को बधाई देना चाहता हूं और यह स्पष्ट करना चाहता हूं कि आगे सब कुछ सिर्फ एक बोनस है। जब दबाव गायब हो जाता है, तो हम बनाना शुरू कर सकते हैं।

तो बीएफएस को चलाने में क्या कठिनाई है? सबसे खराब स्थिति में, हमें प्रत्येक व्यक्ति के नोड और किनारे पर विचार करना चाहिए, जो रैखिक जटिलता O(N+E) । यह O(N+E) ग्राफ निर्माण की उसी जटिलता के शीर्ष पर है। एक खोज इंजन के लिए, यह शायद अच्छा है: माप का एक हजार इकाइयां अधिकांश उचित अनुप्रयोगों के लिए पर्याप्त है, और प्रत्येक क्वेरी के लिए मेमोरी खोज करना एक अधिभार नहीं है।

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

यह अक्सर गणना परिणामों को केवल कैश करने के लिए सुझाया जाता है। जब भी एक इकाई रूपांतरण की गणना की जाती है, हम हमेशा दो रूपांतरणों के बीच एक बढ़त जोड़ सकते हैं। एक बोनस के रूप में, हमें उलटा परिवर्तन मिलता है, और मुफ्त में! हो गया ना?

वास्तव में, यह हमें एक विषम रूप से निरंतर खोज समय देगा, लेकिन इसमें अतिरिक्त किनारों के भंडारण की लागत होगी। यह वास्तव में काफी महंगा हो जाता है: समय के साथ, हम एक पूर्ण ग्राफ के लिए प्रयास करेंगे, क्योंकि सभी जोड़े परिवर्तनों को धीरे-धीरे गणना और संग्रहीत किया जाता है। ग्राफ में संभावित किनारों की संख्या नोड्स की संख्या का आधा वर्ग है, इसलिए एक हजार नोड्स के लिए हमें आधा मिलियन किनारों की आवश्यकता है। दस हजार नोड्स के लिए, लगभग पचास मिलियन, आदि।

खोज इंजन के दायरे से परे, एक लाख नोड्स के ग्राफ के लिए, हम आधे ट्रिलियन किनारों के लिए प्रयास करते हैं। यह राशि केवल स्टोर करने के लिए अनुचित है, साथ ही हम ग्राफ़ में किनारों को सम्मिलित करने में समय बिताते हैं। हमें बेहतर करना चाहिए।

सौभाग्य से, द्विघात अंतरिक्ष विकास के बिना, गुणांक की खोज करने के लिए निरंतर समय प्राप्त करने का एक तरीका है। वास्तव में, हमें जो कुछ भी चाहिए वह लगभग हमारी नाक के नीचे है।

भाग 4. लगातार समय

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

BFS समाधान पर एक और नज़र डालें:

 from collections import deque def bfs(rate_graph, start, end): to_visit = deque() to_visit.appendleft( (start, 1.0) ) visited = set() while to_visit: node, rate_from_origin = to_visit.pop() if node == end: return rate_from_origin visited.add(node) for unit, rate in rate_graph.get_neighbors(node): if unit not in visited: to_visit.appendleft((unit, rate_from_origin * rate)) return None 

आइए देखें कि यहां क्या होता है: हम स्रोत नोड से शुरू करते हैं, और प्रत्येक नोड से हमारा सामना होता है, हम स्रोत से इस नोड में रूपांतरण गुणांक की गणना करते हैं। फिर, जैसे ही हम गंतव्य पर पहुंचते हैं, हम शुरुआती और समाप्ति बिंदुओं के बीच गुणांक वापस कर देते हैं और मध्यवर्ती गुणांक को त्याग देते हैं।

ये मध्यवर्ती अनुपात प्रमुख हैं। लेकिन अगर हम उन्हें फेंक न दें तो क्या होगा? क्या होगा अगर हम उन्हें लिखने के बजाय नीचे लिखें? सभी सबसे जटिल और समझ से बाहर खोज सरल हो जाती हैं: ए से बी के अनुपात को खोजने के लिए, पहले एक्स से बी के अनुपात का पता लगाएं, फिर इसे एक्स से ए के अनुपात से विभाजित करें, और आप कर रहे हैं! नेत्रहीन, ऐसा दिखता है:


ध्यान दें कि किसी भी दो नोड्स के बीच दो किनारों से अधिक नहीं

यह पता चला है कि इस तालिका की गणना करने के लिए, हमें लगभग BFS समाधान को बदलने की आवश्यकता नहीं है:

 from collections import deque def make_conversions(graph): def conversions_bfs(rate_graph, start, conversions): to_visit = deque() to_visit.appendleft( (start, 1.0) ) while to_visit: node, rate_from_origin = to_visit.pop() conversions[node] = (start, rate_from_origin) for unit, rate in rate_graph.get_neighbors(node): if unit not in conversions: to_visit.append((unit, rate_from_origin * rate)) return conversions conversions = {} for node in graph.get_nodes(): if node not in conversions: conversions_bfs(graph, node, conversions) return conversions 

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

इस BFS के बाहर, एक सहायक कार्य है जो एक ग्राफ़ में नोड्स पर पुनरावृत्त करता है। जब भी यह अनुवाद शब्दकोश के बाहर एक नोड का सामना करता है, तो यह उस नोड से शुरू होने वाला बीएफएस शुरू होता है। , .

, , :

 def convert(conversions, start, end): 'Given a conversion structure, performs a constant-time conversion' try: start_root, start_rate = conversions[start] end_root, end_rate = conversions[end] except KeyError: return None if start_root != end_root: return None return end_rate / start_rate 

« » . « » : , , BFS, , . , .

! O(V+E)(पिछले समाधानों से भी बदतर नहीं), लेकिन वह भी निरंतर समय के साथ खोज करती है। सैद्धांतिक रूप से, हम अंतरिक्ष आवश्यकताओं को दोगुना करते हैं, लेकिन ज्यादातर समय हमें मूल ग्राफ की आवश्यकता नहीं होती है, इसलिए हम इसे केवल हटा सकते हैं और केवल इस एक का उपयोग कर सकते हैं। इसके अलावा, स्थानिक जटिलता वास्तव में मूल ग्राफ से कम है: इसकी आवश्यकता है O(V+E)क्योंकि इसे सभी किनारों और कोने को संग्रहीत करने की आवश्यकता है, और इस संरचना की आवश्यकता केवल O(V)इसलिए है क्योंकि हमें किनारों की आवश्यकता नहीं है।

परिणाम

, , , , - . - , . , .

( , , , ), « ». , : , , .

यह एक उपयोगी संकेत है। मैं समझ सकता हूं कि जब कोई व्यक्ति उन्नत या अस्पष्ट डेटा संरचनाओं को नहीं जानता है, क्योंकि हम ईमानदार होंगे, आपको शायद ही कभी असहमति सेट को लागू करना होगा। लेकिन रेखांकन एक मौलिक डेटा संरचना है और इस विषय पर लगभग किसी भी परिचयात्मक पाठ्यक्रम के हिस्से के रूप में पढ़ाया जाता है। यदि उम्मीदवार उन्हें समझने के लिए संघर्ष करता है या आसानी से उन्हें लागू नहीं कर सकता है, तो शायद उसके लिए Google पर सफल होना मुश्किल होगा (कम से कम मेरे समय में, मुझे नहीं पता कि आज कैसे है)।

दूसरी ओर, एल्गोरिथ्म का विकल्प विशेष रूप से उपयोगी सिग्नल स्रोत नहीं था। फ़्रेमिंग चरण से गुजरने वाले लोग आमतौर पर एल्गोरिथ्म में बिना किसी समस्या के आते थे। मुझे संदेह है कि यह इस तथ्य के कारण है कि खोज एल्गोरिदम लगभग हमेशा रेखांकन के साथ-साथ खुद को सिखाया जाता है, इसलिए यदि कोई एक से परिचित है, तो वे दूसरे को जानते हैं।

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

मेरी राय में, जो कोई भी कार्यान्वयन के चरण से गुजरता है, उसने पहले ही मुझे "किराया" सिफारिश प्राप्त कर ली है, और निरंतर नेतृत्व समय की चर्चा बस एक बोनस है। यद्यपि हमने लेख में विस्तार से समाधान को देखा, व्यवहार में, कोड लिखने के बजाय एक मौखिक चर्चा आमतौर पर अधिक उत्पादक होती है। बहुत कम उम्मीदवार तुरंत कोई निर्णय ले पाते। मुझे अक्सर पर्याप्त सुराग देना पड़ता था, और तब भी कई लोग उसे नहीं ढूंढ पाए थे। यह सामान्य है: जैसा कि अपेक्षित था, अत्यधिक अनुशंसित रेटिंग अर्जित करना कठिन है।

लेकिन रुको, यह सब नहीं है!

, , , , . :

-, : , , . , , . , - , - . , , .

-, , , . — : — , A B — / . : , , , , , . .

अंत में, एक असली रत्न: कुछ इकाइयों को विभिन्न आधार इकाइयों के संयोजन के रूप में व्यक्त किया जाता है। उदाहरण के लिए, एसआई प्रणाली में एक वाट को किलो के रूप में परिभाषित किया गया है • m³ / satt। अंतिम कार्य इन इकाइयों के बीच रूपांतरण का समर्थन करने के लिए इस प्रणाली का विस्तार करना है, केवल मूल एसआई इकाइयों की परिभाषाओं को ध्यान में रखते हुए।

यदि आपके कोई प्रश्न हैं, तो बेझिझक मुझसे reddit पर संपर्क करें ।

निष्कर्ष

, , . : , , , . , , , , : , . , , , .

मुझे उम्मीद है कि आपको यह लेख उपयोगी लगा होगा। मैं समझता हूं कि कुछ पिछले लेखों में एल्गोरिदम के साथ उतने रोमांच नहीं हो सकते हैं। डेवलपर्स के साक्षात्कार में, एल्गोरिदम पर बहुतायत से चर्चा करने का रिवाज है। लेकिन सच्चाई यह है कि एक सरल, प्रसिद्ध विधि का उपयोग करते समय महत्वपूर्ण कठिनाइयां उत्पन्न होती हैं। सभी कोड इस लेख श्रृंखला के भंडार में है ।