Topological Sort का उपयोग करके Course Schedule II को कैसे हल करें?

प्रश्न और कार्यक्षेत्र (Prompt and Scope)

num_courses कोर्स हैं जिन्हें 0 से num_courses - 1 तक लेबल किया गया है। एक पूर्व-आवश्यकता जोड़ी [course, prerequisite] का अर्थ है कि course से पहले prerequisite को पूरा किया जाना चाहिए। कोई भी ऐसा क्रम लौटाएं जो प्रत्येक कोर्स को पूरा करता हो। यदि ऐसा कोई क्रम मौजूद नहीं है तो एक खाली सूची लौटाएं।

इस संस्करण के लिए, मान लें कि 0 <= num_courses <= 2000 है, प्रत्येक कोर्स लेबल मान्य है, जोड़े अलग (distinct) हैं, और इनपुट में कोई सेल्फ-एज (self-edge) नहीं है। num_courses == 0 होने पर एक खाली सूची लौटाएं। num_courses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]] के लिए, [0, 1, 2, 3] और [0, 2, 1, 3] दोनों सही हैं। [[1, 0], [0, 1]] के लिए, दोनों कोर्स एक दूसरे पर निर्भर करते हैं, इसलिए एकमात्र मान्य उत्तर एक खाली सूची है।

यह एक प्रतिनिधि सामान्य सॉफ्टवेयर-इंजीनियरिंग कोडिंग समस्या है। इसका मुख्य कार्य प्राकृतिक भाषा की निर्भरताओं को एक निर्देशित ग्राफ (directed graph) में बदलना और यह तय करना है कि क्या वह ग्राफ अचक्रीय (acyclic) है। मूल समस्या कोई भी मान्य क्रम मांगती है। यह लेक्सिकोग्राफ़िक रूप से सबसे छोटा क्रम, कोर्स की अवधि, या समवर्ती (concurrent) कोर्स पर कोई सीमा नहीं मांगती है।

इंटरव्यूअर क्या मूल्यांकन करता है

पहला संकेत एज की दिशा (edge direction) है। [course, prerequisite] बन जाता है prerequisite -> course, क्योंकि पूर्व-आवश्यकता को पूरा करने से अगला कोर्स अनलॉक होता है। एक उल्टा ग्राफ अभी भी एक क्रमपरिवर्तन (permutation) उत्पन्न कर सकता है, लेकिन वह क्रमपरिवर्तन विपरीत बाधा (opposite constraint) को एनकोड करता है।

दूसरा संकेत यह है कि क्या उम्मीदवार "वर्तमान में उपलब्ध कोर्स" वाक्यांश से indegree निकाल सकता है। किसी कोर्स की indegree उन प्रत्यक्ष पूर्व-आवश्यकताओं की संख्या है जो अभी भी असंतुष्ट हैं। केवल शून्य-indegree वाला कोर्स ही तैयार होता है। एक कोर्स को पूरा करने से केवल उसके प्रत्यक्ष उत्तराधिकारियों (successors) की indegree घटती है। एक मजबूत उत्तर केवल "BFS का उपयोग करें" कहने के बजाय इस स्थिति की व्याख्या करता है।

तीसरा संकेत चक्र का पता लगाना (cycle detection) है। एक खाली कतार (queue) आंशिक उत्तर लौटाने को सही नहीं ठहराती है। सभी नोड्स केवल तभी संसाधित होते हैं जब परिणाम की लंबाई कोर्स की कुल संख्या के बराबर होती है। एक छोटा परिणाम यह दर्शाता है कि शेष सबग्राफ में कोई शून्य-indegree नोड नहीं है और इसमें एक निर्देशित चक्र (directed cycle) होना चाहिए।

