नौकरी के साक्षात्कार एल्गोरिथ्म अवलोकन - सेट जनरेशन

नमस्कार, हेब्र!

यह पोस्ट एल्गोरिदम के अनुसार कार्यों का विश्लेषण शुरू करता है जो बड़ी आईटी कंपनियों (Mail.Ru Group, Google, आदि) को साक्षात्कार के लिए उम्मीदवार देने के लिए पसंद है (यदि एल्गोरिदम के साथ साक्षात्कार अच्छा नहीं है, तो एक सपने की कंपनी में नौकरी पाने की संभावना, अफसोस शून्य हो जाते हैं)। सबसे पहले, यह पोस्ट उन लोगों के लिए उपयोगी है, जिनके पास ओलंपियाड प्रोग्रामिंग या शाद या एलकेएस जैसे भारी पाठ्यक्रमों का अनुभव नहीं है, जिसमें एल्गोरिदम के विषयों को गंभीरता से लिया जाता है, या उन लोगों के लिए जो एक निश्चित क्षेत्र में अपने ज्ञान को ताज़ा करना चाहते हैं।

इसी समय, यह तर्क नहीं दिया जा सकता है कि यहां निपटाए जाने वाले सभी कार्यों को साक्षात्कार में निश्चित रूप से पूरा किया जाएगा, हालांकि, ऐसे कार्यों को हल करने वाले दृष्टिकोण ज्यादातर मामलों में समान हैं।

विवरण को विभिन्न विषयों में विभाजित किया जाएगा, और हम एक विशिष्ट संरचना के साथ सेट उत्पन्न करके शुरू करेंगे।

1. चलो बटन समझौते के साथ शुरू करते हैं: आपको एक ही प्रकार के ब्रैकेट ( क्या सही ब्रैकेट अनुक्रम है ) के साथ सभी सही ब्रैकेट अनुक्रम उत्पन्न करने की आवश्यकता है, जहां कोष्ठक की संख्या k है।

इस समस्या को कई तरीकों से हल किया जा सकता है। चलो पुनरावर्ती के साथ शुरू करते हैं।

यह विधि मानती है कि हम एक खाली सूची से अनुक्रमों पर पुनरावृति करना शुरू कर रहे हैं। ब्रैकेट (खुलने या बंद होने) को सूची में जोड़ने के बाद, पुन: कॉल किया जाता है और शर्तों की जाँच की जाती है। क्या शर्तें हैं? ब्रैकेट्स को खोलने और बंद करने के बीच अंतर की निगरानी करना आवश्यक है ( cnt वैरिएबल) - यदि आप यह अंतर पॉजिटिव नहीं है, तो आप लिस्ट में क्लोजिंग ब्रैकेट नहीं जोड़ सकते, अन्यथा ब्रैकेट अनुक्रम सही नहीं रहेगा। कोड में इसे सावधानीपूर्वक लागू करना बाकी है।

 k = 6 #   init = list(np.zeros(k)) #  ,    cnt = 0 #    ind = 0 # ,       def f(cnt, ind, k, init): #  . ,     if (cnt <= k-ind-2): init[ind] = '(' f(cnt+1, ind+1, k, init) # .    ,  cnt > 0 if cnt > 0: init[ind] = ')' f(cnt-1, ind+1, k, init) #      if ind == k: if cnt == 0: print (init) 

इस एल्गोरिथ्म की जटिलता है $$$O ((C_k ^ {k / 2} - C_k ^ {k / 2 -1}) * k)$अतिरिक्त मेमोरी की आवश्यकता है $$$O (k)$।

दिए गए मापदंडों के साथ, फ़ंक्शन कॉल करता है $$$f (cnt, ind, k, init)$निम्नलिखित उत्पादन होगा:

इस समस्या को हल करने के लिए एक पुनरावृत्ति तरीका: इस मामले में, विचार मौलिक रूप से अलग होगा - आपको ब्रैकेट अनुक्रमों के लिए लेक्सिकोग्राफिक ऑर्डर की अवधारणा को पेश करने की आवश्यकता है।

