सबसे महत्वपूर्ण डेटा संरचनाएं आपको अपने प्रोग्रामिंग साक्षात्कार के बारे में पता होना चाहिए

स्विस कंप्यूटर वैज्ञानिक, निकोलस विर्थ ने 1976 में एक पुस्तक लिखी जिसका नाम अल्गोरिद्म + डेटा स्ट्रक्चर्स = प्रोग्राम है ।

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

लगभग सभी कार्यों में, एक उम्मीदवार को डेटा संरचनाओं की गहरी समझ की आवश्यकता होती है। इसी समय, यह इतना महत्वपूर्ण नहीं है कि आप स्नातक हैं (विश्वविद्यालय या प्रोग्रामिंग पाठ्यक्रमों से स्नातक हैं), या आपके पास दसियों वर्ष का अनुभव है।

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

डेटा संरचनाओं का अध्ययन करना एक अनिवार्य व्यवसाय है, भले ही आप अपनी वर्तमान नौकरी में पेशेवर रूप से सुधार करने की कोशिश कर रहे हों। आइए बुनियादी बातों से शुरू करें।

Alconost में अनुवादित

डेटा संरचना क्या है?

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

हमें डेटा संरचनाओं की आवश्यकता क्यों है?

चूंकि डेटा संरचनाओं का उपयोग सूचना को व्यवस्थित तरीके से संग्रहीत करने के लिए किया जाता है, और डेटा कंप्यूटर विज्ञान में सबसे महत्वपूर्ण घटना है, डेटा संरचनाओं का सही मूल्य स्पष्ट है।

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

विशिष्ट परिदृश्य के आधार पर, डेटा को एक उपयुक्त प्रारूप में संग्रहीत किया जाना चाहिए। हमारे पास हमारे निपटान में कई डेटा संरचनाएं हैं जो हमें ऐसे विभिन्न स्वरूपों के साथ प्रदान करती हैं।

सामान्य डेटा संरचनाएँ

सबसे पहले, आइए सबसे सामान्य डेटा संरचनाओं को सूचीबद्ध करते हैं, और फिर बदले में प्रत्येक को पार्स करते हैं:

1. सरणियों
2. ढेर
3. कतारों
4. लिंक की गई सूची
5. पेड़
6. गिनता
7. बर्स (संक्षेप में, ये भी पेड़ हैं, लेकिन उन्हें अलग से माना जाना चाहिए)।
8. हैश टेबल

सरणियों

एक सरणी सबसे सरल और सबसे आम डेटा संरचना है। अन्य डेटा संरचनाएं, जैसे कि स्टैक और कतार, सरणियों से ली गई हैं।

यहाँ दिखाया गया है आकार का एक सरल सरणी 4 युक्त तत्व (1, 2, 3 और 4)।

प्रत्येक डेटा आइटम को एक पॉजिटिव न्यूमेरिक मान असाइन किया जाता है, जिसे इंडेक्स कहा जाता है और यह एरे में इस आइटम की स्थिति के अनुसार होता है। अधिकांश प्रोग्रामिंग भाषाओं में, सरणी में तत्व 0 से गिने जाते हैं।

दो प्रकार के सरणियाँ हैं:

• एक आयामी (जैसे ऊपर दिखाया गया है)
• बहुआयामी (ऐसे सरणियाँ जिनमें अन्य सरणियाँ सन्निहित हैं)

सबसे सरल सरणी ऑपरेशन

• सम्मिलित करें - दिए गए सूचकांक के साथ एक स्थिति में एक तत्व डालें
• प्राप्त करें - दिए गए सूचकांक के साथ एक स्थिति पर कब्जा करने वाला तत्व लौटाएं
• हटाएं - निर्दिष्ट सूचकांक के साथ आइटम को हटा दें
• आकार - सरणी में तत्वों की कुल संख्या प्राप्त करें

साक्षात्कार अक्सर पूछे जाने वाले प्रश्न

• दूसरा न्यूनतम सरणी तत्व खोजें
• किसी सरणी में गैर-दोहराए जाने वाले पूर्णांक खोजें
• दो क्रमबद्ध सरणियों को मर्ज करें
• किसी सरणी में सकारात्मक और नकारात्मक मानों को पुन: व्यवस्थित करें

ढेर

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