इंटरव्यूअर जटिलता, सीमाओं और अनुबंध अनुशासन की भी जांच करेगा। एक एडजायसेंसी-लिस्ट (adjacency-list) कार्यान्वयन O(V + E) समय और स्थान का उपयोग करता है। deque.popleft() कतार के सामने से हटाने की क्रिया को स्थिर-समय (constant-time) में रखता है। परीक्षणों में कई मान्य ऑर्डर, डिस्कनेक्ट किए गए कोर्स, खाली इनपुट और एक लंबी निर्भरता श्रृंखला शामिल होनी चाहिए।

उत्तर देने से पहले स्पष्टीकरण प्रश्न (Clarifying Questions)

• क्या मैं कोई भी क्रम लौटा सकता हूँ, या यह लेक्सिकोग्राफ़िक रूप से सबसे छोटा होना चाहिए? एक सामान्य कतार कोई भी

क्रम लौटाती है। सबसे छोटे क्रम के लिए min-heap की आवश्यकता होती है और यह समय सीमा को O(E + V log V) में बदल देता है।

• क्या पूर्व-आवश्यकता जोड़े दोहराए जा सकते हैं? इस समस्या में कहा गया है कि वे अलग हैं। यदि वे दोहराए जा सकते हैं, तो या तो

डुप्लिकेट एडजायसेंसी प्रविष्टियाँ रखें और indegree में दोनों की गणना करें, या ग्राफ बनाते समय दोनों संरचनाओं से डुप्लिकेट हटा दें। केवल एक तरफ से डुप्लिकेट हटाने से गिनती असंगत हो जाती है।

• क्या लेबल अमान्य हो सकते हैं, या इनपुट में सेल्फ-एज हो सकते हैं? आधार समस्या मान्य

इनपुट मानती है। एक रक्षात्मक API को एक अमान्य अनुरोध और चक्र वाले एक मान्य ग्राफ के बीच अंतर करना चाहिए, बजाय इसके कि दोनों मामलों को चुपचाप एक खाली सूची में मैप किया जाए।

• क्या हमें एक क्रम की आवश्यकता है या प्रत्येक मान्य क्रम की? एक क्रम खोजना एक रैखिक ग्राफ ट्रैवर्सल है।

प्रत्येक क्रम की गणना वर्तमान में उपलब्ध सभी नोड्स पर शाखाएं बनाती है और लगभग फैक्टोरियल जितने परिणाम उत्पन्न कर सकती है।

• क्या कोर्स समानांतर में चल सकते हैं? मूल परिणाम एक रैखिक क्रम है। असीमित सेमेस्टर

क्षमता के साथ, न्यूनतम सेमेस्टरों के लिए स्तर-दर-स्तर कतार प्रसंस्करण (level-by-level queue processing) की आवश्यकता होती है। कोर्स की अवधि के साथ, समस्या DAG पर सबसे लंबे पथ की गणना (longest-path computation) बन जाती है।

• क्या ग्राफ मेमोरी में फिट बैठता है? V <= 2000 के लिए एक एडजायसेंसी लिस्ट सीधी है। बाहरी

स्टोरेज या पार्टिशन्ड प्रोसेसिंग एक अलग सिस्टम समस्या होगी।

30-सेकंड उत्तर रूपरेखा (Answer Framework)

"मैं प्रत्येक कोर्स को एक नोड के रूप में मॉडल करूँगा और [course, prerequisite] को पूर्व-आवश्यकता से कोर्स की ओर एक एज में बदल दूंगा। मैं प्रत्येक कोर्स की indegree की गणना भी करूँगा। मैं प्रत्येक शून्य-indegree कोर्स को एक कतार में रखूँगा, बार-बार एक को परिणाम में निकालूँगा, उसके उत्तराधिकारियों की indegrees घटाऊँगा, और किसी उत्तराधिकारी की indegree शून्य होने पर उसे कतार में डालूँगा। कतार में केवल वही असंसाधित कोर्स होते हैं जिनकी सभी पूर्व-आवश्यकताएं पूरी हो चुकी हैं, इसलिए प्रत्येक विकल्प सुरक्षित है। यदि परिणाम में प्रत्येक कोर्स शामिल है, तो मैं इसे लौटाता हूँ; अन्यथा शेष नोड्स में एक चक्र होता है, इसलिए मैं एक खाली सूची लौटाता हूँ। एक एडजायसेंसी लिस्ट के साथ, समय और अतिरिक्त स्थान दोनों O(V + E) हैं।"

