19:53
DSA PATTERNS Episode 16 | Sliding Window Pattern: Amazon Interview Question
Padho with Pratyush
Overview
यह वीडियो 'स्लाइडिंग विंडो पैटर्न' पर एक विस्तृत व्याख्या प्रदान करता है, जो डेटा स्ट्रक्चर्स और एल्गोरिदम (DSA) में एक महत्वपूर्ण विषय है। यह विशेष रूप से Amazon जैसी कंपनियों के इंटरव्यू में पूछे जाने वाले एक कठिन प्रश्न को हल करने पर केंद्रित है। वक्ता रटने के बजाय पैटर्न-आधारित दृष्टिकोण के महत्व पर जोर देता है, यह समझाते हुए कि स्लाइडिंग विंडो समस्याओं को कैसे पहचाना जाए और उन्हें हल करने के लिए एक व्यवस्थित टेम्पलेट का उपयोग कैसे किया जाए। वीडियो में मिन-विंडो सबस्ट्रिंग समस्या को हल करने के लिए चरण-दर-चरण प्रक्रिया का वर्णन किया गया है, जिसमें फ्रीक्वेंसी काउंटिंग और विंडो कंडीशन चेकिंग जैसे कॉन्सेप्ट्स शामिल हैं।
How was this?
Save this permanently with flashcards, quizzes, and AI chat
Chapters
- इंटरव्यू में अक्सर पूछे जाने वाले कठिन प्रश्नों को हल करने के लिए स्लाइडिंग विंडो पैटर्न एक महत्वपूर्ण तकनीक है।
- पैटर्न-आधारित दृष्टिकोण रटने से बेहतर है क्योंकि यह विभिन्न समस्याओं पर लागू होता है।
- यह पैटर्न स्ट्रिंग मैनिपुलेशन और सबस्ट्रिंग से संबंधित समस्याओं के लिए विशेष रूप से उपयोगी है।
यह समझना कि स्लाइडिंग विंडो पैटर्न क्यों महत्वपूर्ण है, आपको इंटरव्यू में पूछे जाने वाले जटिल स्ट्रिंग-आधारित प्रश्नों को अधिक कुशलता से हल करने में मदद करेगा।
लीड कोड पर एक हार्ड-रेटेड प्रश्न, जो Amazon, Facebook, LinkedIn जैसी कंपनियों में पूछा गया है, को स्लाइडिंग विंडो पैटर्न का उपयोग करके हल किया जा सकता है।
- समस्या में दो स्ट्रिंग S और T दिए गए हैं, और S में T का एक मिनिमम विंडो सबस्ट्रिंग खोजना है।
- इस विंडो में T के सभी कैरेक्टर, उनकी फ्रीक्वेंसी सहित, मौजूद होने चाहिए, भले ही उनका ऑर्डर कुछ भी हो।
- उदाहरण के लिए, यदि T = "AABC", तो विंडो में कम से कम दो 'A', एक 'B', और एक 'C' होना चाहिए।
इस समस्या को समझना आपको यह सीखने में मदद करता है कि कैसे एक स्ट्रिंग के भीतर एक सबस्ट्रिंग की न्यूनतम लंबाई या सबस्ट्रिंग को खोजना है जो कुछ शर्तों को पूरा करता हो।
यदि S = "ADOBECODEBANC" और T = "ABC", तो मिनिमम विंडो सबस्ट्रिंग "BANC" है।
- किसी भी स्लाइडिंग विंडो समस्या को पहचानने के लिए, देखें कि क्या यह फिक्स्ड-विंडो या वेरिएबल-विंडो समस्या है। यह प्रश्न मिनिमम सबस्ट्रिंग मांग रहा है, इसलिए यह वेरिएबल-विंडो है।
- विंडो की जानकारी (information) को स्टोर करने के लिए फ्रीक्वेंसी मैप (hash map या array) का उपयोग करें।
- यह निर्धारित करें कि विंडो की जानकारी सही है या गलत, यह जांच कर कि क्या यह दी गई कंडीशन को पूरा करती है (जैसे, T के सभी कैरेक्टर की फ्रीक्वेंसी मौजूद है)।
एक व्यवस्थित टेम्पलेट का पालन करने से आप स्लाइडिंग विंडो समस्याओं को हल करने के लिए एक सुसंगत और कुशल तरीका विकसित कर सकते हैं।
विंडो में कैरेक्टर की फ्रीक्वेंसी को ट्रैक करने के लिए 256 साइज़ के कैरेक्टर एरे का उपयोग करना, क्योंकि इसमें सभी ASCII कैरेक्टर शामिल हो सकते हैं।
- हाई पॉइंटर को स्ट्रिंग S के माध्यम से आगे बढ़ाएं और विंडो में कैरेक्टर की फ्रीक्वेंसी अपडेट करें।
- जब तक विंडो की जानकारी सही है (यानी, T की सभी आवश्यक फ्रीक्वेंसी पूरी हो रही हैं), तब तक विंडो की लंबाई को रिजल्ट के रूप में स्टोर करें और लो पॉइंटर को आगे बढ़ाएं।
- लो पॉइंटर को आगे बढ़ाते समय, विंडो से कैरेक्टर की फ्रीक्वेंसी को हटाना न भूलें।
यह फ्लोचार्ट मिनिमम विंडो समस्याओं के लिए एक सामान्य समाधान प्रदान करता है, जिससे आप किसी भी समान समस्या को हल करने के लिए इसे अनुकूलित कर सकते हैं।
जब विंडो "ADOBEC" है और T = "ABC", तो विंडो में A, B, C हैं। जब हाई 'O' पर जाता है, तो विंडो "ADOBECO" हो जाती है। अब, चूंकि कंडीशन पूरी हो गई है, हम लो को आगे बढ़ाना शुरू करते हैं।
- एक फंक्शन बनाएं जो दो फ्रीक्वेंसी एरे (हैव और नीडेड) लेता है।
- यह फंक्शन जांचता है कि क्या 'हैव' एरे में प्रत्येक कैरेक्टर की फ्रीक्वेंसी 'नीडेड' एरे में संबंधित कैरेक्टर की फ्रीक्वेंसी से कम है।
- यदि किसी भी कैरेक्टर के लिए यह कंडीशन गलत है, तो फंक्शन 'फॉल्स' रिटर्न करता है; अन्यथा, यह 'ट्रू' रिटर्न करता है।
एक स्पष्ट कंडीशन चेकिंग फंक्शन कोड को अधिक पठनीय बनाता है और स्लाइडिंग विंडो लॉजिक के मुख्य भाग को सरल बनाता है।
एक फंक्शन `bool check(vector<int>& have, vector<int>& needed)` जो यह सुनिश्चित करता है कि `have[i] >= needed[i]` सभी `i` के लिए।
- मिनिमम विंडो सबस्ट्रिंग को रिटर्न करने के लिए, आपको मिनिमम लेंथ और उस सबस्ट्रिंग के स्टार्टिंग पॉइंट को ट्रैक करना होगा।
- जब भी आपको एक नई मिनिमम लेंथ मिलती है, तो रिजल्ट लेंथ और स्टार्टिंग पॉइंट (जो कि लो पॉइंटर का मान होता है) को अपडेट करें।
- अंत में, मूल स्ट्रिंग S से स्टार्टिंग पॉइंट और मिनिमम लेंथ का उपयोग करके सबस्ट्रिंग निकालें और रिटर्न करें।
समस्या का अंतिम समाधान केवल मिनिमम लेंथ नहीं, बल्कि वास्तविक सबस्ट्रिंग है, इसलिए इसे सही ढंग से निकालना महत्वपूर्ण है।
यदि मिनिमम लेंथ 4 है और स्टार्टिंग पॉइंट 10 है, तो आप स्ट्रिंग S से इंडेक्स 10 से शुरू होने वाले 4 कैरेक्टर का सबस्ट्रिंग रिटर्न करेंगे।
Key takeaways
- रटने के बजाय DSA पैटर्न को समझना इंटरव्यू में सफलता की कुंजी है।
- स्लाइडिंग विंडो पैटर्न स्ट्रिंग-आधारित समस्याओं को कुशलतापूर्वक हल करने के लिए एक शक्तिशाली टूल है।
- मिनिमम या मैक्सिमम विंडो समस्याओं को पहचानने के लिए कंडीशन (जैसे, सम >= K) का विश्लेषण करें।
- फ्रीक्वेंसी काउंटिंग (हैश मैप या एरे का उपयोग करके) स्लाइडिंग विंडो समस्याओं में एक सामान्य तकनीक है।
- एक व्यवस्थित फ्लोचार्ट (हाई को बढ़ाना, कंडीशन चेक करना, लो को सिकोड़ना) अधिकांश स्लाइडिंग विंडो समस्याओं पर लागू होता है।
- इंटरव्यू में, अपने समाधान के पीछे के लॉजिक को समझाने के लिए तैयार रहें, न कि केवल रटे हुए कोड को प्रस्तुत करने के लिए।
Key terms
Sliding Window PatternMinimum Window SubstringFrequency MapHash MapArrayVariable WindowFixed WindowPointer (Low, High)Condition CheckingSubstring
Test your understanding
- स्लाइडिंग विंडो पैटर्न का उपयोग करके मिनिमम विंडो सबस्ट्रिंग समस्या को हल करने के लिए मुख्य चरण क्या हैं?
- आप कैसे पहचानेंगे कि कोई समस्या स्लाइडिंग विंडो पैटर्न का उपयोग करके हल की जा सकती है?
- फ्रीक्वेंसी मैप (जैसे हैश मैप या एरे) स्लाइडिंग विंडो समस्याओं में क्या भूमिका निभाता है?
- मिनिमम विंडो समस्या में, विंडो को सिकोड़ने (shrinking) का लॉजिक क्या है और यह मैक्सिमम विंडो समस्या से कैसे भिन्न हो सकता है?
- इंटरव्यू में रटने के बजाय पैटर्न-आधारित दृष्टिकोण क्यों बेहतर है?