यह सब पैटर्न के बारे में है!

एक बार जब आप पैटर्न सीख लेते हैं, तो सब कुछ थोड़ा आसान लगने लगता है! यदि आप मेरे जैसे हैं, तो संभवतः आपको तकनीकी साक्षात्कार पसंद नहीं होंगे, और मैं आपको दोष नहीं देता - वे कठिन हो सकते हैं।

सरणी संबंधी समस्याएं कुछ सबसे आम समस्याएं हैं जिनका सामना आप साक्षात्कारों में करेंगे। इन समस्याओं में अक्सर प्राकृतिक सरणियों के साथ काम करना शामिल होता है:

const arr = [1, 2, 3, 4, 5];

और स्ट्रिंग समस्याएं, जो अनिवार्य रूप से वर्णों की सारणी हैं:

"mylongstring".split(""); // ['m', 'y', 'l', 'o','n', 'g', 's','t','r','i', 'n', 'g']

सरणी समस्याओं को हल करने के लिए सबसे आम पैटर्न में से एक स्लाइडिंग विंडो है।

स्लाइडिंग विंडो पैटर्न

स्लाइडिंग विंडो पैटर्न में दो पॉइंटर्स शामिल होते हैं जो एक ही दिशा में चलते हैं - जैसे कि सरणी में स्लाइड करने वाली विंडो।

इसका उपयोग कब करें

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

नियम 1: यदि आपको एक उप-सरणी या उप-स्ट्रिंग ढूंढने की आवश्यकता है और डेटा संरचना एक सरणी या स्ट्रिंग है, तो स्लाइडिंग विंडो पैटर्न का उपयोग करने पर विचार करें।

सरल उदाहरण

स्लाइडिंग विंडो में पॉइंटर्स की अवधारणा को पेश करने के लिए यहां एक बुनियादी उदाहरण दिया गया है:

