एक मामूली साक्षात्कार गाइड: भाग 1

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

• डेटा संरचनाएं
• एल्गोरिदम और "अवधारणाएं"
• प्रोग्रामिंग भाषा

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

डेटा संरचनाएं

• ऐरे और स्ट्रिंग्स
• संबंधित सूची
• ढेर और कतार
• पेड़ और रेखांकन

एल्गोरिदम और "अवधारणाएं"

• क्रमबद्ध करें और खोजें
• प्रत्यावर्तन
• बिट हेरफेर
• ऑब्जेक्ट ओरिएंटेड डिज़ाइन

प्रोग्रामिंग भाषा

• मूल घटक
• "होम" परियोजनाओं को पूरा किया
• जितना संभव हो

और अब अलमारियों पर, क्या, कैसे और क्यों?

डेटा संरचनाएं

ऐरे और स्ट्रिंग्स

प्रश्न जो "स्थिति" का एक सामान्य विचार देते हैं:
" एक फ़ंक्शन लागू करें जो यह निर्धारित करता है कि क्या सभी वर्ण किसी दिए गए स्ट्रिंग में गैर-दोहरा रहे हैं ।"
सादगी के लिए, कल्पना करें कि एक ASCII वर्ण सेट है (यदि नहीं, तो आपको "कंटेनर" का आकार बदलने की आवश्यकता होगी, तर्क किसी भी तरह से नहीं बदलेगा)।

bool are_unique_characters(const std::string& str) { std::vector<bool> char_set(256, false); for (int i = 0; i < str.size(); ++i) { int val = str.at(i); if (char_set[val]) { return false; } char_set[val] = true; } return true; } 

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

 bool are_unique_characters(const std::string& str) { int checker = 0; for (int i = 0; i < str.size(); ++i) { int val = str.at(i) - 'a'; if ((checker & (1 << val)) > 0) { return false; } checker |= (1 << val); } return true; } 

प्रतिबिंब के लिए, यह क्लासिक कार्य है: " सी-लाइन को चालू करें (जिसका अर्थ है कि" abcd "पाँच वर्ण हैं, पाँचवाँ समाप्ति शब्द null वर्ण '\ 0' है) ।"
इसके साथ अपने निर्णय की तुलना करें और प्रश्न का उत्तर दें, आपका कोड बेहतर क्यों है?

 void reverse_c_string(char* str) { char* end = str; char tmp; if (str) { while (*end) { ++end; } --end; while (str < end) { tmp = *str; *str++ = *end; *end-- = tmp; } } } 

होमवर्क के रूप में, इस समस्या को हल करने का प्रयास करें: “आपको एक NxN सरणी के रूप में एक छवि दी गई है, जहां प्रत्येक तत्व एक पिक्सेल है और प्रत्येक पिक्सेल का वजन 4 बाइट होता है। एक फ़ंक्शन लिखें जो छवि को 90 डिग्री पर फ़्लिप करता है । ”

संबंधित सूची

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

कार्यों के उदाहरण:
" डुप्लिकेट आइटमों को एक लिंक न की गई सूची से हटाने के लिए कोड लिखें ।"
होने

 struct list_node { int data; list_node* next; }; 

