यह Google में साक्षात्कारों से कार्यों की चर्चा का एक नया लेख है। जब मैंने वहां काम किया, तो मैंने उम्मीदवारों को ऐसे कार्यों की पेशकश की। फिर एक रिसाव हुआ, और उन्हें प्रतिबंधित कर दिया गया। लेकिन सिक्का का एक फ्लिप पक्ष है: अब मैं स्वतंत्र रूप से समाधान बता सकता हूं।

शुरू करने के लिए अच्छी खबर: मैंने Google छोड़ दिया! मुझे आपको यह बताते हुए खुशी हो रही है कि मैं अब न्यू यॉर्क में रेडिट के तकनीकी प्रबंधक के रूप में काम कर रहा हूँ! लेकिन लेखों की यह श्रृंखला अभी भी जारी रहेगी।

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

सवाल

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

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

तो सवाल है।

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

आइए कार्य को औपचारिक रूप दें। मान लें कि स्ट्रिंग जोड़े के दो सेट हैं: पर्याय जोड़े और क्वेरी जोड़े।

विशेष रूप से, यहाँ उदाहरण के लिए एक उदाहरण दिया गया है:

SYNONYMS = [ ('rate', 'ratings'), ('approval', 'popularity'), ] QUERIES = [ ('obama approval rate', 'obama popularity ratings'), ('obama approval rates', 'obama popularity ratings'), ('obama approval rate', 'popularity ratings obama') ] 

तार्किक मूल्यों की एक सूची तैयार करना आवश्यक है: प्रत्येक जोड़ी पर्यायवाची में प्रश्न हैं।

सभी नए प्रश्न ...

पहली नज़र में, यह एक सरल कार्य है। लेकिन आप जितना लंबा सोचते हैं, उतना ही मुश्किल होता जाता है। क्या किसी शब्द के कई पर्यायवाची शब्द हो सकते हैं? शब्द आदेश मायने रखता है? क्या पर्यायवाची रिश्ते सकर्मक हैं, यदि A, B का पर्यायवाची है और B, C का पर्यायवाची है, तो A, C का पर्यायवाची है? क्या पर्यायवाची कुछ शब्दों को शामिल कर सकते हैं, "संयुक्त राज्य अमेरिका" "संयुक्त राज्य अमेरिका" या "संयुक्त राज्य अमेरिका" वाक्यांशों का पर्याय कैसे है?

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

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


मैंडलब्रॉट सेट

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

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

भाग 1. (बिल्कुल नहीं) एक साधारण मामला

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

एक उच्च-स्तरीय अवलोकन निम्नानुसार है: क्वेरी को शब्दों में तोड़ो (उदाहरण के लिए, रिक्त स्थान पर) और समान शब्दों और समानार्थक शब्द के लिए खोज करने के लिए संबंधित जोड़े की तुलना करें। नेत्रहीन, ऐसा दिखता है:



कोड में:

 def synonym_queries(synonym_words, queries): ''' synonym_words: iterable of pairs of strings representing synonymous words queries: iterable of pairs of strings representing queries to be tested for synonymous-ness ''' output = [] for q1, q2 in queries: q1, q2 = q1.split(), q2.split() if len(q1) != len(q2): output.append(False) continue result = True for i in range(len(q1)): w1, w2 = q1[i], q2[i] if w1 == w2: continue elif words_are_synonyms(w1, w2): continue result = False break output.append(result) return output 

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

लेकिन पहली नज़र में ऐसा लगता है कि इससे ज्यादा बारीकियाँ हैं। बेशक, सबसे कठिन घटक समानार्थक शब्द की तुलना है। यद्यपि घटक को समझना और वर्णन करना आसान है, लेकिन गलती करने के कई तरीके हैं। मैं आपको सबसे सामान्य गलतियों के बारे में बताऊंगा।

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

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

प्रत्येक साक्षात्कार में, मैंने सफलता और असफलता का एक अलग संयोजन देखा, ये सबसे आम गलतियाँ हैं।

यादृच्छिक प्रदर्शन हत्यारे

सबसे पहले, कुछ उम्मीदवारों ने पर्यायवाची शब्दों की सूची को ट्रेस करके पर्यायवाची का पता लगाया है:

 ... elif (w1, w2) in synonym_words: continue ... 

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

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

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

उम्मीदवार को अपनी इंद्रियों में आने के लिए, यह आमतौर पर उसे याद दिलाने के लिए पर्याप्त है कि इनपुट संरचना एक सूची है। यह निरीक्षण करना बहुत महत्वपूर्ण है कि उम्मीदवार किस प्रकार संकेत देता है। सर्वश्रेष्ठ उम्मीदवार तुरंत किसी भी समानार्थी शब्द को पूर्व-संसाधित करने का प्रयास करते हैं, जो एक अच्छी शुरुआत है। हालाँकि, यह दृष्टिकोण इसके नुकसान के बिना नहीं है ...