चरण-दर-चरण गहन विश्लेषण (Step-by-Step Deep Dive)

एक प्रत्यक्ष समाधान बार-बार प्रत्येक अनचयनित कोर्स को स्कैन करता है और एक ऐसा कोर्स चुनता है जिसकी पूर्व-आवश्यकताएं पहले ही आ चुकी हैं। पूर्ण किए गए कोर्स के सेट के साथ भी, प्रत्येक राउंड प्रत्येक एज का निरीक्षण कर सकता है। एक श्रृंखला के लिए V राउंड की आवश्यकता हो सकती है, जिससे सबसे खराब स्थिति O(VE) हो जाती है। संतुष्ट निर्भरताओं की बार-बार पुनर्गणना ही अड़चन (bottleneck) है।

Kahn's एल्गोरिदम उस जानकारी को indegree के रूप में वृद्धिशील (incrementally) रूप से बनाए रखता है। मान लें कि graph[u] में वे कोर्स शामिल हैं जो u को पूरा करने के बाद अनलॉक हो सकते हैं, और indegree[v] शेष v की प्रत्यक्ष पूर्व-आवश्यकताओं की गणना करता है। प्रत्येक [course, prerequisite] के लिए, course को graph[prerequisite] में जोड़ें और indegree[course] को बढ़ाएं।

एल्गोरिदम दो invariants बनाए रखता है:

1. indegree[v] असंसाधित नोड्स से v में आने वाली एजेस की संख्या के बराबर है।
2. कतार में केवल और केवल वही असंसाधित कोर्स शामिल हैं जिनकी शेष indegree शून्य है।

प्रारंभिक गणना पहले invariant को संतुष्ट करती है, और प्रत्येक शून्य-indegree नोड को कतार में जोड़ना दूसरे को स्थापित करता है। जब कोर्स u को हटाया जाता है, तो कोई भी असंसाधित पूर्व-आवश्यकता इसकी ओर इंगित नहीं करती है, इसलिए इसे परिणाम में जोड़ना सुरक्षित है। u को हटाने को graph[u] पर जाकर और प्रत्येक उत्तराधिकारी की indegree को घटाकर दर्शाया जाता है। एक उत्तराधिकारी को कतार में ठीक तब जोड़ा जाता है जब उसकी गिनती पहली बार शून्य तक पहुंचती है, जिससे दोनों invariants सुरक्षित रहते हैं।

from collections import deque


def find_course_order(
    num_courses: int,
    prerequisites: list[list[int]],
) -> list[int]:
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses

    for course, prerequisite in prerequisites:
        graph[prerequisite].append(course)
        indegree[course] += 1

    ready = deque(
        course for course, degree in enumerate(indegree) if degree == 0
    )
    order: list[int] = []

    while ready:
        course = ready.popleft()
        order.append(course)

        for dependent in graph[course]:
            indegree[dependent] -= 1
            if indegree[dependent] == 0:
                ready.append(dependent)

    return order if len(order) == num_courses else []

यदि प्रत्येक कोर्स को हटा दिया जाता है, तो invariants गारंटी देते हैं कि इसकी सभी पूर्व-आवश्यकताएं पहले दिखाई दी थीं, इसलिए परिणाम मान्य है। यदि परिणाम V से छोटा है, तो शेष परिमित (finite) सबग्राफ के प्रत्येक नोड में धनात्मक शेष indegree होती है। किसी भी शेष नोड से शुरू करें और बार-बार एक आने वाले एज का अनुसरण करें। एक सीमित ग्राफ को अंततः एक नोड को दोहराना होगा, और दोहराया गया खंड एक निर्देशित चक्र (directed cycle) है। इसलिए कोई पूर्ण क्रम मौजूद नहीं है। लंबाई की जांच ही चक्र परीक्षण (cycle test) भी है।