समाधान इस तरह होगा (और तुम्हारा?):

 void delete_duplicates(list_node* head) { if (NULL == head) { return; } list_node* previous = head; list_node* current = previous->next; while (NULL != current) { list_node* runner = head; while (runner != current) { if (runner->data == current->data) { list_node* tmp = current->next; previous->next = tmp; current = tmp; break; } runner = runner->next; } if (runner == current) { previous = current; current = current->next; } } } 

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

 bool delete_node(list_node* nd) { if (NULL == nd || NULL == nd->next) { return false; // whatta..? } list_node* nxt = nd->next; nd->data = nxt->data; nd->next = nxt->next; return true; } 

उर्फ होमवर्क के बारे में सोचने के लिए प्रश्न:
" आपके पास लिंक की गई सूची के रूप में प्रस्तुत दो नंबर हैं, जहां प्रत्येक नोड में एक अंक होता है। संख्याएं रिवर्स ऑर्डर में संग्रहीत की जाती हैं। एक फ़ंक्शन लिखें जो इन संख्याओं के योग को घटाता है और लिंक की गई सूची के रूप में वापस लौटता है।
उदाहरण: संख्या 295 और 513 के लिए हमें कुल 808 मिले।
इनपुट: (5 -> 9 -> 2), (3 -> 1 -> 5)
बाहर निकलें: (8 -> 0 -> 8) । "

" लिंक की गई सूची के मध्य का पता लगाएं ।"

ढेर और कतार

आवश्यक ज्ञान स्टैक और कतार को लागू करने की क्षमता है। लागू वर्ग विधियों में सभी इनपुट मूल्यों और "सीमा मामलों" की जांच करना याद रखें।

" एक वर्ग my_queue लिखें जो दो स्टैक का उपयोग करके कतार को लागू करता है ।"
" नीचे पिछली समस्या का समाधान है, इस कोड में क्या गलत है? "

 template <typename T> class my_queue { private: std::stack<T> m_stack1; std::stack<T> m_stack2; int size() const { return m_stack1.size() + m_stack2.size(); } void add(const T& value) { m_stack1.push(value); } T peek() { if (!m_stack2.empty()) { return m_stack2.top(); } while (!m_stack1.empty()) { m_stack2.push(m_stack1.top()); m_stack1.pop(); } return m_stack2.top(); } T remove() { if (!m_stack2.empty()) { T tmp = m_stack2.top(); m_stack2.pop(); return tmp; } while (!m_stack1.empty()) { m_stack2.push(m_stack1.top()); m_stack1.pop(); } return m_stack2.top(); } }; 

विचार के लिए:
" एक प्रोग्राम लिखें जो स्टैक को आरोही क्रम में क्रमबद्ध करता है ।"

पेड़ और रेखांकन

पेड़ों और रेखांकन पर प्रश्न मुख्य रूप से निम्नलिखित रूपों में "उपलब्ध" हैं:

• पेड़ को लागू करें / नोड ढूंढें / नोड / अन्य महत्वपूर्ण एल्गोरिदम को हटा दें
• एक प्रसिद्ध एल्गोरिथ्म के संशोधित संस्करण को लागू करें

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

• डायरेक्ट ट्री वॉक (प्री-ऑर्डर)
• सममित बायपास (इन-ऑर्डर)
• रिवर्स बाईपास (पोस्ट-ऑर्डर)
• नोड डालें

ग्राफ अनिवार्य ज्ञान:

• गहराई पहली खोज
• चौड़ाई पहली खोज

" एक क्रमबद्ध (आरोही क्रम में) सरणी को देखते हुए, एक एल्गोरिथ्म लिखें जो न्यूनतम ऊंचाई का एक द्विआधारी वृक्ष बनाता है ।"
एल्गोरिथ्म:

1. सरणी के मध्य तत्व को पेड़ में डालें
2. "बाईं सबर्रे" के तत्वों को "बाएं सबट्री में" डालें
3. "राइट सबर्रे" के तत्वों को (सही सबट्री में) डालें
4. और इसलिए पुनरावृत्ति

 tree_node* add_to_tree(int arr[], int start, int end) { if (end < start) { return NULL; } int mid = (start + end) / 2; tree_node* n = new tree_node(arr[mid]); n->left = add_to_tree(arr, start, mid - 1); n->right = add_to_tree(arr, mid + 1, end); return n; } tree_node* create_min_BST(int arr[]) { //... SIZE   //... arr   return add_to_tree(arr, 0, SIZE - 1); } 

विचार के लिए:
" गैर-पुनरावर्ती सममित ट्री वॉक लागू करें ।"

UPD : जैसा कि शेडल ने उल्लेख किया है, यह मार्गदर्शिका छात्रों ( कनिष्ठों ) के लिए है।

UPD 2 : भाग दो