डेटा स्ट्रक्चर्स और एल्गोरिदम
मुख्य डेटा स्ट्रक्चर्स, एल्गोरिदमिक तकनीकें, और ग्राफ़ एल्गोरिदम, तकनीकी इंटरव्यू की तैयारी और समकक्ष अंडरग्रेजुएट कोर्सवर्क के लिए।
एक क्विक डायग्नॉस्टिक लें
सभी 32 टॉपिक्स
हर वह स्किल जिसे डायग्नोस्टिक जाँच सकता है, नक्शे की तरह समूहों में। लेसन शुरू करने के लिए कोई भी टॉपिक खोलें।
बुनियादी सिद्धांत
- कॉम्प्लेक्सिटी एनालिसिस: Big-O का इस्तेमाल करके यह बताना कि इनपुट साइज़ बढ़ने पर किसी एल्गोरिदम का रनिंग टाइम या मेमोरी कैसे बढ़ती है।
- रिकर्शन: एक फ़ंक्शन जो किसी समस्या को उसी समस्या के छोटे रूप पर खुद को बुलाकर हल करता है।
लीनियर स्ट्रक्चर्स
- ऐरे: मेमोरी का एक तय-लेआउट, सटीक ब्लॉक जहाँ कोई भी इंडेक्स कॉन्स्टेंट टाइम में मिल जाता है।
- लिंक्ड लिस्ट: मेमोरी में बिखरे हुए नोड्स, हर एक अगले की ओर इशारा करता है, तेज़ इंडेक्सिंग की जगह सस्ती इंसर्शन देते हुए।
- स्टैक और क्यू: दो सीमित-एक्सेस क्रम, लास्ट-इन-फ़र्स्ट-आउट और फ़र्स्ट-इन-फ़र्स्ट-आउट।
सर्चिंग और सॉर्टिंग
- बाइनरी सर्च: एक क्रमबद्ध रेंज को बार-बार आधा करके लॉगरिदमिक समय में टारगेट ढूंढना।
- बुनियादी तुलना-आधारित सॉर्ट: साधारण O(n स्क्वायर) सॉर्ट, बबल, इंसर्शन, सिलेक्शन, जो एलिमेंट्स के जोड़ों की तुलना और अदला-बदली करते हैं।
- डिवाइड-एंड-कॉन्कर सॉर्टिंग: डिवाइड-एंड-कॉन्कर सॉर्ट, मर्ज सॉर्ट और क्विकसॉर्ट, जो समस्या को बांटकर O(n स्क्वायर) से बेहतर करते हैं।
- नॉन-कम्पैरिज़न सॉर्टिंग: तुलना की बजाय वैल्यूज़ में मौजूद ज्ञात संरचना का फ़ायदा उठाकर सॉर्ट करना, जैसे काउंटिंग या रैडिक्स सॉर्ट।
हैशिंग
- हैश टेबल: हैश फ़ंक्शन के ज़रिए keys को ऐरे के स्लॉट्स से मैप करना, ताकि लगभग कॉन्स्टेंट-टाइम लुकअप मिल सके।
ट्रीज़
- बाइनरी ट्री: एक पदानुक्रमित संरचना जहाँ हर नोड के ज़्यादा से ज़्यादा दो बच्चे होते हैं।
- बाइनरी सर्च ट्री: एक बाइनरी ट्री जिसे इस तरह क्रमबद्ध रखा जाता है कि हर नोड का बायाँ सबट्री छोटा और दायाँ सबट्री बड़ा हो।
- बैलेंस्ड सर्च ट्री: एक BST जो खुद को सक्रिय रूप से बैलेंस करता है, AVL रोटेशन या रेड-ब्लैक कलरिंग के ज़रिए, ताकि यह कभी एक सीधी लाइन में न बदल जाए।
- हीप और प्रायोरिटी क्यू: एक ट्री जैसी संरचना जो हमेशा सबसे छोटे, या सबसे बड़े, एलिमेंट को जल्दी ढूंढने लायक रखती है।
- ट्राइज़: एक ट्री जहाँ रूट से हर पथ एक प्रीफ़िक्स को दर्शाता है, स्ट्रिंग की तेज़ खोज के लिए बनाया गया।
ग्राफ़्स
- ग्राफ़ रिप्रेजेंटेशन: किसी ग्राफ़ के वर्टिसेज़ और एज को एडजेसेंसी मैट्रिक्स या एडजेसेंसी लिस्ट के तौर पर स्टोर करना।
- ग्राफ़ ट्रैवर्सल (BFS और DFS): हर पहुँच योग्य वर्टेक्स को या तो लेवल दर लेवल (BFS) या पहले गहराई में जाकर (DFS) विज़िट करना।
- टोपोलॉजिकल सॉर्ट: एक डायरेक्टेड एसाइक्लिक ग्राफ़ के वर्टिसेज़ को इस तरह क्रमबद्ध करना कि हर एज आगे की ओर इशारा करे।
- यूनियन-फ़ाइंड: एक संरचना जो ट्रैक रखती है कि कौन से एलिमेंट एक ही ग्रुप में हैं और ग्रुपों को तेज़ी से मर्ज करती है।
- डाइक्स्ट्रा एल्गोरिदम: जब कोई एज वेट नेगेटिव न हो, तब एक वर्टेक्स से बाकी सबतक सबसे सस्ता रास्ता ढूंढना।
- बेलमैन-फ़ोर्ड एल्गोरिदम: सबसे छोटे रास्ते ढूंढना जो तब भी काम करता है जब कुछ एज वेट नेगेटिव हों, बस स्पीड की कीमत पर।
- मिनिमम स्पैनिंग ट्री: एज का वह सबसे सस्ता सेट जो बिना किसी साइकल के हर वर्टेक्स को जोड़ता है।
एडवांस्ड स्ट्रक्चर्स
- सेगमेंट ट्री: एक ऐरे पर बना बाइनरी ट्री जो रेंज क्वेरीज़ का, जैसे सम या मिनिमम, लॉगरिदमिक समय में जवाब देता है।
- फेनविक ट्री: एक कॉम्पैक्ट, ऐरे-आधारित संरचना जो प्रीफ़िक्स-सम क्वेरीज़ का लॉगरिदमिक समय में जवाब देती है।
तकनीकें
- डिवाइड एंड कॉन्कर: किसी समस्या को उसी की छोटी, स्वतंत्र कॉपियों में बांटना, हर एक को हल करना, फिर उन्हें मिलाना।
- ग्रीडी एल्गोरिदम: हर कदम पर स्थानीय रूप से सबसे अच्छा विकल्प चुनना, यह भरोसा करते हुए कि यह वैश्विक स्तर पर सबसे अच्छे जवाब तक ले जाएगा।
- डायनामिक प्रोग्रामिंग: ओवरलैपिंग सबप्रॉब्लम्स के जवाबों को दोबारा निकालने की बजाय कैश करके किसी समस्या को हल करना।
- बैकट्रैकिंग: एक विकल्प आज़माना, रिकर्स करना, और अगर वह कहीं नहीं ले जाता तो उसे पलटना, ताकि सभी संभावनाएं देखी जा सकें।
- टू पॉइंटर्स: नेस्टेड लूप से बचने के लिए एक सीक्वेंस में एक साथ दो इंडेक्स चलाना।
- स्लाइडिंग विंडो: एक ही पास में किसी चल रही शर्त को ट्रैक करने के लिए किसी सीक्वेंस पर एक सटीक रेंज को बढ़ाना और घटाना।
- बिट मैनिपुलेशन: किसी संख्या के अलग-अलग बाइनरी बिट्स को सीधे इस्तेमाल करना, जैसे कोई छोटा सेट दिखाने या कोई फ़्लैग टॉगल करने के लिए।
स्ट्रिंग्स