प्रत्येक नोड कतार में अधिकतम एक बार प्रवेश करता है और बाहर निकलता है। ग्राफ का निर्माण करते समय और उत्तराधिकारियों को छोड़ते समय प्रत्येक एज को एक बार संभाला जाता है, इसलिए समय O(V + E) है। एडजायसेंसी लिस्ट, indegree ऐरे, कतार और परिणाम O(V + E) स्पेस का उपयोग करते हैं। कार्यान्वयन deque का उपयोग करता है क्योंकि Python का list.pop(0) शेष तत्वों को शिफ्ट करता है और कतार संचालन को रैखिक बना सकता है।

प्रतिकूल सत्यापन (Adversarial validation) को एक निश्चित उत्तर के बजाय गुणों की जांच करनी चाहिए। एक सफल परिणाम में ठीक V अद्वितीय लेबल होने चाहिए, और प्रत्येक जोड़ी के लिए prerequisite की स्थिति course की स्थिति से छोटी होनी चाहिए। एक खाली ग्राफ, एक नोड, सभी-स्वतंत्र नोड्स, एक लंबी श्रृंखला, कई ऑर्डर वाला एक डायमंड, डिस्कनेक्ट किए गए घटक और एक निर्देशित चक्र को कवर करें। डायमंड केस उन परीक्षणों को पकड़ता है जो गलत तरीके से एक विशेष टोपोलॉजिकल क्रम की मांग करते हैं।

DFS भी एक टोपोलॉजिकल क्रम की गणना कर सकता है। सफेद, ग्रे और काले रंगों की अवस्थाओं (states) का उपयोग करें; एक ग्रे नोड की ओर जाने वाला एज चक्र का पता लगाता है, और पोस्टऑर्डर को उलटने से पहले रिकर्सिव निकास पर नोड्स परिणाम में प्रवेश करते हैं। DFS तब उपयोगी होता है जब API को एक ठोस चक्र की रिपोर्ट भी करनी चाहिए, लेकिन एक लंबी श्रृंखला Python की रिकर्शन सीमा को पार कर सकती है। Kahn का एल्गोरिदम वर्तमान में उपलब्ध कोर्स के सेट को प्रदर्शित करता है और समानांतर सेमेस्टरों के लिए स्वाभाविक रूप से विस्तारित होता है, जिससे यह यहाँ अधिक सीधा विकल्प बन जाता है। एक छोटे ग्राफ के लिए जहाँ केवल व्यवहार्यता मायने रखती है, बार-बार स्कैनिंग छोटी हो सकती है; इसकी सबसे खराब स्थिति की लागत बताएं बजाय इसके कि इसे रैखिक कहें।

उच्च गुणवत्ता वाला नमूना उत्तर (High-Quality Sample Answer)

"मैं पहले पुष्टि करूँगा कि कोई भी मान्य क्रम स्वीकार्य है और मानूँगा कि लेबल और विशिष्ट एजेस मान्य हैं। प्रत्येक [course, prerequisite] जोड़ी पूर्व-आवश्यकता से कोर्स तक एक एज बनाती है। फिर किसी कोर्स की indegree यह मापती है कि कितनी प्रत्यक्ष पूर्व-आवश्यकताएं अभी भी अधूरी हैं।

मैं एक एडजायसेंसी लिस्ट और indegree ऐरे बनाता हूँ, फिर प्रत्येक शून्य-indegree कोर्स को एक deque में जोड़ता हूँ। लूप में, मैं उत्तर में एक कोर्स निकालता हूँ और उसके उत्तराधिकारियों की indegrees घटाता हूँ। किसी उत्तराधिकारी को केवल तभी कतार में रखा जाता है जब उसकी indegree शून्य हो जाती है। मुख्य invariant यह है कि कतार में केवल वही कोर्स होते हैं जिनकी कोई अधूरी पूर्व-आवश्यकता नहीं होती है, इसलिए इसमें से चुनने पर किसी एज का उल्लंघन नहीं हो सकता है।

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

