कोडिंग पैटर्न: साक्षात्कार तैयारी कोडिंग के लिए एक बेहतर दृष्टिकोण

साक्षात्कार कोडिंग के लिए तैयारी करना एक वास्तविक चुनौती हो सकती है क्योंकि डेवलपर्स अक्सर नई सामग्री की समीक्षा करने और सीखने में कई सप्ताह बिताते हैं।

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

आइए पारंपरिक कोडिंग साक्षात्कार तैयारी से जुड़ी कुछ समस्याओं पर करीब से नज़र डालें।

पारंपरिक साक्षात्कार तैयारी के नुकसान

पारंपरिक साक्षात्कार की तैयारी में सबसे आम कमियों में से एक "पीसने" की प्रथा है। इस दृष्टिकोण में स्पष्ट योजना या रणनीति के बिना यथासंभव अधिक से अधिक लीटकोड समस्याओं को हल करना शामिल है। हालाँकि यह एक उत्पादक रणनीति की तरह लग सकती है, लेकिन इसमें कई कमियाँ हैं।

जब आप संरचित दृष्टिकोण के बिना समस्याओं का समाधान करते हैं, तो हो सकता है कि आप अपनी कमजोरियों को पहचान न सकें। आपके अध्ययन के लिए कोई जानबूझकर योजना नहीं बनाई गई है; लक्ष्य केवल उतनी ही समस्याओं को हल करना है जितना आप कर सकते हैं। परिणामस्वरूप, आपको ऐसा महसूस हो सकता है कि आपने बहुत कुछ सीख लिया है, लेकिन आपके ज्ञान में महत्वपूर्ण अंतराल हो सकते हैं।

इसके अलावा, इसके साथ मुद्दा यह है कि यह अनिवार्य रूप से कई समस्याओं के समाधान याद रखने के इर्द-गिर्द घूमता है। सैकड़ों अलग-अलग कोडिंग समस्याओं के समाधान को याद रखने का प्रयास तब अप्रभावी साबित होता है जब साक्षात्कारकर्ता ऐसे प्रश्न प्रस्तुत करते हैं जो आपके द्वारा पहले सामना किए गए प्रश्नों से थोड़ा भी भिन्न होते हैं। इससे आप समस्या विविधताओं को संभालने के लिए तैयार नहीं महसूस कर सकते हैं।

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

इन चुनौतियों को देखते हुए, एक बेहतर तरीका होना चाहिए।

एक बेहतर तरीका: कोडिंग पैटर्न को अपनाना

तो, क्या साक्षात्कार की तैयारी के लिए कोडिंग का कोई अधिक प्रभावी और टिकाऊ तरीका है? इसका उत्तर कोडिंग पैटर्न को समझने और उनका उपयोग करने में निहित है।

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

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

याद रखें, बेहतर तैयारी करें, कठिन नहीं।

क्या उम्मीद करें?

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

हालाँकि मैं इस लेख में बहुत कुछ शामिल करता हूँ, यदि आप अधिक गहन प्रशिक्षण, स्पष्टीकरण और कोडिंग अभ्यास चाहते हैं, तो आप Techinterviews.io पर हमारे व्यापक कोडिंग साक्षात्कार तैयारी पाठ्यक्रम को देख सकते हैं। हम डेटा संरचना , व्यवहारिक साक्षात्कार और यहां तक कि वेतन वार्ता जैसे महत्वपूर्ण विषयों को भी कवर करते हैं।

आइए अब इन कोडिंग पैटर्न पर गौर करें।

1. लिंक्ड सूची उलटाव

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

किसी लिंक की गई सूची से निपटते समय यह उपयोगी होता है और बाधा इसे उसी स्थान पर उलटने की होती है।

किसी लिंक की गई सूची को उसी स्थान पर उलटने की प्रक्रिया इस प्रकार है:

1. तीन चर परिभाषित करके प्रारंभ करें: वर्तमान , पिछला और अगला । करंट को लिंक की गई सूची के प्रमुख के रूप में सेट करें, और पिछले और अगले को कोई नहीं के रूप में प्रारंभ करें।

2. जबकि वर्तमान चर कोई नहीं है, निम्नानुसार आगे बढ़ें:

   1. अगले नोड को एक अस्थायी चर में संग्रहीत करें।
   2. पिछले नोड को इंगित करने के लिए वर्तमान नोड के पॉइंटर को उल्टा करें।
   3. पिछले को वर्तमान नोड के रूप में और वर्तमान को अगले नोड के रूप में अद्यतन करें।

3. अंत में, उलटी सूची के शीर्ष को अंतिम नोड पर सेट करें, जो पिछले चर में संग्रहीत है।

महत्वपूर्ण संकेतक:

• आपको लिंक की गई सूची में तत्वों के क्रम को उलटना होगा।
• समस्याओं में लिंक्ड सूचियों में पैलिंड्रोम की जाँच करना शामिल है।
• आप सूची के भीतर एक विशिष्ट उपसूची में तत्वों के क्रम को उलटना चाहते हैं।

टेम्पलेट कोड:

अजगर

 def reverse_linked_list(head): curr = head prev = None while curr: next_node = curr.next curr.next = prev prev = curr curr = next_node return prev

जे एस

 function reverseLinkedList(head) { let curr = head; let prev = null; while (curr) { const nextNode = curr.next; curr.next = prev; prev = curr; curr = nextNode; } return prev; }

जावा

 public ListNode reverseLinkedList(ListNode head) { ListNode curr = head; ListNode prev = null; while (curr != null) { ListNode nextNode = curr.next; curr.next = prev; prev = curr; curr = nextNode; } return prev; }

2. संशोधित बाइनरी खोज

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

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

क्रमबद्ध डेटा संरचना में इस पैटर्न को कैसे लागू किया जाए, इसका विवरण यहां दिया गया है:

1. आरंभ और अंत स्थिति के बीच मध्यबिंदु की पहचान करके शुरुआत करें। संभावित पूर्णांक अतिप्रवाह से बचने के लिए, मध्य की गणना इस प्रकार करना अधिक सुरक्षित है: middle = start + (end - start) / 2
2. जांचें कि क्या कुंजी मध्य सूचकांक के तत्व से मेल खाती है। यदि ऐसा होता है, तो परिणाम के रूप में मध्य सूचकांक लौटाएँ।
3. यदि कुंजी मध्य सूचकांक के तत्व से मेल नहीं खाती है, तो अगले चरणों पर आगे बढ़ें।
4. मूल्यांकन करें कि क्या कुंजी सूचकांक मध्य में तत्व से कम है। यदि ऐसा है, तो अंत से मध्य - 1 तक अपडेट करके अपनी खोज सीमा को सीमित करें।
5. इसके विपरीत, यदि कुंजी सूचकांक मध्य में तत्व से बड़ी है, तो प्रारंभ को मध्य + 1 में अपडेट करके अपनी खोज सीमा को समायोजित करें।

महत्वपूर्ण संकेतक:

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

टेम्पलेट कोड:

