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

Longest Increasing Subsequence

O(n^2) DP और फिर O(n log n) की तरकीब

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

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

LIS क्या है

एक उपअनुक्रम क्रम बनाए रखता है, लेकिन कुछ तत्व छोड़ सकता है। सबसे लंबा बढ़ता हुआ उपअनुक्रम वह सबसे लंबी श्रृंखला है जो सख्ती से बढ़ती है।

a = [3, 1, 4, 1, 5, 9, 2]

उपअनुक्रम, उपसरणी नहीं

उपसरणी के विपरीत, LIS का सन्निहित होना आवश्यक नहीं है। श्रृंखला को बढ़ाते रहने के लिए आप छोटे अंकों को छोड़ सकते हैं।

O(n^2) DP अवस्था

मान लीजिए dp[i], सूचकांक i पर समाप्त होने वाले LIS की लंबाई है। हर तत्व अपने-आप में कम-से-कम लंबाई एक का उपअनुक्रम होता है।

dp = [1] * n

O(n^2) संक्रमण

हर i के लिए, उससे पहले के प्रत्येक j को देखिए। यदि a[j] छोटा है, तो उसे बढ़ाइए: dp[i] = max(dp[i], dp[j] + 1)।

for i in range(n):
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j]+1)

उत्तर पढ़ें

परिणाम सारणी का सबसे बड़ा मान है, क्योंकि LIS कहीं भी समाप्त हो सकता है, केवल अंतिम सूचकांक पर नहीं।

answer = max(dp)

O(n^2) से TLE क्यों हो सकता है

दोहरा लूप O(n squared) लागत लेता है। n के लगभग 100000 होने पर यह बहुत धीमा है और समय-सीमा वाला निर्णय मिलता है।

पेशेंस का विचार

तेज़ विधि हर उपअनुक्रम की लंबाई के लिए सबसे छोटा संभव अंतिम तत्व रखती है, कुछ-कुछ पेशेंस सॉर्टिंग की तरह।

tails = []

स्थान तय करने के लिए द्विभाजन का उपयोग करें

हर संख्या के लिए, अंतिम तत्वों के बीच उसका स्थान bisect_left से द्विआधारी खोज द्वारा तय कीजिए; इस तरह कुल समय O(n log n) रहता है।

from bisect import bisect_left

बढ़ाएँ या बदलें

यदि स्थान अंतिम तत्व के बाद है, तो LIS को बढ़ाने के लिए append कीजिए। अन्यथा उस अंतिम तत्व को छोटी मान से बदल दीजिए।

i = bisect_left(tails, x)
if i == len(tails):
    tails.append(x)
else:
    tails[i] = x

लंबाई tails में रहती है

स्कैन समाप्त होने पर len(tails) ही LIS की लंबाई होती है। स्वयं सूची हमेशा उपअनुक्रम नहीं होती; केवल उसकी लंबाई निश्चित रूप से सही होती है।

answer = len(tails)

सख्ती से बढ़ता बनाम घटित न होने वाला

घटित न होने वाले रूप के लिए bisect_right का उपयोग कीजिए, ताकि समान मान भी श्रृंखला को बढ़ा सकें।

from bisect import bisect_right

त्वरित जाँच

O(n log n) में LIS की लंबाई कौन-सी विधि ढूँढ़ती है?

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

पुनरावृत्ति: n^2 से n log n तक

अब आप LIS को दो तरीकों से हल कर सकते हैं। O(n^2) DP सरल है; tails और द्विभाजन वाली विधि बड़ी दी गई सूचियों पर भी अच्छी तरह काम करती है और समय-सीमा पार नहीं होने देती।

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

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

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

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

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

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

क्या “Longest Increasing Subsequence” पाठ निःशुल्क है?

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

“Longest Increasing Subsequence” में मैं क्या सीखूँगा?

O(n^2) DP और फिर O(n log n) की तरकीब आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।

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

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

“Longest Increasing Subsequence” पाठ पूरा करने में कितना समय लगता है?

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

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

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

इस पाठ्यक्रम के सभी पाठ

← कोडिंग साक्षात्कार की तैयारी पर वापस जाएँ