एडजायसेंसी लिस्ट प्रत्येक नोड और एज को एक स्थिर संख्या में संसाधित करती है, जिससे O(V + E) समय और O(V + E) स्थान मिलता है। मैं एक खाली ग्राफ, एक नोड, एक लंबी श्रृंखला, कई उत्तरों वाले एक डायमंड, डिस्कनेक्ट किए गए घटकों और दो नोड वाले चक्र का परीक्षण करूँगा। कई उत्तरों के लिए, मैं एक निश्चित ऐरे के साथ तुलना करने के बजाय प्रत्येक पूर्व-आवश्यकता की सापेक्ष स्थिति को मान्य करता हूँ।"

सामान्य गलतियाँ (Common Mistakes)

• course -> prerequisite का निर्माण करना → एक कोर्स अपनी पूर्व-आवश्यकता से पहले दिखाई दे सकता है → prerequisite -> course का निर्माण करें, इस प्रश्न का अनुसरण करते हुए कि 'इस नोड को पूरा करने से क्या अनलॉक होता है?'
• केवल कोर्स 0 से शुरू करना → डिस्कनेक्ट किए गए घटक छूट जाते हैं → प्रत्येक नोड को स्कैन करें और प्रत्येक प्रारंभिक शून्य-indegree नोड को कतार में डालें।
• कतार खाली होने पर आंशिक परिणाम लौटाना → चक्रीय इनपुट को सफलता के रूप में रिपोर्ट किया जाता है → केवल तभी क्रम लौटाएं जब len(order) == num_courses हो।
• किसी नोड को एक से अधिक बार कतार में रखना → परिणाम में डुप्लिकेट कोर्स होते हैं → केवल indegree 1 से 0 के संक्रमण (transition) पर कतार में डालें।
• कतार के रूप में list.pop(0) का उपयोग करना → बड़े इनपुट बार-बार तत्वों को शिफ्ट करते हैं → deque.popleft() का उपयोग करें।
• आउटपुट की तुलना एक निश्चित टोपोलॉजिकल क्रम से करना → दूसरा मान्य क्रम परीक्षण में विफल हो जाता है → विशिष्टता, लंबाई और प्रत्येक एज की सापेक्ष स्थिति की जांच करें।
• ग्राफ से डुप्लिकेट हटाना लेकिन indegree से नहीं, या इसके विपरीत → डुप्लिकेट-एज अनुबंध के तहत गिनती असहमत होती है → डुप्लिकेट को लगातार बनाए रखें या ग्राफ निर्माण के दौरान प्रत्येक एज से डुप्लिकेट हटाएं।
• O(V) अतिरिक्त स्थान का दावा करना → एडजायसेंसी लिस्ट अभी भी सभी एजेस को संग्रहीत करती है → इस विरल-ग्राफ (sparse-graph) प्रतिनिधित्व के लिए O(V + E) की रिपोर्ट करें।
• प्रगतिशील स्थिति (in-progress state) के बिना DFS का उपयोग करना → चक्र नोड्स बार-बार पुनरावृति करते हैं या गलत तरीके से समाप्त होते हैं → सक्रिय और पूर्ण नोड्स को अलग करने के लिए कम से कम तीन स्थितियों का उपयोग करें।

फॉलो-अप और उन्हें कैसे संभालें

फॉलो-अप 1: आप लेक्सिकोग्राफ़िक रूप से सबसे छोटा मान्य क्रम कैसे लौटाएंगे?

कतार को min-heap से बदलें। वर्तमान में उपलब्ध सभी नोड्स में से सबसे छोटा लेबल लेने से ग्रीडी एक्सचेंज तर्क द्वारा लेक्सिकोग्राफ़िक रूप से सबसे छोटा परिणाम मिलता है। एज का काम O(E) रहता है, जबकि हीप प्रविष्टि और निष्कासन कुल मिलाकर O(E + V log V) बनाते हैं। जब कोई भी क्रम स्वीकार्य हो तो एक सामान्य कतार सरल और तेज़ होती है।