अजगर

 def binary_search(arr: List[int], target: int) -> int: left, right = 0, len(arr) - 1 first_true_index = -1 # Perform binary search until left and right pointers meet while left <= right: mid = (left + right) // 2 if feasible(mid): # If the condition is true at mid index, update first_true_index first_true_index = mid right = mid - 1 else: # If the condition is false at mid index, narrow down the search space left = mid + 1 return first_true_index

जे एस

 function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; let firstTrueIndex = -1; // Perform binary search until left and right pointers meet while (left <= right) { const mid = Math.floor((left + right) / 2); if (feasible(mid)) { // If the condition is true at mid index, update firstTrueIndex firstTrueIndex = mid; right = mid - 1; } else { // If the condition is false at mid index, narrow down the search space left = mid + 1; } } return firstTrueIndex; }

जावा

 public int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - 1; int firstTrueIndex = -1; // Perform binary search until left and right pointers meet while (left <= right) { int mid = left + (right - left) / 2; if (feasible(mid)) { // If the condition is true at mid index, update firstTrueIndex firstTrueIndex = mid; right = mid - 1; } else { // If the condition is false at mid index, narrow down the search space left = mid + 1; } } return firstTrueIndex; }

3. दो सूचक

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

इस तकनीक का लाभ इसकी सादगी और दक्षता में निहित है, खासकर जब सरणी या स्ट्रिंग जैसी रैखिक डेटा संरचनाओं से निपटते समय आप शुरुआत में केवल एक पॉइंटर का उपयोग कर सकते हैं। दो पॉइंटर्स को नियोजित करके, आप अनावश्यक संचालन को रोक सकते हैं और रनटाइम दक्षता को महत्वपूर्ण रूप से बढ़ा सकते हैं, संभावित रूप से इसे O(n^2) से घटाकर O(n) कर सकते हैं।

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

यदि आप डेटा संरचना को पार करने के लिए एकाधिक पॉइंटर्स को नियोजित करते हैं, तो आप अपने दृष्टिकोण को "टू पॉइंटर्स" पैटर्न के अनुसार वर्गीकृत कर सकते हैं।

महत्वपूर्ण संकेतक:

• आपको विभिन्न स्थानों पर तत्वों की तुलना करने या उन पर काम करने की आवश्यकता है।
• समस्याओं के लिए क्रमबद्ध सरणी में तत्वों के जोड़े की खोज की आवश्यकता होती है।
• आप क्रमबद्ध सरणी से डुप्लिकेट को कुशलतापूर्वक हटाना चाहते हैं।
• रैखिक डेटा संरचनाओं (सरणियों, स्ट्रिंग्स, या लिंक की गई सूचियों) से निपटने और द्विघात समय जटिलता ( O(n^2) क्रूर बल समाधान) का सामना करते समय, दो पॉइंटर्स को नियोजित करने पर विचार करें।

टेम्पलेट कोड:

"विपरीत दिशा" भिन्नता के लिए टेम्पलेट

अजगर

 def two_pointers_opposite(arr): left = 0 right = len(arr) - 1 ans = 0 while left < right: # Perform logic using the left and right pointers if CONDITION: left += 1 else: right -= 1 return ans

