कोडिंग साक्षात्कार की तैयारी · पाठ

अंतराल DP पैटर्न और भरने का क्रम

Q: क्या “अंतराल DP पैटर्न और भरने का क्रम” पाठ निःशुल्क है?

हाँ—“अंतराल DP पैटर्न और भरने का क्रम” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

Q: क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?

पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 1वाँ पाठ है।

Q: “अंतराल DP पैटर्न और भरने का क्रम” पाठ पूरा करने में कितना समय लगता है?

CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।

Q: क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?

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

अंतराल DP स्थिति dp[i][j] परिभाषित कीजिए, समझाइए कि अंतरालों को बढ़ती लंबाई के क्रम में क्यों भरना चाहिए, और मैट्रिक्स चेन गुणन पर इस पैटर्न को ट्रेस कीजिए।

पाठ 1, कुल 4 में से13 चरण

अंतराल DP पैटर्न और भरने का क्रम, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 1वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

अंतराल DP क्या है

अंतराल DP एक डायनेमिक प्रोग्रामिंग पैटर्न है, जिसमें अवस्था dp[i][j] उन सूचकांकों i से j तक फैली उपसमस्या के सर्वोत्तम उत्तर को दर्शाती है। मुख्य अंतर्दृष्टि यह है कि हम पहले छोटे अंतराल हल करते हैं और फिर पूरे क्षेत्र तक पहुँचते हैं। यह पैटर्न स्वाभाविक रूप से मैट्रिक्स श्रृंखला गुणन, पैलिन्ड्रोम विभाजन और गुब्बारे फोड़ने जैसी समस्याओं का मॉडल बनाता है, जहाँ उपसमस्या की सीमाएँ किसी क्षेत्र की बाईं और दाईं अंतिम सीमाएँ होती हैं।

अवस्था की परिभाषा और आधार मामले

अंतराल DP में अवस्था dp[i][j] होती है, जहाँ i <= j। आधार मामले एकल-तत्व वाले अंतराल होते हैं: dp[i][i]। ये आसानी से हल हो जाते हैं — उदाहरण के लिए, एकल मैट्रिक्स की गुणन लागत शून्य होती है। दो-तत्व वाले अंतराल dp[i][i+1] के उत्तर भी अक्सर सरल होते हैं। हम लंबाई 1 से n तक बढ़ती हुई अंतराल लंबाइयों के क्रम में तालिका भरते हैं।

n = 4
dp = [[0] * n for _ in range(n)]
# Base cases: single elements
for i in range(n):
    dp[i][i] = 0  # length-1 intervals

भरने का क्रम: बढ़ती हुई लंबाई

अंतराल DP में महत्वपूर्ण विवरण भरने का क्रम है। हमें लंबाई L वाले सभी अंतरालों की गणना लंबाई L+1 वाले अंतरालों से पहले करनी चाहिए, क्योंकि लंबा अंतराल छोटे उप-अंतरालों पर निर्भर करता है। बाहरी लूप अंतराल की लंबाई को 2 से n तक चलाता है, बीच वाला लूप बाईं सीमा i निर्धारित करता है, और हम दाईं सीमा j = i + L - 1 के रूप में निकालते हैं।

n = 5
dp = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = 0

for length in range(2, n + 1):      # interval length
    for i in range(n - length + 1): # left boundary
        j = i + length - 1          # right boundary
        for k in range(i, j):       # split point
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])

मैट्रिक्स श्रृंखला गुणन की तैयारी

क्लासिक अंतराल DP समस्या मैट्रिक्स श्रृंखला गुणन है: dims[0..n] आयामों वाले मैट्रिक्स दिए हों, तो गुणनफल निकालने के लिए आवश्यक न्यूनतम अदिश गुणनों की संख्या ज्ञात करें। मैट्रिक्स A(p×q) को B(q×r) से गुणा करने में p*q*r संक्रियाएँ लगती हैं। dp[i][j] = मैट्रिक्स i से j तक गुणा करने की न्यूनतम लागत। विभाजन बिंदु k तय करता है कि श्रृंखला को दो उप-श्रृंखलाओं में कहाँ बाँटना है।

def matrix_chain_order(dims):
    n = len(dims) - 1  # number of matrices
    dp = [[0] * n for _ in range(n)]
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n-1]

print(matrix_chain_order([10, 30, 5, 60]))  # 4500

DP तालिका का अनुकरण

आइए [10, 30, 5, 60] आयामों वाले मैट्रिक्स श्रृंखला उदाहरण को देखें, जो तीन मैट्रिक्स दर्शाते हैं: A(10×30), B(30×5), C(5×60)। dp[0][2] के लिए हम k=0 पर विभाजन आज़माते हैं: dp[0][0] + dp[1][2] + 10×30×60 = 0 + 9000 + 18000 = 27000, और k=1 पर: dp[0][1] + dp[2][2] + 10×5×60 = 1500 + 0 + 3000 = 4500। इसलिए dp[0][2] = 4500, जो पहले AB का गुणन करने पर प्राप्त होता है।

यह भरने का क्रम क्यों काम करता है