फॉलो-अप 2: प्रति सेमेस्टर असीमित समानांतर कोर्स के साथ, न्यूनतम सेमेस्टर गणना क्या है?

कतार को उसके वर्तमान स्तर के आकार (level size) के आधार पर संसाधित करें। एक स्तर के कोर्स एक ही सेमेस्टर में पूरे होते हैं, और उनके नए जारी किए गए शून्य-indegree उत्तराधिकारी अगला स्तर बनाते हैं। प्रति स्तर सेमेस्टर गणना बढ़ाएं। यह केवल तभी काम करता है जब सभी कोर्स समान समय लेते हैं और सेमेस्टर क्षमता असीमित होती है। प्रति सेमेस्टर अधिकतम k कोर्स की सीमा वैश्विक इष्टतमता (global optimality) के लिए सरल स्तर प्रसंस्करण को अपर्याप्त बनाती है।

फॉलो-अप 3: कोर्स की अलग-अलग अवधियां हैं। आप स्नातक होने का सबसे प्रारंभिक समय कैसे खोजेंगे?

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

फॉलो-अप 4: आप एक ठोस निर्भरता चक्र (concrete dependency cycle) कैसे लौटाएंगे?

Kahn का एल्गोरिदम यह साबित करता है कि शेष सबग्राफ में एक चक्र है लेकिन यह उसके पथ को बरकरार नहीं रखता है। शेष नोड्स पर तीन-रंग का DFS चलाएं और पैरेंट पॉइंटर्स स्टोर करें। एक ग्रे नोड की ओर जाने वाले एज पर, चक्र को फिर से बनाने के लिए पैरेंट्स का पीछे की ओर अनुसरण करें। यदि निदान एक प्राथमिक आवश्यकता है, तो शुरुआत से ही पैरेंट-ट्रैकिंग DFS टोपोलॉजिकल सॉर्ट का उपयोग किया जा सकता है।

फॉलो-अप 5: पूर्व-आवश्यकता एजेस जोड़े जाने पर आप एक क्रम कैसे बनाए रखेंगे?

कम लगातार अपडेट के लिए, प्रत्येक प्रविष्टि के बाद O(V + E) एल्गोरिदम को फिर से चलाना सबसे विश्वसनीय और सत्यापित करने में सबसे आसान है। लगातार अपडेट वाले बड़े ग्राफ के लिए, प्रत्येक नोड की वर्तमान स्थिति को स्टोर करें। उस क्रम के साथ पहले से ही सुसंगत एज को किसी बदलाव की आवश्यकता नहीं है; एक असंगत एज के लिए प्रभावित अंतराल के भीतर पहुंच योग्यता जांच (reachability checking) और पुन: क्रमबद्ध करने की आवश्यकता होती है। डायनेमिक टोपोलॉजिकल ऑर्डरिंग जटिल है, इसलिए इसकी लागत को मापे गए ग्राफ आकार और अपडेट दर द्वारा उचित ठहराया जाना चाहिए।

फॉलो-अप 6: आप प्रत्येक मान्य कोर्स क्रम की गणना (enumerate) कैसे करेंगे?

बैकट्रैकिंग का उपयोग करें। प्रत्येक चरण में, सभी वर्तमान शून्य-indegree नोड्स पर शाखा बनाएं, अस्थायी रूप से एक चुनें, उसके उत्तराधिकारियों को अपडेट करें, रिकर्स करें, और indegrees को पुनर्स्थापित करें। यह अमान्य क्रमपरिवर्तनों से बचता है, लेकिन मान्य ऑर्डर की संख्या V! तक पहुंच सकती है, इसलिए रनिंग टाइम कम से कम आउटपुट के आनुपातिक होता है। पहले एक छोटी सीमा की पुष्टि करें और पूछें कि क्या कॉलर को वास्तव में एक गिनती, एक नमूना, या केवल पहले k ऑर्डर की आवश्यकता है।