सही डेटा संरचना का उपयोग करें

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

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

 ... synonyms = {} for w1, w2 in synonym_words: synonyms[w1] = w2 ... elif synonyms[w1] == w2: continue 

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

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

 ... synonyms = defaultdict(set) for w1, w2 in synonym_words: synonyms[w1].append(w2) synonyms[w2].append(w1) ... elif w2 in synonyms.get(w1, tuple()): continue 

दो आवेषण क्यों करते हैं और दो बार अधिक मेमोरी का उपयोग करते हैं?

 ... synonyms = defaultdict(set) for w1, w2 in synonym_words: synonyms[w1].append(w2) ... elif (w2 in synonyms.get(w1, tuple()) or w1 in synonyms.get(w2, tuple())): continue 

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

क्रमबद्ध करें?

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

दुर्भाग्य से, समय की जटिलता में हस्तक्षेप होता है: समानार्थक शब्द की सूची को Nlog(N) लिए Nlog(N) समय की आवश्यकता होती है, और फिर समानार्थी शब्द के प्रत्येक जोड़े की खोज के लिए एक और log(N) , जबकि वर्णित प्रीप्रोसेसिंग समाधान रैखिक और फिर निरंतर समय में होता है। इसके अलावा, मैं स्पष्ट रूप से बोर्ड पर छँटाई और द्विआधारी खोज को लागू करने के लिए उम्मीदवार को मजबूर करने के खिलाफ हूं, क्योंकि: 1) सॉर्टिंग एल्गोरिदम अच्छी तरह से ज्ञात हैं, इसलिए, जहां तक ​​मुझे पता है, उम्मीदवार इसे बिना सोचे जारी कर सकते हैं; 2) इन एल्गोरिदम को सही ढंग से लागू करना मुश्किल है, और अक्सर सर्वश्रेष्ठ उम्मीदवार भी ऐसी गलतियाँ करेंगे जो आपके प्रोग्रामिंग कौशल के बारे में कुछ नहीं कहते हैं।

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

अंत में समाधान

अंत में, उम्मीदवार कुछ सही और यथोचित इष्टतम प्रदान करता है। यहां दी गई शर्तों के लिए रैखिक समय और रैखिक स्थान में कार्यान्वयन है:

 def synonym_queries(synonym_words, queries): ''' synonym_words: iterable of pairs of strings representing synonymous words queries: iterable of pairs of strings representing queries to be tested for synonymous-ness ''' synonyms = defaultdict(set) for w1, w2 in synonym_words: synonyms[w1].add(w2) output = [] for q1, q2 in queries: q1, q2 = q1.split(), q2.split() if len(q1) != len(q2): output.append(False) continue result = True for i in range(len(q1)): w1, w2 = q1[i], q2[i] if w1 == w2: continue elif ((w1 in synonyms and w2 in synonyms[w1]) or (w2 in synonyms and w1 in synonyms[w2])): continue result = False break output.append(result) return output 

कुछ त्वरित नोट्स:

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

भाग 2: कठिन हो रही है!

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

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

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

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

सकारात्मकता: Naive दृष्टिकोण

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

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

 synonyms = defaultdict(set) for w1, w2 in synonym_words: for w in synonyms[w1]: synonyms[w].add(w2) synonyms[w1].add(w2) for w in synonyms[w2]: synonyms[w].add(w1) synonyms[w2].add(w1) 

कृपया ध्यान दें कि कोड बनाते समय, हम पहले ही इस समाधान में देरी कर चुके हैं।

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



ध्यान दें कि हम तीन कुंजी और छह रिकॉर्ड से चार कुंजी और बारह रिकॉर्ड से गए थे। 50 पर्यायवाची शब्द के साथ 50 कुंजी और लगभग 2500 प्रविष्टियों की आवश्यकता होगी। एक शब्द का प्रतिनिधित्व करने के लिए आवश्यक स्थान समानार्थी शब्द के सेट में वृद्धि के साथ चौगुना बढ़ता है, जो कि व्यर्थ है।

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

ट्रांज़िटिविटी: डिस्गॉइंट सेट का उपयोग करना

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

सामान्य सेट संरचना (हैशसेट, ट्रीसेट) एक कंटेनर है जो आपको यह निर्धारित करने की अनुमति देता है कि कोई वस्तु इसके अंदर या बाहर है या नहीं। Disjoint सेट एक पूरी तरह से अलग समस्या को हल करते हैं: एक विशिष्ट तत्व को परिभाषित करने के बजाय, वे आपको यह निर्धारित करने की अनुमति देते हैं कि क्या दो तत्व एक ही सेट से संबंधित हैं । इसके अलावा, संरचना यह एक सम्मोहक तेजी से समय O(a(n)) , जहां a(n) उलटा एकरमैन फ़ंक्शन है। यदि आपने उन्नत एल्गोरिदम का अध्ययन नहीं किया है, तो आप इस फ़ंक्शन को नहीं जान सकते हैं, जो सभी वाजिब इनपुट के लिए वास्तव में निरंतर समय में निष्पादित होता है।