जे एस

 function twoPointersOpposite(arr) { let left = 0; let right = arr.length - 1; let ans = 0; while (left < right) { // Perform logic using the left and right pointers if (CONDITION) { left++; } else { right--; } } return ans; }

जावा

 public int twoPointersOpposite(int[] arr) { int left = 0; int right = arr.length - 1; int ans = 0; while (left < right) { // Perform logic using the left and right pointers if (CONDITION) { left++; } else { right--; } } return ans; }

4. स्लाइडिंग विंडो

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

यह पैटर्न अक्सर विंडो के भीतर व्यक्तिगत डेटा की ट्रैकिंग की सुविधा के लिए हैश मैप का उपयोग करता है। हालाँकि, यह ध्यान रखना महत्वपूर्ण है कि इस दृष्टिकोण के परिणामस्वरूप O(n) की अंतरिक्ष-समय जटिलता हो सकती है।

महत्वपूर्ण संकेतक:

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

टेम्पलेट कोड:

अजगर

 def slidingWindow(nums): # Initialize necessary variables left = 0 window = [] # Initialize the window ans = 0 # Initialize the answer variable for right in range(len(nums)): window.append(nums[right]) # Expand the window to the right while invalid(window): # Condition to shrink the window from the left until it is valid again window.pop(0) # Remove the left element from the window left += 1 ans = max(ans, len(window)) # Update the answer, can vary on your implementation return ans

जे एस

 function slidingWindow(nums) { let left = 0; const window = []; // Initialize the window let ans = 0; // Initialize the answer variable for (let right = 0; right < nums.length; right++) { window.push(nums[right]); // Expand the window to the right while (invalid(window)) { // Condition to shrink the window from the left until it is valid again window.shift(); // Remove the left element from the window left++; } ans = Math.max(ans, window.length); // Update the answer , can vary on your implementation } return ans; }

जावा

 public static int slidingWindow(int[] nums) { int left = 0; List<Integer> window = new ArrayList<>(); // Initialize the window int ans = 0; // Initialize the answer variable for (int right = 0; right < nums.length; right++) { window.add(nums[right]); // Expand the window to the right while (invalid(window)) { // Condition to shrink the window from the left until it is valid again window.remove(0); // Remove the left element from the window left++; } ans = Math.max(ans, window.size()); // Update the answer , can vary on your implementation } return ans; }

5. शीर्ष K तत्व

इस पैटर्न में संग्रह में K के सबसे बड़े या सबसे छोटे तत्वों को ढूंढना शामिल है, जिसे अक्सर ढेर या प्राथमिकता कतार जैसी डेटा संरचनाओं का उपयोग करके कार्यान्वित किया जाता है। यह उनके मूल्य या आवृत्ति के आधार पर तत्वों के सबसेट का चयन करने के लिए उपयोगी है।

जब भी हमें किसी दिए गए डेटासेट के भीतर सबसे लगातार, सबसे छोटे, या शीर्ष 'K' तत्वों को खोजने के लिए कहा जाता है तो हम इस पैटर्न का उपयोग करने पर विचार कर सकते हैं।

यह जिस तरह से काम करता है वह बहुत सरल है:

1. हम अपने न्यूनतम या अधिकतम ढेर में 'K' तत्व डालते हैं (यह कार्यान्वयन पर निर्भर करता है)।
2. जब भी हम अपने ढेर में जोड़ते हैं तो हमें समायोजित करना चाहिए ताकि हर समय लगातार/सबसे छोटे/शीर्ष 'K' तत्व बने रहें।

इस दृष्टिकोण की सुंदरता इसकी दक्षता में निहित है; आपको किसी भी सॉर्टिंग एल्गोरिदम का सहारा लेने की आवश्यकता नहीं है, क्योंकि ढेर स्वयं स्वाभाविक रूप से आपके लिए आवश्यक क्रम बनाए रखता है।

महत्वपूर्ण संकेतक:

• आपको संग्रह में K सबसे बड़े या सबसे छोटे तत्वों की पहचान करने की आवश्यकता है।
• समस्याओं के लिए कुछ मानदंडों के आधार पर रैंकिंग तत्वों की आवश्यकता होती है।
• आप डेटासेट में शीर्ष K लगातार तत्वों को ढूंढना चाहते हैं।

टेम्पलेट कोड:

अजगर

 import heapq def top_k_elements(arr, k): heap = [] for num in arr: # Define your own criteria and logic to push elements onto the heap # For example, if you want to find the top k largest elements, push (-num, num) onto the heap heapq.heappush(heap, (-CRITERIA, num)) if len(heap) > k: heapq.heappop(heap) return [num for _, num in heap]

जे एस

 function topKElements(arr, k) { const minHeap = []; for (const num of arr) { // Define your own criteria and logic to push elements onto the heap // For example, if you want to find the top k smallest elements, push num onto the heap minHeap.push(CRITERIA); if (minHeap.length > k) { minHeap.sort((a, b) => a - b).shift(); } } return minHeap.sort((a, b) => a - b); }

जावा

 import java.util.*; public List<Integer> topKElements(int[] arr, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(a -> -CRITERIA)); for (int num : arr) { // Define your own criteria and logic to push elements onto the heap // For example, if you want to find the top k largest elements, push -num onto the heap heap.offer(-CRITERIA); if (heap.size() > k) { heap.poll(); } } List<Integer> topK = new ArrayList<>(); while (!heap.isEmpty()) { topK.add(-heap.poll()); } Collections.reverse(topK); return topK; }

6. दो ढेर

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

यह ऐसे काम करता है:

1. दो ढेरों का उपयोग करें: सबसे बड़े तत्व की पहचान करने के लिए एक अधिकतम ढेर और सबसे छोटे तत्व का पता लगाने के लिए एक न्यूनतम ढेर।
2. मैक्स हीप को पहले आधे नंबरों से भरें, उनमें से सबसे बड़े को खोजने का लक्ष्य रखें।
3. इस भाग में सबसे छोटे को इंगित करने के लिए न्यूनतम ढेर को संख्याओं के दूसरे भाग से भरें।
4. दोनों ढेरों के शीर्ष तत्वों की जांच करके किसी भी समय वर्तमान संख्या सेट के मध्य की गणना की जा सकती है।

महत्वपूर्ण संकेतक:

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

टेम्पलेट कोड:

अजगर

 import heapq class TwoHeaps: def __init__(self): self.min_heap = [] # Right heap to store larger half self.max_heap = [] # Left heap to store smaller half def add_num(self, num): if not self.max_heap or num <= -self.max_heap[0]: heapq.heappush(self.max_heap, -num) else: heapq.heappush(self.min_heap, num) # Balance the heaps if necessary if len(self.max_heap) > len(self.min_heap) + 1: heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap)) elif len(self.min_heap) > len(self.max_heap): heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap)) def find_median(self): if len(self.max_heap) == len(self.min_heap): return (-self.max_heap[0] + self.min_heap[0]) / 2.0 else: return -self.max_heap[0] # Usage: two_heaps = TwoHeaps() two_heaps.add_num(1) two_heaps.add_num(2) median = two_heaps.find_median() print("Median:", median)

जे एस

 class TwoHeaps { constructor() { this.minHeap = []; // Right heap to store larger half this.maxHeap = []; // Left heap to store smaller half } addNumber(num) { if (this.maxHeap.length === 0 || num <= -this.maxHeap[0]) { this.maxHeap.push(-num); } else { this.minHeap.push(num); } // Balance the heaps if necessary if (this.maxHeap.length > this.minHeap.length + 1) { this.minHeap.push(-this.maxHeap.shift()); } else if (this.minHeap.length > this.maxHeap.length) { this.maxHeap.push(-this.minHeap.shift()); } } findMedian() { if (this.maxHeap.length === this.minHeap.length) { return (-this.maxHeap[0] + this.minHeap[0]) / 2; } else { return -this.maxHeap[0]; } } } // Usage: const twoHeaps = new TwoHeaps(); twoHeaps.addNumber(1); twoHeaps.addNumber(2); const median = twoHeaps.findMedian(); console.log("Median:", median);

जावा

 import java.util.*; class TwoHeaps { private PriorityQueue<Integer> minHeap; // Right heap to store larger half private PriorityQueue<Integer> maxHeap; // Left heap to store smaller half public TwoHeaps() { minHeap = new PriorityQueue<>(); maxHeap = new PriorityQueue<>(Collections.reverseOrder()); } public void addNumber(int num) { if (maxHeap.isEmpty() || num <= -maxHeap.peek()) { maxHeap.offer(-num); } else { minHeap.offer(num); } // Balance the heaps if necessary if (maxHeap.size() > minHeap.size() + 1) { minHeap.offer(-maxHeap.poll()); } else if (minHeap.size() > maxHeap.size()) { maxHeap.offer(-minHeap.poll()); } } public double findMedian() { if (maxHeap.size() == minHeap.size()) { return (-maxHeap.peek() + minHeap.peek()) / 2.0; } else { return -maxHeap.peek(); } } } // Usage: TwoHeaps twoHeaps = new TwoHeaps(); twoHeaps.addNumber(1); twoHeaps.addNumber(2); double median = twoHeaps.findMedian(); System.out.println("Median: " + median);

7. मोनोटोनिक स्टैक

मोनोटोनिक - (किसी कार्य या मात्रा का) इस प्रकार बदलता रहता है कि वह या तो कभी घटती नहीं है या कभी बढ़ती नहीं है।

मोनोटोनिक स्टैक गैर-बढ़ते या गैर-घटते क्रम में तत्वों के ढेर को बनाए रखता है, जिसका उपयोग अक्सर किसी सरणी में निकटतम छोटे/बड़े तत्वों को खोजने के लिए किया जाता है। यह कुछ समस्याओं के अनुकूलन के लिए एक शक्तिशाली उपकरण है।

आदेश सख्त है, जब भी हमारा सामना किसी ऐसे तत्व से होता है जो स्टैक के शीर्ष पर मौजूद तत्व से छोटा (या बड़ा) है तो हमें मोनोटोनिक स्टैक से तब तक निकलना चाहिए जब तक कि जिस तत्व को हम जोड़ना चाह रहे हैं वह सबसे छोटा (या सबसे बड़ा) न हो जाए। उन्हें।

महत्वपूर्ण संकेतक:

• आपको तत्वों को गैर-बढ़ते या गैर-घटते क्रम में बनाए रखने की आवश्यकता है।
• समस्याओं में निकटतम छोटे या बड़े तत्व को ढूंढना शामिल है।
• आप ऑर्डर को संरक्षित करते हुए स्टैक-आधारित संचालन को अनुकूलित करना चाहते हैं।

टेम्पलेट कोड:

अजगर

 def monotonic_stack(items): stack = [] for item in items: # Adjust the condition for comparisons to suit your needs while stack and stack[-1] <= item: stack.pop() # Do something with the popped item here stack.append(item)

जे एस

 function monotonicStack(items) { const stack = []; for (const item of items) { // Adjust the condition for comparisons to suit your needs while (stack.length > 0 && stack[stack.length - 1] <= item) { stack.pop(); // Do something with the popped item here } stack.push(item); } return stack; }

जावा

 import java.util.*; public static int[] monotonicStack(int[] items) { Deque<Integer> stack = new ArrayDeque<>(); for (int item : items) { // Adjust the condition for comparisons to suit your needs while (!stack.isEmpty() && stack.peekLast() <= item) { stack.pollLast(); // Do something with the popped item here } stack.offerLast(item); } int[] result = new int[stack.size()]; int i = stack.size() - 1; while (!stack.isEmpty()) { result[i--] = stack.pollLast(); } return result; }

8. गहराई-पहली खोज

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

किसी पेड़ पर डीएफएस करने के लिए, आपको जड़ से शुरुआत करनी होगी। फिर नीचे दिए गए चरणों का पालन करें:

1. आमतौर पर बाएँ से दाएँ , उसके चिल्ड्रेन नोड्स पर जाकर वर्तमान नोड का अन्वेषण करें।
2. पेड़ में गहराई तक जाकर, प्रत्येक चाइल्ड नोड पर DFS प्रक्रिया को पुनरावर्ती रूप से लागू करें ।
3. एक बार सभी चाइल्ड नोड्स का दौरा हो जाने के बाद, मूल नोड पर वापस जाएँ ।
4. वर्तमान नोड के प्रत्येक अनविज़िट बच्चे के लिए चरण 1-3 को तब तक दोहराएँ जब तक कि पेड़ के सभी नोड्स का दौरा न हो जाए।

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

महत्वपूर्ण संकेतक:

• आप वृक्ष संरचनाओं के साथ काम कर रहे हैं और आपको विशिष्ट ट्रैवर्सल ऑर्डर का पता लगाने की आवश्यकता है।
• समस्याओं में पथ ढूंढना, गहराई की गणना करना, या प्री-ऑर्डर/इन-ऑर्डर/पोस्ट-ऑर्डर ट्रैवर्सल करना शामिल है।
• आप यह जांचना चाहते हैं कि दो नोड्स के बीच कोई पथ मौजूद है या नहीं।

टेम्पलेट कोड:

अजगर

 def dfs(root, target): if root is None: # Base case: Check if the current node is None return None if root.val == target: # Base case: Check if the current node value matches the target return root left = dfs(root.left, target) # Recursively search the left subtree if left is not None: # If the target is found in the left subtree, return the result return left return dfs(root.right, target) # Recursively search the right subtree

जे एस

 function dfs(root, target) { if (root === null) { // Base case: Check if the current node is null return null; } if (root.val === target) { // Base case: Check if the current node value matches the target return root; } let left = dfs(root.left, target); // Recursively search the left subtree if (left !== null) { // If the target is found in the left subtree, return the result return left; } return dfs(root.right, target); // Recursively search the right subtree }

जावा

 public TreeNode dfs(TreeNode root, int target) { if (root == null) { // Base case: Check if the current node is null return null; } if (root.val == target) { // Base case: Check if the current node value matches the target return root; } TreeNode left = dfs(root.left, target); // Recursively search the left subtree if (left != null) { // If the target is found in the left subtree, return the result return left; } return dfs(root.right, target); // Recursively search the right subtree }

9. चौड़ाई-पहली खोज

बीएफएस पेड़ों और ग्राफ़ के लिए एक ट्रैवर्सल तकनीक है जो अगले स्तर पर जाने से पहले वर्तमान गहराई पर सभी नोड्स का पता लगाती है।

किसी पेड़ पर बीएफएस निष्पादित करने के लिए, आपको जड़ से शुरुआत करनी होगी। फिर नीचे दिए गए चरणों का पालन करें:

1. देखे जाने वाले नोड्स का ट्रैक रखने के लिए एक खाली कतार डेटा संरचना प्रारंभ करें।

2. रूट नोड को कतार में संलग्न करें ।

3. कतार खाली होने तक एक लूप दर्ज करें:

   1. कतार के सामने नोड को हटा दें।
   2. पंक्तिबद्ध नोड को संसाधित करें (उदाहरण के लिए, उस पर जाएँ या उस पर कुछ ऑपरेशन करें)।
   3. नोड के सभी बच्चों (यदि कोई हो) को कतार में शामिल करें।

4. कतार खाली होने तक चरण 3ए-3सी दोहराएँ ।

5. बीएफएस ट्रैवर्सल तब पूरा होता है जब पेड़ के सभी नोड्स को बाएं से दाएं स्तर-वार तरीके से देखा जाता है।

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

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

महत्वपूर्ण संकेतक:

• आपको एक पेड़ को एक-एक स्तर पार करना होगा।
• समस्याओं में अभारित ग्राफ़ में सबसे छोटा रास्ता ढूंढना शामिल है।
• आप किसी पेड़ या ग्राफ़ का चौड़ाई-प्रथम तरीके से अन्वेषण करना चाहते हैं।

टेम्पलेट कोड:

अजगर

 from collections import deque def bfs(root): # Create a queue and initialize it with the root node queue = deque([root]) # Perform breadth-first search until the queue is empty while len(queue) > 0: # Dequeue the front node from the queue node = queue.popleft() # Process the current node for child in node.children: if is_goal(child): # If the goal condition is satisfied, return the child node return FOUND(child) # Enqueue the child node to explore it in the next iterations queue.append(child) # Return NOT_FOUND if the goal is not reached return NOT_FOUND

जे एस

 function bfs(root) { const queue = []; // Create a queue and initialize it with the root node queue.push(root); while (queue.length > 0) { // Perform breadth-first search until the queue is empty const node = queue.shift(); // Dequeue the front node from the queue for (const child of node.children) { // Process the current node if (isGoal(child)) { // If the goal condition is satisfied, return the child node return `FOUND ${child}`; } queue.push(child); // Enqueue the child node to explore it in the next iterations } } return 'NOT_FOUND'; // Return NOT_FOUND if the goal is not reached }

जावा

 import java.util.LinkedList; import java.util.Queue; public String bfs(Node root) { Queue<Node> queue = new LinkedList<>(); // Create a queue and initialize it with the root node queue.offer(root); while (!queue.isEmpty()) { // Perform breadth-first search until the queue is empty Node node = queue.poll(); // Dequeue the front node from the queue for (Node child : node.getChildren()) { // Process the current node if (isGoal(child)) { // If the goal condition is satisfied, return the child node return "FOUND(child)"; } queue.offer(child); // Enqueue the child node to explore it in the next iterations } } return "NOT_FOUND"; // Return NOT_FOUND if the goal is not reached }

10. यूनियन फाइंड (डिसजॉइंट-सेट यूनियन)

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

यूनियन फाइंड को निम्नानुसार कार्यान्वित किया गया है:

1. आरंभीकरण: तत्वों के संग्रह से प्रारंभ करें, प्रत्येक को एक अलग असंयुक्त सेट के रूप में माना जाता है। प्रत्येक सेट के लिए एक अद्वितीय प्रतिनिधि (अक्सर तत्व ही) निर्दिष्ट करें।
2. यूनियन ऑपरेशन: दो सेटों को मर्ज करने के लिए यूनियन ऑपरेशन करें। एक सेट का प्रतिनिधि चुनें (अक्सर कुछ मानदंडों के आधार पर, जैसे रैंक या आकार) और इसे दूसरे सेट के प्रतिनिधि का जनक बनाएं। यह प्रभावी ढंग से दो सेटों को जोड़ता है।
3. फाइंड ऑपरेशन: जब आपको यह निर्धारित करने की आवश्यकता हो कि कोई तत्व किस सेट से संबंधित है, तो फाइंड ऑपरेशन का उपयोग करें। प्रश्न में तत्व से शुरू करते हुए, उसके सेट के रूट नोड (प्रतिनिधि) को खोजने के लिए पेड़ को ऊपर की ओर पार करें। पथ के तत्वों को सीधे रूट पर इंगित करके भविष्य के खोज संचालन को अनुकूलित करने के लिए पथ संपीड़न तकनीक को यहां लागू किया जा सकता है।
4. साइकिल डिटेक्शन: यूनियन-फाइंड का उपयोग अक्सर ग्राफ़ में चक्रों का पता लगाने के लिए किया जाता है। यूनियन ऑपरेशन करते समय, यदि दोनों तत्व एक ही सेट से संबंधित हैं (यानी, उनके पास एक ही प्रतिनिधि है), तो यह इंगित करता है कि नोड्स के बीच एक किनारे को जोड़ने से ग्राफ़ में एक चक्र बन जाएगा।
5. अनुकूलन: यूनियन-फाइंड ऑपरेशंस की दक्षता में सुधार के लिए विभिन्न अनुकूलन तकनीकों को लागू किया जा सकता है, जैसे रैंक और पथ संपीड़न द्वारा यूनियन।

टेम्पलेट कोड:

अजगर

 class UnionFind: def __init__(self): self.id = {} def find(self, x): y = self.id.get(x, x) if y != x: self.id[x] = y = self.find(y) return y def union(self, x, y): self.id[self.find(x)] = self.find(y)

जे एस

 class UnionFind { constructor() { this.id = {}; } /** * Find the root parent of an element in the set. * Implements path compression for better efficiency. * @param x The element to find the root parent for. * @returns The root parent of the element. */ find(x) { let y = this.id[x] || x; if (y !== x) { this.id[x] = y = this.find(y); } return y; } /** * Union two elements into the same set. * @param x The first element. * @param y The second element. */ union(x, y) { this.id[this.find(x)] = this.find(y); } }

जावा

 import java.util.*; class UnionFind { private Map<String, String> id; public UnionFind() { id = new HashMap<>(); } /** * Find the root parent of an element in the set. * Implements path compression for better efficiency. * @param x The element to find the root parent for. * @return The root parent of the element. */ public String find(String x) { String y = id.getOrDefault(x, x); if (!y.equals(x)) { id.put(x, find(y)); } return y; } /** * Union two elements into the same set. * @param x The first element. * @param y The second element. */ public void union(String x, String y) { id.put(find(x), find(y)); } }

11. टोपोलॉजिकल सॉर्ट

एक निर्देशित चक्रीय ग्राफ (डीएजी) एक निर्देशित ग्राफ है जिसमें कोई निर्देशित चक्र नहीं है।

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

यहां टोपोलॉजिकल सॉर्टिंग का चरण-दर-चरण विवरण दिया गया है:

1. आरंभीकरण: एक निर्देशित एसाइक्लिक ग्राफ ( डीएजी ) से शुरू करें जो निर्भरता वाले कार्यों या नोड्स का प्रतिनिधित्व करता है। क्रमबद्ध नोड्स को रखने के लिए एक कतार प्रारंभ करें।

2. इन-डिग्री गणना: ग्राफ़ में प्रत्येक नोड के लिए इन-डिग्री (आने वाले किनारों की संख्या) की गणना करें। 0 की इन-डिग्री वाले नोड्स में कोई निर्भरता नहीं होती है और वे टोपोलॉजिकल सॉर्ट के शुरुआती बिंदु होने के लिए उपयुक्त होते हैं।

3. आरंभिक कतार भरना: 0 की इन-डिग्री वाले सभी नोड्स को कतार में शामिल करें। इन नोड्स को पहले संसाधित किया जा सकता है।

4. टोपोलॉजिकल सॉर्ट लूप: जबकि कतार खाली नहीं है, निम्न चरणों का पालन करें:

   1. कतार के सामने से एक नोड हटाएँ।
   2. नोड को संसाधित करें (उदाहरण के लिए, इसे क्रमबद्ध सूची में जोड़ें)।
   3. नोड के प्रत्येक पड़ोसी (जिस नोड की ओर यह इंगित करता है) के लिए, उनकी डिग्री में 1 की कमी करें।
   4. यदि किसी पड़ोसी की इन-डिग्री वृद्धि के परिणामस्वरूप 0 हो जाती है, तो उसे कतार में शामिल करें।

5. पूर्णता: एक बार टोपोलॉजिकल सॉर्ट लूप पूरा हो जाने पर, कतार खाली हो जाएगी, और सॉर्ट की गई सूची में सभी नोड्स एक वैध टोपोलॉजिकल क्रम में होंगे।

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

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

महत्वपूर्ण संकेतक:

• समस्या में निर्भरता वाले कार्यों को शेड्यूल करना या ऑर्डर करना शामिल है।
• आप एक निर्देशित एसाइक्लिक ग्राफ (डीएजी) के साथ काम कर रहे हैं।
• कार्यों को उनकी निर्भरता का पालन करते हुए एक विशिष्ट क्रम में निष्पादित करने की आवश्यकता है।

टेम्पलेट कोड:

अजगर

 from collections import deque def find_indegree(graph): # Calculate the indegree of each node in the graph indegree = {node: 0 for node in graph} for node in graph: for neighbor in graph[node]: indegree[neighbor] += 1 return indegree def topological_sort(graph): result = [] queue = deque() indegree = find_indegree(graph) # Add nodes with 0 indegree to the queue for node in indegree: if indegree[node] == 0: queue.append(node) while queue: node = queue.popleft() result.append(node) # Update the indegree of neighboring nodes for neighbor in graph[node]: indegree[neighbor] -= 1 if indegree[neighbor] == 0: queue.append(neighbor) # If all nodes are visited, return the result if len(graph) == len(result): return result else: return None

जे एस

 /** * Finds the indegree of each node in the graph. * @param {object} graph - The input graph. * @returns {object} - The indegree of each node. */ function findIndegree(graph) { const indegree = {}; for (const node in graph) { indegree[node] = 0; } for (const node in graph) { for (const neighbor of graph[node]) { indegree[neighbor]++; } } return indegree; } /** * Performs topological sorting on the given graph. * @param {object} graph - The input graph. * @returns {array|null} - The sorted nodes in topological order or null if a cycle is detected. */ function topologicalSort(graph) { const result = []; const queue = []; const indegree = findIndegree(graph); // Add nodes with no incoming edges to the queue for (const node in indegree) { if (indegree[node] === 0) { queue.push(node); } } while (queue.length > 0) { const node = queue.shift(); result.push(node); // Decrement the indegree of neighbors and enqueue if indegree becomes zero for (const neighbor of graph[node]) { indegree[neighbor]--; if (indegree[neighbor] === 0) { queue.push(neighbor); } } } // Check if all nodes have been visited (no cycles) if (Object.keys(graph).length === result.length) { return result; } else { return null; } }

जावा

 import java.util.*; /** * Finds the indegree of each node in the graph. * @param graph - The input graph. * @return The indegree of each node. */ public Map<String, Integer> findIndegree(Map<String, List<String>> graph) { Map<String, Integer> indegree = new HashMap<>(); for (String node : graph.keySet()) { indegree.put(node, 0); } for (String node : graph.keySet()) { for (String neighbor : graph.get(node)) { indegree.put(neighbor, indegree.getOrDefault(neighbor, 0) + 1); } } return indegree; } /** * Performs topological sorting on the given graph. * @param graph - The input graph. * @return The sorted nodes in topological order or null if a cycle is detected. */ public List<String> topologicalSort(Map<String, List<String>> graph) { List<String> result = new ArrayList<>(); Queue<String> queue = new LinkedList<>(); Map<String, Integer> indegree = findIndegree(graph); // Add nodes with no incoming edges to the queue for (String node : indegree.keySet()) { if (indegree.get(node) == 0) { queue.offer(node); } } while (!queue.isEmpty()) { String node = queue.poll(); result.add(node); // Decrement the indegree of neighbors and enqueue if indegree becomes zero for (String neighbor : graph.get(node)) { indegree.put(neighbor, indegree.get(neighbor) - 1); if (indegree.get(neighbor) == 0) { queue.offer(neighbor); } } } // Check if all nodes have been visited (no cycles) if (graph.size() == result.size()) { return result; } else { return null; } }

12. प्रयास (उपसर्ग-वृक्ष)

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

यहां बताया गया है कि ट्राइ को कैसे कार्यान्वित किया जाए:

1. आरंभीकरण: एक खाली ट्राई से प्रारंभ करें, जिसमें आम तौर पर एक रूट नोड होता है जिसमें कोई संबद्ध वर्ण नहीं होता है।

2. सम्मिलन: किसी शब्द को ट्राइ में सम्मिलित करने के लिए, रूट नोड से शुरू करें और पेड़ के नीचे एक समय में एक वर्ण को पार करें। शब्द के प्रत्येक अक्षर के लिए:

   1. जांचें कि क्या उस वर्ण वाला कोई चाइल्ड नोड वर्तमान नोड के अंतर्गत मौजूद है।
   2. यदि ऐसा होता है, तो चाइल्ड नोड पर जाएँ।
   3. यदि नहीं, तो चरित्र के साथ एक नया चाइल्ड नोड बनाएं और उस पर जाएं।

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

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

5. हटाना: ट्राई से किसी शब्द को हटाने के लिए, शब्द की खोज करें। जब आप शब्द के अंत तक पहुंचें, तो अंतिम मार्कर हटा दें (यदि वह मौजूद है)। यदि नोड में कोई अन्य संतान नहीं है, तो आप ट्राई की पूरी शाखा को सुरक्षित रूप से हटा सकते हैं, जो शब्द का प्रतिनिधित्व करती है।

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

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

महत्वपूर्ण संकेतक:

• आप स्ट्रिंग्स से निपट रहे हैं और आपको कुशल स्ट्रिंग मिलान की आवश्यकता है।
• समस्याओं में स्वत: पूर्ण सुझाव, वर्तनी जांचकर्ता, या सामान्य उपसर्गों वाले शब्दों की खोज शामिल है।
• आप शब्दों को कुशलतापूर्वक संग्रहित करना और खोजना चाहते हैं।

टेम्पलेट कोड:

अजगर

 class TrieNode: def __init__(self, value): self.value = value self.children = {} def insert(self, s, idx): # idx: index of the current character in s if idx != len(s): self.children.setdefault(s[idx], TrieNode(s[idx])) self.children.get(s[idx]).insert(s, idx + 1)

जे एस

 class TrieNode { constructor(value) { this.value = value; this.children = {}; } insert(s, idx) { // idx: index of the current character in s if (idx !== s.length) { if (!this.children[s[idx]]) { this.children[s[idx]] = new TrieNode(s[idx]); } this.children[s[idx]].insert(s, idx + 1); } } }

जावा

 import java.util.*; class TrieNode { char value; Map<Character, TrieNode> children; TrieNode(char value) { this.value = value; this.children = new HashMap<>(); } void insert(String s, int idx) { // idx: index of the current character in s if (idx != s.length()) { char c = s.charAt(idx); if (!children.containsKey(c)) { children.put(c, new TrieNode(c)); } children.get(c).insert(s, idx + 1); } } }

13. गतिशील प्रोग्रामिंग

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

यहां इसकी प्रमुख विशेषताएं हैं और यह कैसे काम करता है:

इष्टतम उपसंरचना:

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

ओवरलैपिंग उपसमस्याएँ:

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

डायनामिक प्रोग्रामिंग कैसे काम करती है:

1. उपसमस्याओं की पहचान करें: डीपी का उपयोग करके किसी समस्या को हल करने में पहला कदम उपसमस्याओं की पहचान करना है। समस्या को छोटी, प्रबंधनीय उप-समस्याओं में विभाजित करें, जो हल होने पर मुख्य समस्या को हल करने में योगदान करती हैं।
2. पुनरावर्ती समाधान: एक पुनरावर्ती समाधान विकसित करें जो बड़ी समस्या के समाधान को छोटी उपसमस्याओं के समाधान के रूप में व्यक्त करता है। यह पुनरावर्ती सूत्रीकरण इष्टतम उपसंरचना को ग्रहण करता है।
3. संस्मरण या सारणीकरण: अतिव्यापी उप-समस्याओं को संबोधित करने के लिए, आप दो सामान्य तकनीकों के बीच चयन कर सकते हैं:
   • संस्मरण: उपसमस्याओं के परिणामों को गणना करते समय डेटा संरचना (आमतौर पर एक सरणी या हैश तालिका) में संग्रहीत करें। जब कोई उप-समस्या दोबारा सामने आती है, तो उसकी पुनर्गणना करने के बजाय स्टोरेज से उसका समाधान प्राप्त करें। इसे टॉप-डाउन दृष्टिकोण के रूप में भी जाना जाता है।
   • सारणीकरण: उप-समस्याओं के समाधानों को नीचे से ऊपर की ओर संग्रहीत करने के लिए एक तालिका (अक्सर एक 2डी सरणी) बनाएं। सबसे छोटी उपसमस्याओं को हल करके शुरुआत करें और धीरे-धीरे मुख्य समस्या तक पहुँचें।
4. इष्टतम समाधान: एक बार जब सभी उपसमस्याएँ हल हो जाती हैं, तो समस्या की पुनरावर्ती संरचना के अनुसार उसकी उपसमस्याओं के समाधानों को जोड़कर मुख्य समस्या का समाधान प्राप्त किया जा सकता है।

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

महत्वपूर्ण अवधारणाएँ: नीचे से ऊपर का दृष्टिकोण, ऊपर से नीचे, संस्मरण, सारणीकरण

महत्वपूर्ण संकेतक:

• समस्या को छोटी ओवरलैपिंग उपसमस्याओं में विभाजित किया जा सकता है।
• उप-समस्याओं के समाधानों को संग्रहीत और पुन: उपयोग करके अनुकूलित करने की आवश्यकता है।
• आप अनुकूलन या गिनती से जुड़ी समस्याओं को हल करना चाहते हैं।

टेम्पलेट कोड:

टॉप-डाउन मेमोइज़ेशन के लिए टेम्प्लेट गतिशील प्रोग्रामिंग को लागू करने के कई तरीकों में से एक है।

अजगर

 def top_down_memo(arr): def dp(state): # Base case(s): Define your own base case(s) for the problem if base_case: return 0 # Check if the state has already been memoized if state in memo: return memo[state] # Calculate the result using recurrence relation and memoize it result = recurrence_relation(state) memo[state] = result return result memo = {} # Memoization table to store calculated results return dp(initial_state)

जे एस

 function topDownMemo(arr) { function dp(state) { // Base case(s): Define your own base case(s) for the problem if (baseCase) { return 0; } // Check if the state has already been memoized if (memo.has(state)) { return memo.get(state); } // Calculate the result using recurrence relation and memoize it const result = recurrenceRelation(state); memo.set(state, result); return result; } const memo = new Map(); // Memoization map to store calculated results return dp(initialState); }

जावा

 import java.util.HashMap; import java.util.Map; public int topDownMemo(int[] arr) { Map<StateType, Integer> memo = new HashMap<>(); // Memoization map to store calculated results return dp(initialState, memo); } private int dp(StateType state, Map<StateType, Integer> memo) { // Base case(s): Define your own base case(s) for the problem if (baseCase) { return 0; } // Check if the state has already been memoized if (memo.containsKey(state)) { return memo.get(state); } // Calculate the result using recurrence relation and memoize it int result = recurrenceRelation(state); memo.put(state, result); return result; }

14. पीछे हटना

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

बैकट्रैकिंग कैसे काम करती है, इसकी गहराई से जानकारी यहां दी गई है:

1. समस्या स्थान अन्वेषण: बैकट्रैकिंग एक समय में एक समाधान का निर्माण करके समस्या स्थान का पता लगाता है। हर कदम पर वह निर्णय लेती है और आगे बढ़ती है।
2. पुनरावर्ती संरचना: बैकट्रैकिंग में अक्सर पुनरावर्तन शामिल होता है। यह प्रारंभिक आंशिक समाधान से शुरू होता है और इसे विस्तारित करने के सभी संभावित तरीकों की खोज करता है। यह प्रक्रिया बार-बार तब तक जारी रहती है जब तक कि पूर्ण समाधान नहीं मिल जाता या यह स्पष्ट नहीं हो जाता कि कोई वैध समाधान मौजूद नहीं है।
3. निर्णय बिंदु: प्रत्येक चरण में, निर्णय बिंदु होते हैं जहां एल्गोरिदम को उपलब्ध विकल्पों में से चयन करना होगा। ये विकल्प अन्वेषण प्रक्रिया में शाखाओं को बढ़ावा देते हैं।
4. समाधान सत्यापन: चुनाव करने के बाद, एल्गोरिदम जाँचता है कि वर्तमान आंशिक समाधान वैध है या नहीं। यदि यह मान्य है, तो एल्गोरिदम अगले चरण पर आगे बढ़ता है। यदि नहीं, तो यह पीछे हट जाता है, पिछली पसंद को रद्द कर देता है और अन्य विकल्प तलाशता है।
5. समाप्ति की शर्तें: बैकट्रैकिंग तब तक जारी रहती है जब तक कि दो शर्तों में से एक पूरी नहीं हो जाती:
   • एक वैध समाधान मिल जाता है, ऐसी स्थिति में एल्गोरिदम रुक जाता है और समाधान लौटा देता है।
   • यह निर्धारित किया गया है कि कोई वैध समाधान मौजूद नहीं है, जिस बिंदु पर एल्गोरिदम पिछले निर्णय बिंदु पर वापस जाता है और विभिन्न विकल्पों की खोज करता है।
6. प्रूनिंग: खोज को अनुकूलित करने के लिए, बैकट्रैकिंग में अक्सर प्रूनिंग रणनीतियाँ शामिल होती हैं। प्रूनिंग में उन रास्तों की खोज से बचना शामिल है जो अमान्य समाधानों की ओर ले जाने की गारंटी देते हैं, जिससे खोज स्थान काफी कम हो जाता है।

बैकट्रैकिंग के अनुप्रयोग:

बैकट्रैकिंग का उपयोग विभिन्न समस्या डोमेन में किया जाता है, जिनमें शामिल हैं:

• सुडोकू और एन-क्वींस जैसी पहेलियाँ सुलझाना।
• क्रमपरिवर्तन और संयोजन उत्पन्न करना.
• ग्राफ़ और पेड़ों में पथ खोजना।
• बाधा संतुष्टि की समस्याएँ (उदाहरण के लिए, ट्रैवलिंग सेल्समैन की समस्या)।
• गेम-प्लेइंग एल्गोरिदम (उदाहरण के लिए, शतरंज एआई)।

महत्वपूर्ण संकेतक:

• समस्या में क्रमिक रूप से अनेक संभावनाओं की खोज शामिल है।
• ऐसे निर्णय बिंदु या बाधाएँ हैं जिनके लिए विभिन्न विकल्पों को आज़माने की आवश्यकता होती है।
• आपको विस्तृत खोज के माध्यम से सभी संभावित समाधान खोजने या विशिष्ट शर्तों को पूरा करने की आवश्यकता है।

टेम्पलेट कोड:

अजगर

 def backtrack(curr, OTHER_ARGUMENTS...): if BASE_CASE: # Modify the answer according to the problem's requirements return ans = 0 for ITERATE_OVER_INPUT: # Modify the current state according to the problem's requirements ans += backtrack(curr, OTHER_ARGUMENTS...) # Undo the modification of the current state (backtrack) return ans

जे एस

 function backtrack(curr, ...OTHER_ARGUMENTS) { if (BASE_CASE) { // Modify the answer according to the problem's requirements return; } let ans = 0; for (let i = 0; i < ITERATE_OVER_INPUT.length; i++) { const item = ITERATE_OVER_INPUT[i]; // Modify the current state according to the problem's requirements ans += backtrack(curr, ...OTHER_ARGUMENTS); // Undo the modification of the current state (backtrack) } return ans; }

जावा

 public int backtrack(StateType curr, OtherArgumentType... OTHER_ARGUMENTS) { if (BASE_CASE) { // Modify the answer according to the problem's requirements return; } int ans = 0; for (int i = 0; i < ITERATE_OVER_INPUT.length; i++) { ItemType item = ITERATE_OVER_INPUT[i]; // Modify the current state according to the problem's requirements ans += backtrack(curr, OTHER_ARGUMENTS); // Undo the modification of the current state (backtrack) } return ans; }

15. मर्ज अंतराल

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

यहां देखें कि विलय अंतराल कैसे काम करता है:

1. अंतराल प्रतिनिधित्व: अंतराल को आम तौर पर प्रारंभ और अंत बिंदुओं के जोड़े के रूप में दर्शाया जाता है (उदाहरण के लिए, [प्रारंभ, अंत] )।
2. क्रमबद्ध करना: अंतरालों को कुशलतापूर्वक मर्ज करने के लिए, उन्हें उनके प्रारंभ बिंदुओं के आधार पर क्रमबद्ध करके प्रारंभ करें। यह सुनिश्चित करता है कि ओवरलैपिंग या आसन्न अंतराल क्रमबद्ध सूची में आसन्न हैं।
3. विलय प्रक्रिया: मर्ज किए गए अंतरालों को बनाए रखने के लिए एक खाली सूची प्रारंभ करें। फिर, क्रमबद्ध अंतरालों को एक-एक करके पुनरावृत्त करें:
   • यदि वर्तमान अंतराल पिछले अंतराल के साथ ओवरलैप नहीं होता है, तो इसे मर्ज किए गए अंतराल की सूची में जोड़ें।
   • यदि कोई ओवरलैप है, तो वर्तमान और पिछले दोनों अंतरालों को शामिल करने के लिए पिछले मर्ज किए गए अंतराल के समापन बिंदु को अपडेट करें, उन्हें प्रभावी ढंग से मर्ज करें।
4. समापन: सभी अंतरालों को संसाधित करने के बाद, मर्ज किए गए अंतरालों की सूची में गैर-अतिव्यापी और समेकित अंतराल शामिल होंगे।

मर्ज अंतराल के अनुप्रयोग:

विलय अंतराल आमतौर पर उपयोग किए जाते हैं:

• शेड्यूलिंग और समय प्रबंधन अनुप्रयोग.
• कैलेंडर सिस्टम में ओवरलैपिंग इवेंट का पता लगाना।
• अंतराल-आधारित डेटा विश्लेषण, जैसे डेटाबेस क्वेरीज़ में।
• संसाधन आवंटन और बैठक समय-निर्धारण से संबंधित समस्याओं का समाधान करना।

ओवरलैपिंग अंतरालों को मर्ज करके, यह तकनीक अंतराल-आधारित संचालन को सरल बनाती है और विभिन्न अनुप्रयोगों में दक्षता बढ़ाती है।

महत्वपूर्ण संकेतक:

• आप अंतराल या समय-आधारित डेटा से निपट रहे हैं।
• समस्याओं में ओवरलैपिंग या आसन्न अंतरालों का विलय शामिल है।
• आप अंतराल-आधारित संचालन को सरल बनाना चाहते हैं या ईवेंट शेड्यूलिंग को अनुकूलित करना चाहते हैं।

टेम्पलेट कोड:

अजगर

 def merge_intervals(intervals): # 1. Sort the intervals based on their start values. intervals.sort(key=lambda x: x[0]) # 2. Initialize an empty list to store merged intervals. merged_intervals = [] # 3. Iterate through the sorted intervals. for interval in intervals: # 4. If the merged_intervals list is empty or the current interval does not overlap with the last merged interval: if not merged_intervals or interval[0] > merged_intervals[-1][1]: merged_intervals.append(interval) else: # 5. If the current interval overlaps with the last merged interval, merge them. merged_intervals[-1][1] = max(merged_intervals[-1][1], interval[1]) # 6. Return the merged_intervals list. return merged_intervals

जे एस

 function mergeIntervals(intervals) { // 1. Sort the intervals based on their start values. intervals.sort((a, b) => a[0] - b[0]); // 2. Initialize an empty array to store merged intervals. const mergedIntervals = []; // 3. Iterate through the sorted intervals. for (const interval of intervals) { // 4. If the mergedIntervals array is empty or the current interval does not overlap with the last merged interval: if (mergedIntervals.length === 0 || interval[0] > mergedIntervals[mergedIntervals.length - 1][1]) { mergedIntervals.push(interval); } else { // 5. If the current interval overlaps with the last merged interval, merge them. mergedIntervals[mergedIntervals.length - 1][1] = Math.max(mergedIntervals[mergedIntervals.length - 1][1], interval[1]); } } // 6. Return the mergedIntervals array. return mergedIntervals; }

जावा

 public class MergeIntervals { public int[][] merge(int[][] intervals) { // 1. Sort the intervals based on their start values. Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // 2. Create a list to store merged intervals. List<int[]> mergedIntervals = new ArrayList<>(); // 3. Iterate through the sorted intervals. for (int[] interval : intervals) { // 4. If the mergedIntervals list is empty or the current interval does not overlap with the last merged interval: if (mergedIntervals.isEmpty() || interval[0] > mergedIntervals.get(mergedIntervals.size() - 1)[1]) { mergedIntervals.add(interval); } else { // 5. If the current interval overlaps with the last merged interval, merge them. mergedIntervals.get(mergedIntervals.size() - 1)[1] = Math.max(mergedIntervals.get(mergedIntervals.size() - 1)[1], interval[1]); } } // 6. Convert the list to an array and return it. return mergedIntervals.toArray(new int[mergedIntervals.size()][]); } }

और अधिक सीखना चाहते हैं?

यदि आप इन पैटर्नों के बारे में अधिक जानना चाहते हैं और अपने अगले कोडिंग साक्षात्कार के दौरान आप इन्हें अधिक प्रभावी ढंग से कैसे लागू कर सकते हैं, तो techinterviews.io आज ही देखें! हम आपको आपके अगले कोडिंग साक्षात्कार के लिए तैयार करने के लिए एक व्यापक पाठ्यक्रम प्रदान करते हैं, जिसमें डेटा संरचना , एल्गोरिदम , व्यवहार साक्षात्कार और यहां तक कि वेतन वार्ता जैसे विषयों को शामिल किया गया है। आपके अभ्यास के लिए हमारे पास एक अंतर्निहित कोडिंग कार्यक्षेत्र भी है।

$30 की छूट पर हमारे प्रोमो कोड TECH30 के साथ आज ही अपनी कोडिंग साक्षात्कार तैयारी को सुपरचार्ज करें!