स्टैक की तुलना पुस्तकों के उच्च स्टैक से की जा सकती है। यदि आपको स्टैक के केंद्र के पास पड़ी हुई पुस्तक की आवश्यकता है, तो आपको सबसे पहले उपरोक्त सभी पुस्तकों को निकालना होगा। यह कैसे LIFO सिद्धांत काम करता है (अंतिम बार, पहले जाओ)।

यह तीन डेटा तत्वों (1, 2 और 3) वाले स्टैक की तरह दिखता है, जहां 3 शीर्ष पर है - इसलिए इसे पहले हटा दिया जाएगा:

सबसे सरल स्टैक ऑपरेशन:

• पुश - शीर्ष पर स्टैक पर एक आइटम को धक्का देता है
• पॉप - स्टैक से हटाने के बाद शीर्ष वस्तु को लौटाता है
• isEmpty - यदि स्टैक खाली है तो सही है
• शीर्ष - स्टैक से हटाए बिना शीर्ष आइटम लौटाता है

साक्षात्कार स्टैक के बारे में अक्सर पूछे जाने वाले प्रश्न

• स्टैक का उपयोग करके पोस्टफ़िक्स अभिव्यक्ति की गणना करें
• ढेर पर क्रमबद्ध मूल्यों
• अभिव्यक्ति में संतुलित कोष्ठक की जाँच करें

कतारों

एक कतार, एक स्टैक की तरह, एक रैखिक डेटा संरचना है जिसमें तत्वों को अनुक्रमिक क्रम में संग्रहीत किया जाता है। स्टैक और कतार के बीच एकमात्र महत्वपूर्ण अंतर यह है कि कतार में, LIFO के बजाय, FIFO सिद्धांत लागू होता है (पहले आओ, पहले पाओ)।

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

यहां चार डेटा तत्वों (1, 2, 3 और 4) के साथ एक कतार की एक छवि है, जहां 1 पहले जाता है और पहले कतार छोड़ता है:

सरल कतार संचालन

• एन्क्यू () - पंक्ति के अंत में एक आइटम जोड़ता है
• Dequeue () - कतार के सामने से एक आइटम निकालता है
• isEmpty () - यदि कतार खाली है तो सही है
• शीर्ष () - कतार में पहला आइटम लौटाता है

साक्षात्कार अक्सर पूछे जाने वाले प्रश्न

• एक कतार का उपयोग करके एक स्टैक को लागू करें
• कतार में पहले k आइटम का भुगतान करें
• एक कतार का उपयोग करके 1 से n तक द्विआधारी संख्या उत्पन्न करें

लिंक की गई सूची

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

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

लिंक की गई सूची, फ़ाइल सिस्टम, हैश टेबल और आसन्न सूची का उपयोग करके कार्यान्वित किया जाता है।

यह है कि आप किसी लिंक की गई सूची की आंतरिक संरचना की कल्पना कैसे कर सकते हैं:


लिंक्ड सूची के प्रकार हैं:

• एकल लिंक सूची (यूनिडायरेक्शनल)
• संदेह से जुड़ी सूची (द्विदिश)

लिंक की गई सूचियों के साथ सबसे सरल ऑपरेशन हैं:

• InsertAtEnd - लिंक की गई सूची के अंत में निर्दिष्ट आइटम सम्मिलित करता है।
• InsertAtHead - लिंक किए गए सूची की शुरुआत (सिर से) में निर्दिष्ट तत्व सम्मिलित करता है
• हटाएं - लिंक की गई सूची से निर्दिष्ट आइटम हटाता है।
• DeleteAtHead - किसी लिंक की गई सूची में पहला आइटम हटाता है।
• खोज - लिंक की गई सूची से निर्दिष्ट आइटम लौटाता है।
• isEmpty - यदि लिंक की गई सूची खाली है तो सही है

साक्षात्कार अक्सर पूछे जाने वाले प्रश्न:

• लिंक की गई सूची का भुगतान करें
• लिंक की गई सूची में लूप ढूंढें
• लिंक की गई सूची के ऊपर से Nth नोड लौटाएं
• लिंक की गई सूची से डुप्लिकेट मान निकालें

गिनता

एक ग्राफ नेटवर्क के रूप में एक दूसरे से जुड़े नोड्स का एक सेट है। नोड्स को कोने भी कहा जाता है। जोड़ी (x, y) को बढ़त कहा जाता है, जिसका अर्थ है कि शीर्ष x , शीर्ष y से जुड़ा है। एक किनारे का वजन / लागत हो सकता है - एक संकेतक जो यह दर्शाता है कि शीर्ष x से वर्टेक्स y तक संक्रमण कितना महंगा है।