उच्च स्तर पर, एल्गोरिथ्म निम्नानुसार काम करता है। प्रत्येक तत्व के लिए माता-पिता के साथ पेड़ों द्वारा सेट का प्रतिनिधित्व किया जाता है। चूँकि प्रत्येक पेड़ की जड़ होती है (एक ऐसा तत्व जो उसका अपना माता-पिता होता है), हम यह निर्धारित कर सकते हैं कि क्या दो तत्व अपने माता-पिता को मूल में बताकर एक ही सेट से संबंधित हैं। यदि दो तत्वों की एक जड़ है, तो वे एक सेट से संबंधित हैं। संयोजन सेट करना भी आसान है: बस मूल तत्वों को ढूंढें और उनमें से एक को दूसरे की जड़ बनाएं।

अभी तक तो अच्छा है, लेकिन अभी तक कोई चकाचौंध की गति नहीं देखी गई है। इस संरचना की प्रतिभा संपीड़न नामक एक प्रक्रिया में है। मान लीजिए कि आपके पास निम्नलिखित पेड़ हैं:



कल्पना कीजिए कि आप जानना चाहते हैं कि शीघ्र और जल्दबाजी पर्यायवाची हैं। प्रत्येक माता पिता के माध्यम से जाओ - और एक ही तेजी से जड़ पाते हैं। अब मान लें कि हम तेज और तेज शब्दों के लिए एक समान जांच करते हैं। फिर, हम जड़ तक जाते हैं, और शीघ्रता से हम उसी मार्ग पर जाते हैं। क्या काम के दोहराव से बचा जा सकता है?

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


तेजी और तेज के बीच के सभी शब्दों के लिए, माता-पिता को अपडेट किया गया था, यही बात जल्दबाजी में हुई थी

अब सभी बाद की कॉल निरंतर समय में होगी, क्योंकि इस पेड़ में प्रत्येक नोड तेज होने के लिए इंगित करता है । संचालन की समय जटिलता का मूल्यांकन करना बहुत आसान नहीं है: वास्तव में, यह स्थिर नहीं है, क्योंकि यह पेड़ों की गहराई पर निर्भर करता है, लेकिन यह निरंतर के करीब है, क्योंकि संरचना जल्दी से अनुकूलित है। सादगी के लिए, हम मानते हैं कि समय स्थिर है।

इस अवधारणा के साथ, हम अपनी समस्या के लिए असंबंधित सेट लागू करते हैं:

 class DisjointSet(object): def __init__(self): self.parents = {} def get_root(self, w): words_traversed = [] while self.parents[w] != w: words_traversed.append(w) w = self.parents[w] for word in words_traversed: self.parents[word] = w return w def add_synonyms(self, w1, w2): if w1 not in self.parents: self.parents[w1] = w1 if w2 not in self.parents: self.parents[w2] = w2 w1_root = self.get_root(w1) w2_root = self.get_root(w2) if w1_root < w2_root: w1_root, w2_root = w2_root, w1_root self.parents[w2_root] = w1_root def are_synonymous(self, w1, w2): return self.get_root(w1) == self.get_root(w2) 

इस संरचना का उपयोग करके, आप समानार्थक शब्द को पूर्व-प्रक्रिया कर सकते हैं और रैखिक समय में समस्या को हल कर सकते हैं।

रेटिंग और नोट्स

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

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

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

• समस्या के बयान का विश्लेषण करें और निर्धारित करें कि यह स्पष्ट रूप से तैयार नहीं है , एक अस्पष्ट सूत्रीकरण विकसित करें। इसे जारी रखें जैसा कि आप हल करते हैं और नए प्रश्न उठते हैं। अधिकतम दक्षता के लिए, इन कार्यों को जितनी जल्दी हो सके निष्पादित करें, क्योंकि आगे काम चला गया है, त्रुटि को ठीक करने में अधिक समय लगेगा।
  
• , . , .
  
• . , , .
  
• , . , continue , , .
  
• , : , , , . , , , .
  
• . — , . — .

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

भविष्य की योजना

जैसा कि आप समझ सकते हैं, कार्य अंततः जनता को ज्ञात हो गया । तब से, मैंने कई अन्य प्रश्नों का उपयोग किया है, जो कि पिछले साक्षात्कारकर्ताओं द्वारा पूछे गए और मेरे मूड पर निर्भर करता है (एक प्रश्न हर समय उबाऊ है)। मैं अभी भी कुछ प्रश्नों का उपयोग करता हूं, इसलिए मैं उन्हें गुप्त रखूंगा, लेकिन कुछ नहीं! आप उन्हें निम्नलिखित लेखों में पा सकते हैं।

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

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

पढ़ने के लिए धन्यवाद!

पुनश्च: आप में सभी लेख के कोड की जांच कर सकते हैं भंडार GitHub या उन लोगों के साथ रहते हैं खेलने से मेरे अच्छे दोस्त के लिए धन्यवाद repl.it ।