function SlidingWindow(arr) {
    let l = 0;  // Left pointer
    let r = l   1;  // Right pointer

    while (r 



ध्यान दें कि बाएँ (L) और दाएँ (R) सूचकों को एक ही समय में नहीं चलना है, बल्कि उन्हें एक ही दिशा में चलना है।



दायां सूचक कभी भी बाएं सूचक से नीचे नहीं होगा।

आइए एक वास्तविक साक्षात्कार समस्या के साथ इस अवधारणा का पता लगाएं।


  
  
  वास्तविक दुनिया की समस्या: अक्षरों को दोहराए बिना सबसे लंबी सबस्ट्रिंग


समस्या: एक स्ट्रिंग s को देखते हुए, वर्णों को दोहराए बिना सबसे लंबी उप-स्ट्रिंग की लंबाई ज्ञात करें।

कीवर्ड: उप-स्ट्रिंग, सबसे लंबी (अधिकतम)


function longestSubstr(str) {
    let longest = 0;
    let left = 0;
    let hash = {};

    for (let right = 0; right = left) {
            left = hash[str[right]]   1;
        }

        hash[str[right]] = right;
        longest = Math.max(longest, right - left   1);
    }

    return longest;
}




अगर यह जटिल लगता है तो चिंता न करें—हम इसे थोड़ा-थोड़ा करके देखेंगे।


let str = "helloworld";
console.log(longestSubstr(str));  // Output: 5




इस समस्या का मूल सबसे लंबा उप-स्ट्रिंग बिना दोहराए जाने वाले वर्णों को ढूंढना है।


  
  
  प्रारंभिक विंडो: आकार 0


शुरुआत में, बाएँ (L) और दाएँ (R) दोनों सूचक एक ही स्थान पर हैं:


let left = 0;

for (let right = 0; right 





h e l l o w o r l d 
^
^
L
R




और हमारे पास एक खाली हैश (ऑब्जेक्ट) है:


let hash = {};




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

स्ट्रिंग को देखकर, हम स्पष्ट रूप से बता सकते हैं कि दुनिया बिना अक्षरों को दोहराए सबसे लंबी सबस्ट्रिंग है:


h e l l o w o r l d 
          ^        ^   
          L        R




इसकी लंबाई 5 है। तो, हम वहां कैसे पहुंचेंगे?

आइए इसे चरण दर चरण तोड़ें:


  
  
  आरंभिक राज्य




hash = {}

h e l l o w o r l d 
^
^
L
R





  
  
  पुनरावृत्ति 1:


प्रत्येक पुनरावृत्ति पर, हम आर पॉइंटर के तहत हैश मैप और वृद्धि में वर्ण जोड़ते हैं:


hash[str[right]] = right;
longest = Math.max(longest, right - left   1);




वर्तमान में, हमारी विंडो (एच और ई) में कोई दोहराव वाला अक्षर नहीं है:


hash = {h: 0}
h e l l o w o r l d 
^ ^
L R





  
  
  पुनरावृत्ति 2:




hash = {h: 0, e: 1}
h e l l o w o r l d 
^   ^
L   R




अब, हमारे पास एक नई विंडो है: हेल।


  
  
  पुनरावृत्ति 3:




hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
^     ^
L     R




यहां यह दिलचस्प हो जाता है: हमारे हैश में पहले से ही एल है, और आर स्ट्रिंग में दूसरे एल की ओर इशारा कर रहा है। यहीं पर हमारा if स्टेटमेंट आता है:


if (hash[str[right]] !== undefined)




यदि हमारे हैश में वह अक्षर है जिसकी ओर इशारा कर रहा है, तो हमें एक डुप्लिकेट मिल गया है! पिछली विंडो (हेल) हमारी अब तक की सबसे लंबी विंडो है।

तो, हम आगे क्या करें? हम L पॉइंटर को ऊपर ले जाकर बाईं ओर से विंडो को सिकोड़ते हैं क्योंकि हमने पहले ही बाईं सबस्ट्रिंग को संसाधित कर लिया है। लेकिन हम L को कितनी दूर तक ले जाते हैं?


left = hash[str[right]]   1;




हम डुप्लिकेट के ठीक बाद L को स्थानांतरित करते हैं:


hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
      ^
      ^
      L
      R




हम अभी भी हैश में अपना डुप्लिकेट जोड़ते हैं, इसलिए एल का सूचकांक अब 3 होगा।


hash[str[right]] = right;
longest = Math.max(longest, right - left   1);





  
  
  नया राज्य: पुनरावृत्ति 4




hash = {h: 0, e: 1, l: 3}
h e l l o w o r l d 
      ^ ^
      L R





  
  
  पुनरावृत्तियाँ 4 से 6




hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
      ^     ^
      L     R




जब आर किसी अन्य डुप्लिकेट (ओ) की ओर इशारा करता है, तो हम एल को पहले ओ के ठीक बाद ले जाते हैं:


hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
          ^ ^
          L R




हम तब तक जारी रखते हैं जब तक हमें एक और डुप्लिकेट एल नहीं मिलता:


hash = {h: 0, e: 1, l: 3, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^     ^
          L     R




लेकिन ध्यान दें कि यह वर्तमान विंडो के बाहर है! w से शुरू होकर, 


  
  
  नियम 3: संसाधित उप-x को अनदेखा करें


वर्तमान विंडो के बाहर कुछ भी अप्रासंगिक है—हमने इसे पहले ही संसाधित कर लिया है। इसे प्रबंधित करने के लिए मुख्य कोड है:


if (hash[str[right]] !== undefined && hash[str[right]] >= left)




यह शर्त सुनिश्चित करती है कि हम केवल वर्तमान विंडो के पात्रों की परवाह करते हैं, किसी भी शोर को फ़िल्टर करते हैं।


hash[str[right]] >= left




हम बाएं सूचक से बड़ी या उसके बराबर किसी भी चीज़ पर ध्यान केंद्रित करते हैं


  
  
  अंतिम पुनरावृत्ति:




hash = {h: 0, e: 1, l: 8, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^       ^
          L       R




मुझे पता है कि यह विस्तृत था, लेकिन समस्याओं को छोटे पैटर्न या नियमों में तोड़ना उन पर महारत हासिल करने का सबसे आसान तरीका है।


  
  
  सारांश:

• नियम 1: समस्या में कीवर्ड (जैसे, अधिकतम, न्यूनतम) सुराग हैं। यह समस्या सबसे लंबी उप-स्ट्रिंग बिना दोहराए जाने वाले वर्णों को खोजने के बारे में है।
• नियम 2: यदि आपको अद्वितीय या गैर-दोहराए जाने वाले तत्वों को खोजने की आवश्यकता है, तो हैश मानचित्रों के बारे में सोचें।
• नियम 3: वर्तमान विंडो पर ध्यान केंद्रित करें—इसके बाहर कुछ भी अप्रासंगिक है।

बोनस युक्तियाँ:

• समस्या को तोड़ें और एक छोटे उपसमुच्चय का उपयोग करके इसे विस्तृत बनाएं।
• current विंडो को अधिकतम करते समय, इस बारे में सोचें कि इसे यथासंभव लंबे समय तक कैसे बनाया जाए। इसके विपरीत, छोटा करते समय यह सोचें कि इसे यथासंभव छोटा कैसे किया जाए।

चीजों को पूरा करने के लिए, यहां आपके लिए प्रयास करने की एक छोटी सी चुनौती है! मैं अपना समाधान टिप्पणियों में पोस्ट करूंगा—यह अभ्यास करने का एक शानदार तरीका है।

समस्या 2: योग लक्ष्य से अधिक या उसके बराबर

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

/**
 * 
 * @param {Array} arr 
 * @param {number} target 
 * @returns {number} - length of the smallest subarray
 */
function greaterThanOrEqualSum(arr, target){
   let minimum = Infinity;
   let left = 0;
   let sum = 0;

   // Your sliding window logic here!
}

याद रखें, प्रोग्रामिंग में किसी भी चीज़ की तरह, दोहराव महत्वपूर्ण है! स्लाइडिंग विंडो की समस्याएँ हर समय सामने आती रहती हैं, इसलिए अधिक उदाहरणों के लिए Google पर जाने में संकोच न करें और अभ्यास करते रहें।

मैं इसे छोटा रख रहा हूं, लेकिन देखते रहिए- अगला लेख दो-पॉइंटर पैटर्न और रिकर्सन (पेड़ की समस्याओं के लिए तैयारी) पर चर्चा करेगा। यह थोड़ा अधिक चुनौतीपूर्ण होने वाला है!

यदि आप अधिक विशिष्ट सामग्री चाहते हैं, तो आप मुझे ट्विटर या को-फाई पर फ़ॉलो कर सकते हैं, मैं वहां कुछ अतिरिक्त सामग्री पोस्ट करूंगा!

संसाधन:

तकनीकी साक्षात्कार पुस्तिका

लीट कोड ऐरे 101