एक प्रकार के कोष्ठक के लिए सभी सही लघुकोष्ठक अनुक्रमों को इस तथ्य को ध्यान में रखते हुए आदेश दिया जा सकता है कि $$$’('<’) ’$। उदाहरण के लिए, n = 6 के लिए, सबसे शाब्दिक रूप से निचला क्रम है $$$((()))$और सबसे पुराना - $$$() ()$।

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

मेरी राय में, यह दृष्टिकोण पुनरावर्ती की तुलना में थोड़ा नीच है, लेकिन इसका उपयोग जनरेटिंग सेट की अन्य समस्याओं को हल करने के लिए किया जा सकता है। हम इसे कोड में लागू करते हैं।

 #  ,    n = 6 arr = ['(' for _ in range(n//2)] + [')' for _ in range(n//2)] def f(n, arr): #    print (arr) while True: ind = n-1 cnt = 0 #  . ,    while ind>=0: if arr[ind] == ')': cnt -= 1 if arr[ind] == '(': cnt += 1 if cnt < 0 and arr[ind] =='(': break ind -= 1 #   ,     if ind < 0: break #   .  arr[ind] = ')' #      for i in range(ind+1,n): if i <= (n-ind+cnt)/2 +ind: arr[i] = '(' else: arr[i] = ')' print (arr) 

इस एल्गोरिथ्म की जटिलता पिछले उदाहरण के समान है।

वैसे, एक सरल विधि है जो दर्शाती है कि किसी दिए गए n / 2 के लिए उत्पन्न ब्रैकेट अनुक्रम की संख्या कैटलन संख्याओं से मेल खाना चाहिए।

यह काम करता है!

महान, अब के लिए कोष्ठक के साथ, चलो सबसेट बनाने के लिए आगे बढ़ते हैं। एक सरल पहेली के साथ शुरू करते हैं।

2. संख्याओं के साथ आरोही क्रम सरणी को देखते हुए $$$0$को $$$n-1$, यह अपने सभी सबसेट उत्पन्न करने के लिए आवश्यक है।

ध्यान दें कि इस तरह के एक सेट के सबसेट की संख्या बिल्कुल है $$$2 ^ एन$। यदि प्रत्येक सबसेट को सूचकांकों की एक सरणी के रूप में दर्शाया जाता है, जहां $$$0$इसका मतलब है कि तत्व सेट में शामिल नहीं है, लेकिन $$$1$- क्या शामिल है, तो ऐसी सभी सरणियों की पीढ़ी सभी सबसेट की पीढ़ी होगी।

यदि हम 0 से संख्याओं के बिटवाइज़ प्रतिनिधित्व पर विचार करते हैं $$$2 ^ n - 1$, तो वे वांछित सबसेट को निर्दिष्ट करेंगे। यही है, समस्या को हल करने के लिए, एक बाइनरी संख्या के लिए एकता के अतिरिक्त को लागू करना आवश्यक है। हम सभी शून्य से शुरू करते हैं और एक सरणी के साथ समाप्त होते हैं जिसमें एक इकाइयाँ होती हैं।

 n = 3 B = np.zeros(n+1) #  B   1  (    ) a = np.array(list(range(n))) #   def f(B, n, a): #   while B[0] == 0: ind = n #     while B[ind] == 1: ind -= 1 #   1 B[ind] = 1 #      B[(ind+1):] = 0 print (a[B[1:].astype('bool')]) 

इस एल्गोरिथ्म की जटिलता है $$$O (n * 2 ^ n)$, मेमोरी से - $$$O (n)$।

अब पिछले कार्य को थोड़ा जटिल करते हैं।

3. संख्याओं के साथ आरोही क्रम में एक क्रमबद्ध सरणी को देखते हुए $$$0$को $$$n-1$, आपको यह सब उत्पन्न करने की आवश्यकता है $$$k$-सीमेंट सब्मिट (पुनरावृत्त हल)।

मैं ध्यान देता हूं कि इस समस्या का सूत्रीकरण पिछले एक के समान है और इसे लगभग एक ही पद्धति का उपयोग करके हल किया जा सकता है: प्रारंभिक सरणी को साथ ले जाएं $$$k$इकाइयों और $$$एन-के$शून्य और क्रमिक रूप से लंबाई के ऐसे अनुक्रमों के सभी प्रकारों के माध्यम से $$$एन$

हालांकि, मामूली बदलाव की आवश्यकता है। हमें हर चीज को छांटने की जरूरत है $$$k$से संख्याओं का सेट सेट $$$0$को $$$n-1$। आपको यह समझने की आवश्यकता है कि आपको सबसेट के माध्यम से कैसे सॉर्ट करना है। इस मामले में, हम ऐसे सेटों के लिए लेक्सिकोग्राफिक ऑर्डर की अवधारणा को पेश कर सकते हैं।

हम वर्ण कोड द्वारा अनुक्रम की व्यवस्था भी करते हैं: $$$1 <0$(यह, ज़ाहिर है, अजीब है, लेकिन यह आवश्यक है, और अब हम समझेंगे कि क्यों)। उदाहरण के लिए, के लिए $$$n = 4, k = 2$सबसे कम उम्र और सबसे पुराना अनुक्रम होगा $$$[1,1,0,0]$और $$$[0,0,1,1]$।

यह समझना बाकी है कि एक क्रम से दूसरे क्रम में संक्रमण का वर्णन कैसे किया जाए। यहां सब कुछ सरल है: यदि हम बदलते हैं $$$1$पर $$$0$, फिर बाईं ओर हम स्थिति के संरक्षण को ध्यान में रखते हुए शाब्दिक रूप से न्यूनतम लिखते हैं $$$k$। कोड:

 n = 5 k = 3 a = np.array(list(range(n))) #    k -   init = [1 for _ in range(k)] + [0 for _ in range(nk)] def f(a, n, k, init): #   k-  print (a[a[init].astype('bool')]) while True: unit_cnt = 0 cur_ind = 0 #   ,     1 while (cur_ind < n) and (init[cur_ind]==1 or unit_cnt==0): if init[cur_ind] == 1: unit_cnt += 1 cur_ind += 1 #        -    if cur_ind == n: break #  init[cur_ind] = 1 #   . .  for i in range(cur_ind): if i < unit_cnt-1: init[i] = 1 else: init[i] = 0 print (a[a[init].astype('bool')]) 

कार्य उदाहरण:

इस एल्गोरिथ्म की जटिलता है $$$O (C_n ^ k * n)$, मेमोरी से - $$$O (n)$।

4. संख्याओं के साथ आरोही क्रम सरणी को देखते हुए $$$0$को $$$n-1$, आपको यह सब उत्पन्न करने की आवश्यकता है $$$k$-सीमेंट सबसेट (पुनरावर्ती हल करें)।

अब पुनरावृत्ति की कोशिश करते हैं। विचार सरल है: इस बार विवरण के बिना, कोड देखें।

 n = 5 a = np.array(list(range(n))) ind = 0 # ,       num = 0 # ,       k = 3 sub = list(-np.ones(k)) #  def f(n, a, num, ind, k, sub): #   k  ,     if ind == k: print (sub) else: for i in range(n - num): #  ,      k  if (n - num - i >= k - ind): #      sub[ind] = a[num + i] #     f(n, a, num+1+i, ind+1, k, sub) 

कार्य उदाहरण:

जटिलता पिछले पद्धति के समान है।

5. संख्याओं के साथ आरोही क्रम सरणी को देखते हुए $$$0$को $$$n-1$, यह अपने सभी क्रमपरिवर्तन उत्पन्न करने के लिए आवश्यक है।

हम पुनरावर्तन का उपयोग करके हल करेंगे। समाधान पिछले एक के समान है, जहां हमारे पास एक सहायक सूची है। यदि शुरू में यह शून्य है $$$मैं$-तत्त्व का एक स्थान है, तत्त्व $$$मैं$पहले से ही क्रमचय में। जल्दी से नहीं कहा:

 a = np.array(range(3)) n = a.shape[0] ind_mark = np.zeros(n) #   perm = -np.ones(n) #     def f(ind_mark, perm, ind, n): if ind == n: print (perm) else: for i in range(n): if not ind_mark[i]: #     ind_mark[i] = 1 #   perm[ind] = i f(ind_mark, perm, ind+1, n) #   -    ind_mark[i] = 0 

कार्य उदाहरण:

इस एल्गोरिथ्म की जटिलता है $$$O (n ^ 2 * n!)$, मेमोरी से - $$$O (n)।$

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

6. लंबाई एन के सभी दो आयामी ग्रे कोड उत्पन्न करें।

इस समस्या को हल करने का विचार अच्छा है, लेकिन यदि आप समाधान नहीं जानते हैं, तो यह सोचना बहुत मुश्किल हो सकता है। मैं ध्यान देता हूं कि इस तरह के दृश्यों की संख्या कितनी है $$$2 ^ एन$।

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

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

"कान से" यह समझना मुश्किल है; हम इस एल्गोरिथम के पुनरावृत्तियों को चित्रित करेंगे।

 n = 3 init = [list(np.zeros(n))] def f(n, init): for i in range(n): for j in range(2**i): init.append(list(init[2**i - j - 1])) init[-1][i] = 1.0 return init 

इस कार्य की जटिलता है $$$O (n * 2 ^ n)$, स्मृति से ही।

अब कार्य को जटिल करते हैं।

7. लंबाई n के सभी k- आयामी ग्रे कोड उत्पन्न करें।

यह स्पष्ट है कि पिछला कार्य इस कार्य का केवल एक विशेष मामला है। हालाँकि, उस खूबसूरत तरीके से जो पिछले कार्य को हल किया गया था, इसे हल नहीं किया जा सकता है, यहाँ सही क्रम में अनुक्रमों को क्रमबद्ध करना आवश्यक है। चलो एक दो आयामी सरणी प्राप्त करते हैं $$$k * n$। प्रारंभ में, अंतिम पंक्ति में इकाइयां होती हैं, और बाकी में शून्य होते हैं। इसके अलावा, मैट्रिक्स में, $$$-1$। यहां $$$1$और $$$-1$एक दूसरे से अलग दिशा में: $$$1$इशारा करता है $$$-1$नीचे इंगित करता है। महत्वपूर्ण: किसी भी समय प्रत्येक कॉलम में केवल एक ही हो सकता है $$$1$या $$$-1$, और शेष संख्या शून्य होगी।

अब हम समझेंगे कि ग्रे कोड प्राप्त करने के लिए इन अनुक्रमों को कैसे छांटना संभव है। तत्व को ऊपर ले जाने के लिए अंत से शुरू करें।

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

अब आप पहले कॉलम को नीचे ले जा सकते हैं। हम इसे तब तक हिलाते हैं जब तक कि यह फर्श से न टकराए। और इसी तरह, जब तक सभी तीर फर्श या छत से नहीं टकराते हैं और कोई भी स्तंभ नहीं बचा है जिसे स्थानांतरित किया जा सकता है।

हालाँकि, मेमोरी सेविंग के ढांचे में, हम लंबाई की दो एक आयामी सरणियों का उपयोग करके इस समस्या को हल करेंगे $$$एन$: एक सरणी में अनुक्रम के तत्व स्वयं झूठ बोलेंगे, और उनकी दिशा (तीर) के दूसरे भाग में।

 n,k = 3,3 arr = np.zeros(n) direction = np.ones(n) #   ,    def k_dim_gray(n,k): #    print (arr) while True: ind = n-1 while ind >= 0: #    ,    if (arr[ind] == 0 and direction[ind] == 0) or (arr[ind] == k-1 and direction[ind] == 1): direction[ind] = (direction[ind]+1)%2 else: break ind -= 1 #     ,     if ind < 0: break #    1 ,   1  arr[ind] += direction[ind]*2 - 1 print (arr) 

कार्य उदाहरण:

एल्गोरिथ्म की जटिलता है $$$O (n * k ^ n)$, मेमोरी से - $$$O (n)$।

इस एल्गोरिथ्म की शुद्धता पर प्रेरण द्वारा सिद्ध की जाती है $$$एन$, यहाँ मैं सबूतों का वर्णन नहीं करूँगा।

अगली पोस्ट में हम गतिकी के कार्यों का विश्लेषण करेंगे।