dp[i][j] की गणना करते समय हम सभी k के लिए [i, j-1] में dp[i][k] और dp[k+1][j] का संदर्भ लेते हैं। दोनों उप-अंतरालों की लंबाई [i, j] से सख्ती से कम होती है। लंबाई को छोटी से बड़ी दिशा में चलाने पर सभी आवश्यक उप-अंतरालों की गणना उनसे पहले हो जाती है। अंतराल DP के भरने के क्रम की शुद्धता का यह मूल तर्क है — छोटे अंतराल हमेशा बड़े अंतरालों की निर्भरताएँ होते हैं।

स्मृति-संग्रहीत टॉप-डाउन अंतराल DP

वैकल्पिक रूप से, अंतराल DP को स्मृति-संग्रहण के साथ टॉप-डाउन तरीके से लागू किया जा सकता है। हम एक पुनरावर्ती फ़ंक्शन solve(i, j) लिखते हैं, जो अंतराल [i, j] की इष्टतम लागत लौटाता है, और परिणामों को एक शब्दकोश में संग्रहीत करता है। भरने का क्रम पुनरावर्तन द्वारा अपने-आप संभाल लिया जाता है। टॉप-डाउन तरीके को समझना अक्सर आसान होता है, लेकिन इसमें फ़ंक्शन बुलाने का अतिरिक्त खर्च हो सकता है; बड़े आगतों के लिए व्यवहार में बॉटम-अप तरीका तेज़ होता है।

from functools import lru_cache

def matrix_chain_memo(dims):
    n = len(dims) - 1
    
    @lru_cache(maxsize=None)
    def solve(i, j):
        if i == j:
            return 0
        return min(
            solve(i, k) + solve(k+1, j) + dims[i]*dims[k+1]*dims[j+1]
            for k in range(i, j)
        )
    
    return solve(0, n-1)

print(matrix_chain_memo([10, 30, 5, 60]))  # 4500

समय और स्थान की जटिलता

अंतराल DP में O(n²) अवस्थाएँ होती हैं (सभी युग्म (i, j)) और प्रत्येक अवस्था O(n) विभाजन बिंदुओं पर चलती है, इसलिए कुल मिलाकर O(n³) time लगता है। DP तालिका के लिए स्थान O(n²) है। 100 मैट्रिक्स वाली मैट्रिक्स श्रृंखला के लिए यह 1,000,000 संक्रियाएँ हैं — बहुत आसानी से संभव। यह पैटर्न कई कठिन LeetCode समस्याओं में दिखाई देता है और इसकी गैर-स्पष्ट संरचना के कारण FAANG साक्षात्कारों में पसंदीदा है।

इष्टतम solution का पुनर्निर्माण

वास्तविक कोष्ठकीकरण (सिर्फ लागत नहीं) पुनर्निर्मित करने के लिए, एक अलग split[i][j] तालिका रखें, जिसमें हर अवस्था पर न्यूनतम लागत देने वाला k दर्ज हो। फिर विभाजनों को पुनरावर्ती रूप से पढ़ें: reconstruct(i, j), [i, split[i][j]] और [split[i][j]+1, j] पर पुनरावर्तन करके इष्टतम समूहबद्धता प्रदर्शित करता है। यह तकनीक सभी अंतराल DP समस्याओं पर लागू होती है।

def matrix_chain_with_split(dims):
    n = len(dims) - 1
    dp = [[0]*n for _ in range(n)]
    split = [[0]*n for _ in range(n)]
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
                if cost < dp[i][j]:
                    dp[i][j] = cost
                    split[i][j] = k
    return dp[0][n-1], split

किसी भी अंतराल DP समस्या का खाका

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

def interval_dp_template(n, base_cost, split_cost):
    dp = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = base_cost(i)  # problem-specific base case
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):
                # problem-specific recurrence
                candidate = dp[i][k] + dp[k+1][j] + split_cost(i, k, j)
                dp[i][j] = min(dp[i][j], candidate)
    
    return dp[0][n-1]

अंतराल DP की सामान्य समस्याएँ

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

त्वरित जाँच

इस पाठ में पढ़ी गई डेटा संरचनाएँ एवं एल्गोरिदम — कोडिंग साक्षात्कार तैयारी की अवधारणाओं की अपनी समझ का परीक्षण करें।

इंटरैक्टिव पाठ में इसका उत्तर दें

पाठ का पुनरावलोकन

इस पाठ में आपने सीखा: अंतराल DP किसी क्षेत्र पर इष्टतम उत्तर दर्शाने के लिए dp[i][j] का उपयोग करता है, भरने का क्रम बढ़ती हुई अंतराल लंबाई का होना चाहिए ताकि उप-अंतरालों की गणना पहले हो, और सार्वत्रिक खाके में O(n³) time और O(n²) स्थान लगता है। आगे हम इसी पैटर्न का उपयोग करके सबसे लंबे पैलिन्ड्रोमिक उपअनुक्रम और सब्स्ट्रिंग का अध्ययन करेंगे।

शुरुआत निःशुल्क

एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क

अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।

पाठ्यक्रम: 90
पाठ: 360

निःशुल्क सीखना शुरू करें पूरा पाठ्यक्रम देखें

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

क्या “अंतराल DP पैटर्न और भरने का क्रम” पाठ निःशुल्क है?

हाँ—“अंतराल DP पैटर्न और भरने का क्रम” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।