रेखांकन के प्रकार:

• अप्रत्यक्ष ग्राफ
• ओरिएंटेड ग्राफ़

प्रोग्रामिंग भाषा में, रेखांकन दो प्रकार के हो सकते हैं:

• आसन्न मैट्रिक्स
• आसन्न सूची

सामान्य ग्राफ़ ट्रैवर्सल एल्गोरिदम:

• व्यापक खोज
• गहराई खोज

साक्षात्कार अक्सर पूछे जाने वाले प्रश्न:

• चौड़ाई और गहराई खोजों को लागू करें
• जाँच करें कि ग्राफ एक पेड़ है या नहीं
• एक ग्राफ में किनारों की संख्या की गणना करें
• दो चोटियों के बीच सबसे छोटा रास्ता खोजें

पेड़

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

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

इस डेटा संरचना से जुड़ी एक साधारण ट्री आरेख और बुनियादी शब्दावली इस प्रकार है:


निम्नलिखित प्रकार के पेड़ मौजूद हैं:

• एन-ary पेड़
• संतुलित वृक्ष
• बाइनरी ट्री
• बाइनरी सर्च ट्री
• एवीएल पेड़
• लाल आबनूस
• 2-3 पेड़

उपरोक्त पेड़ों में से, बाइनरी ट्री और बाइनरी सर्च ट्री का सबसे अधिक उपयोग किया जाता है।

पेड़ों के बारे में अक्सर पूछे जाने वाले साक्षात्कार प्रश्न:

एक द्विआधारी पेड़ की ऊंचाई का पता लगाएं
बाइनरी सर्च ट्री में kth का अधिकतम मूल्य ज्ञात करें
रूट से "k" स्थित नोड का पता लगाएं
बाइनरी ट्री में दिए गए नोड के पूर्वजों का पता लगाएं

बोरान

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

यह तीन शब्द "शीर्ष" (शीर्ष), "इस प्रकार" (इसलिए), और "उनके" (उन्हें) जंगल में संग्रहीत हैं:


शब्दों को ऊपर से नीचे तक व्यवस्थित किया गया है, और हरे रंग के नोड्स "पी", "एस" और "आर" पूर्ण, क्रमशः, शब्द "टॉप", "इस प्रकार" और "उनके"।

अक्सर पूछे जाने वाले साक्षात्कार के बारे में प्रश्न:

• देवदार के जंगल में संग्रहीत शब्दों की कुल संख्या की गणना करें
  
• जंगल में संग्रहीत सभी शब्दों को प्रदर्शित करें।
  
• बोरान का उपयोग करके सरणी तत्वों को सॉर्ट करें
  
• बोरॉन का उपयोग करके शब्दावली शब्दों का निर्माण करें
  
• T9 शब्दकोश बनाएँ
  

हैश टेबल

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

एक नियम के रूप में, हैश टेबल को सरणियों का उपयोग करके लागू किया जाता है।

हैशेड डेटा संरचना का प्रदर्शन निम्नलिखित तीन कारकों पर निर्भर करता है:

• हैश फंक्शन
• हैश टेबल का आकार
• टक्कर प्रसंस्करण विधि

निम्नलिखित दिखाता है कि कैसे हैश एक सरणी में मैप करता है। इस सरणी के सूचकांक की गणना हैश फ़ंक्शन का उपयोग करके की जाती है।

साक्षात्कार अक्सर पूछे जाने वाले हैश प्रश्न:

• एक सरणी में सममित जोड़े खोजें
• पूरा रास्ता ट्रैक करें
• खोजें कि क्या एक सरणी दूसरे सरणी का सबसेट है
• जाँच करें कि क्या सरणियाँ अस्वीकृत हैं

उपरोक्त आठ सबसे महत्वपूर्ण डेटा संरचनाओं का वर्णन करता है जो आपको प्रोग्रामिंग साक्षात्कार में जाने से पहले निश्चित रूप से जानना आवश्यक है।

गुड लक और दिलचस्प सीखने! :)

अनुवादक के बारे में

लेख का अनुवाद अल्कोनोस्ट ने किया था।

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

हम विज्ञापन और प्रशिक्षण वीडियो भी बनाते हैं - Google Play और ऐप स्टोर के लिए बिक्री, छवि, विज्ञापन, प्रशिक्षण, टीज़र, खोजकर्ता, ट्रेलरों के लिए।

अधिक जानकारी