बिल्ड ऑर्डर: प्रोजेक्ट निर्भरता और टोपोलॉजिकल क्रम (जावा)

टीएल;डीआर

• समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
• दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ४.७: प्रोजेक्ट और निर्भरता युग्म, वैध बिल्ड क्रम निकालो या चक्र हो तो विफल। साफ जावा में कान इंडिग्री कतार और डीएफएस।
• जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

एक छोटा मोनोरिपो चलाते हो। पैकेज d को पहले a और b चाहिए। पैकेज c को d चाहिए। पैकेज b को f चाहिए। गलत क्रम में कंपाइल करो तो बिल्ड टूट जाता है। दो पैकेज एक-दूसरे पर निर्भर हों तो कोई क्रम काम नहीं करता और त्रुटि देनी होती है। यही बिल्ड ऑर्डर है: प्रोजेक्टों की सूची और निर्भरता के किनारे, फिर हर किनारे का सम्मान करने वाला सुरक्षित क्रम।

यह पोस्ट जावा में बिल्कुल शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू वाली निर्भरता-ग्राफ समस्याओं का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ४, ट्री और ग्राफ।

---

१. रोज़मर्रा की उपमा

कई व्यंजनों वाला खाना सोचो जहाँ कुछ व्यंजन दूसरों से पहले पूरे होने चाहिए:

• प्रोजेक्ट व्यंजन हैं: सूप, ब्रेड, मुख्य, मिठाई।
• निर्भरता (A, B) का मतलब: "बी को पहले ए तैयार चाहिए।" ए पूरा होने से पहले बी नहीं परोसो।
• वैध बिल्ड क्रम कोई भी अनुक्रम है जो हर "पहले चाहिए" नियम मानता है। एक से अधिक वैध अनुक्रम हो सकते हैं।
• चक्र है "सूप को ब्रेड चाहिए और ब्रेड को सूप।" कोई रसोई यह खत्म नहीं कर पाती। त्रुटि बताओ।

हर व्यंजन को नोड बनाओ। जब बी ए पर निर्भर हो तो ए से बी तीर खींचो (A → B मतलब ए को बी से पहले बनाओ)। ग्राफ निर्देशित है। चाहिए उस ग्राफ का टोपोलॉजिकल क्रम: हर किनारा सूची में पहले से बाद की ओर जाए।

ग्राफ में चक्र हो तो कोई टोपोलॉजिकल क्रम नहीं। इंटरव्यू का मुख्य मुद्दा यही है।

---

२. समस्या सादे शब्दों में

इनपुट:

• projects: प्रोजेक्ट नामों की सूची (स्ट्रिंग, या कोई तुलनीय पहचान)।
• dependencies: युग्मों की सूची (before, after) जहाँ after before पर निर्भर है। पहले before बनाओ।

आउटपुट:

• सभी प्रोजेक्टों की क्रमबद्ध सूची जो हर निर्भरता मानती हो, या
• ऐसा क्रम न हो तो त्रुटि संकेत (चक्र, या गायब प्रोजेक्ट का वह ठेका जो तुम तय करो)।

क्लासिक नमूना:

वस्तु	मान
प्रोजेक्ट	a, b, c, d, e, f
निर्भरताएँ	(a, d), (f, b), (b, d), (f, a), (d, c)
एक वैध क्रम	f, e, a, b, d, c (या अन्य वैध क्रम-परिवर्तन)

युग्म ध्यान से पढ़ो। (a, d) का मतलब डी, ए पर निर्भर, इसलिए ए, डी से पहले। किनारा a → d।

कोड से पहले स्पष्ट करो:

• नाम अद्वितीय? (हाँ। उन्हें नोड पहचान मानो।)
• प्रोजेक्ट dependencies में हो और projects में न हो? (आमतौर पर नहीं। जाँचो या जोड़ो। ठेका चुनो।)
• स्व-निर्भरता (x, x)? (लंबाई १ का चक्र। विफल।)
• कई वैध क्रम: कोई एक ठीक, जब तक वे सब क्रम न माँगें (वह अलग समस्या)।
• विफलता पर वापसी: null, खाली सूची, या थ्रो। ज़ोर से बोलो।

---

३. पहले सोचो

ग्राफ मॉडल

निर्देशित ग्राफ बनाओ:

• हर प्रोजेक्ट एक नोड।
• हर निर्भरता (before, after) पर किनारा before → after जोड़ो।
• इंडिग्री रखो: कितने प्रोजेक्ट पूरे होने के बाद यह शुरू हो सकता है।

इंडिग्री ० वाले प्रोजेक्ट के कोई बाकी अवरोधक नहीं। वे अगले बिल्ड में जा सकते हैं।

तरीका क: कान (इंडिग्री + कतार)

इंटरव्यू का साफ डिफ़ॉल्ट।

१. आसन्न सूची बनाओ: हर प्रोजेक्ट से उन प्रोजेक्टों की सूची जो उस पर निर्भर हैं। २. हर प्रोजेक्ट की इंडिग्री गिनो। ३. इंडिग्री ० वाले हर प्रोजेक्ट को कतार (या कोई फीफो / जहाँ से निकालते हो) में डालो। ४. जब तक कतार खाली न हो:

• p निकालो, परिणाम क्रम में जोड़ो।
• p के हर पड़ोसी n की indegree[n] घटाओ। ० हो जाए तो n कतार में डालो। ५. अगर result.size() == projects.length तो क्रम लौटाओ। नहीं तो चक्र (या कभी न निकलने वाला उलझाव) ने कुछ नोड रोके: त्रुटि।

क्यों चलता है: प्रोजेक्ट तभी भेजते हो जब उसके सभी पूर्वज पहले भेज चुके हों। चक्र हो तो वे नोड कभी इंडिग्री ० नहीं पहुँचते, कतार जल्दी खाली हो जाती है।

तरीका ख: रंगों वाला डीएफएस

१. अवस्थाएँ: 0 न देखा, 1 देख रहे (वर्तमान रिकर्शन स्टैक पर), 2 पूरा। २. हर न देखे नोड से डीएफएस। जब सचमुच नोड छोड़ो (पोस्ट-ऑर्डर), स्टैक पर धक्का दो (या सूची के आगे रखो)। ३. कभी 1 नोड में किनारा लगे तो वापसी किनारा मिला: चक्र → त्रुटि। ४. अंत में पोस्ट-ऑर्डर सूची उलटाओ (या स्टैक से निकालो) बिल्ड क्रम के लिए।

समान एसिम्प्टोटिक लागत। कान "तैयार कतार" कहानी से अक्सर आसान। डीएफएस तब सहज जब ट्री रिकर्शन पहले से आदत में हो।

क्या न करो

• सारे क्रम-परिवर्तन आज़माना: एन! इंटरव्यू जवाब नहीं।
• इंडिग्री के बिना बीएफएस: "सभी माता-पिता पूरे" का संकेत खो जाता है।
• सिर्फ नाम अक्षरक्रम से छाँटना: किनारे नज़रअंदाज़।

---

४. जावा समाधान (कान)

import java.util.*;

public class BuildOrder {

    /**
     * @param projects list of project names
     * @param dependencies each pair [before, after]: after depends on before
     * @return a valid build order, or null if a cycle (or incomplete graph) blocks one
     */
    public static String[] findBuildOrder(String[] projects, String[][] dependencies) {
        Map<String, List<String>> graph = new HashMap<>();
        Map<String, Integer> indegree = new HashMap<>();

        for (String p : projects) {
            graph.put(p, new ArrayList<>());
            indegree.put(p, 0);
        }

        for (String[] dep : dependencies) {
            String before = dep[0];
            String after = dep[1];
            if (!graph.containsKey(before) || !graph.containsKey(after)) {
                // dependency names a project we do not know: treat as error
                return null;
            }
            graph.get(before).add(after);
            indegree.put(after, indegree.get(after) + 1);
        }

        Queue<String> ready = new ArrayDeque<>();
        for (String p : projects) {
            if (indegree.get(p) == 0) {
                ready.add(p);
            }
        }

        List<String> order = new ArrayList<>();
        while (!ready.isEmpty()) {
            String p = ready.poll();
            order.add(p);
            for (String next : graph.get(p)) {
                int d = indegree.get(next) - 1;
                indegree.put(next, d);
                if (d == 0) {
                    ready.add(next);
                }
            }
        }

        if (order.size() != projects.length) {
            return null; // cycle: some projects never became ready
        }
        return order.toArray(new String[0]);
    }
}

नमूने का चलना:

कदम	तैयार कतार (उदाहरण)	अब तक बिल्ड	टिप्पणी
शुरू	f, e (इंडिग्री ०)	-	a को f का इंतज़ार; b को f; बाकी भी
लो f	e, a, b	f	f खत्म होने पर a और b खुलते हैं
लो e	a, b	f, e	इस नमूने में e के कोई आश्रित नहीं
लो a	b	f, e, a	d को अभी b भी चाहिए
लो b	d	f, e, a, b	d के दोनों माता-पिता पूरे → इंडिग्री ०
लो d	c	f, e, a, b, d	c खुलता है
लो c	खाली	f, e, a, b, d, c	आकार मेल → सफलता

इंडिग्री ० नोडों के बीच कतार क्रम अद्वितीय नहीं। e बाद में लेना भी ठीक: f, a, b, d, c, e भी चलता है।

वैकल्पिक डीएफएस खाका

// 0 = unvisited, 1 = visiting, 2 = done
// return false from dfs if cycle detected
boolean dfs(String node, Map<String, List<String>> graph,
            Map<String, Integer> state, Deque<String> stack) {
    state.put(node, 1);
    for (String next : graph.get(node)) {
        int s = state.get(next);
        if (s == 1) {
            return false; // back edge
        }
        if (s == 0 && !dfs(next, graph, state, stack)) {
            return false;
        }
    }
    state.put(node, 2);
    stack.push(node); // post-order: dependents already pushed under us
    return true;
}

हर न देखे प्रोजेक्ट पर dfs बुलाओ। सब सफल हों तो स्टैक निकालकर परिणाम ऐरे भरो। वही चक्र नियम: स्लेटी से स्लेटी किनारा विफल।

---

५. जटिलता तालिका

हिस्सा	समय	स्थान
ग्राफ + इंडिग्री बनाना	ओ(वी + ई)	ओ(वी + ई)
कान प्रक्रिया	ओ(वी + ई)	कतार और क्रम के लिए ओ(वी)
डीएफएस प्रक्रिया	ओ(वी + ई)	सबसे खराब ओ(वी) रिकर्शन + स्टैक
कुल	ओ(वी + ई)	ओ(वी + ई)

V प्रोजेक्ट संख्या, E निर्भरता युग्म संख्या। दोनों तरीके ग्राफ के आकार में रैखिक। यह इष्टतम है: हर किनारा कम से कम एक बार पढ़ना पड़ता है।

---

६. किनारे के मामले और आम गलतियाँ

इंटरव्यूअर ये छूते हैं:

• खाली प्रोजेक्ट सूची → खाली क्रम ठीक।
• बिना निर्भरता वाले प्रोजेक्ट → सब तुरंत तैयार समूह में; कोई भी क्रम-परिवर्तन वैध।
• एक प्रोजेक्ट, कोई किनारा नहीं → [वही प्रोजेक्ट]।
• स्व-किनारा (x, x) → एक्स की इंडिग्री कभी साफ नहीं, या डीएफएस वापसी किनारा देखता है। त्रुटि।
• साधारण चक्र a → b → a → कतार बचे नोडों के साथ खाली होने पर त्रुटि।
• निर्भरता में गायब प्रोजेक्ट का नाम → तय करो: त्रुटि बनाम बना देना। ऊपर का कोड त्रुटि लौटाता है।
• डुप्लिकेट निर्भरता युग्म → बिना सोचे दो बार जोड़ोगे तो इंडिग्री दोगुनी। किनारे अनोखे करो, या इनपुट में अद्वितीय युग्म मानो।

आम गलतियाँ:

१. किनारा उलटना। (a, d) मतलब डी, ए पर निर्भर। किनारा a → d है, d → a नहीं। उलटा तो चक्र न हो तब भी क्रम गलत। २. इंडिग्री ० और बिना किनारे वाले प्रोजेक्ट भूलना। अकेले प्रोजेक्ट भी क्रम में आते हैं। ३. कतार खाली होने पर आकार की तुलना न करना। चक्र चूकने का ठीक वही तरीका। ४. मूल निर्भरता सूची को ही एकमात्र संरचना मानकर बदलना। आसन्न मैप बनाओ; इनपुट मत नष्ट करो। ५. अद्वितीय क्रम मान लेना। कई डैग के कई टोपोलॉजिकल क्रम होते हैं। जब तक न कहा जाए, कोई भी वैध लौटाओ। ६. अनिर्देशित सोच। यह ग्राफ निर्देशित है। किनारा सिर्फ एक दिशा बाँधता है।

न्यूनतम उपयोग:

String[] projects = {"a", "b", "c", "d", "e", "f"};
String[][] deps = {
    {"a", "d"}, {"f", "b"}, {"b", "d"}, {"f", "a"}, {"d", "c"}
};
String[] order = BuildOrder.findBuildOrder(projects, deps);
// non-null example: [f, e, a, b, d, c]

---

७. दोस्त को समझाओ सार

बिल्ड ऑर्डर प्रोजेक्ट निर्भरता ग्राफ पर टोपोलॉजिकल क्रम है:

१. हर प्रोजेक्ट एक नोड। जब आफ्टर को बिफोर चाहिए तो किनारा before → after। २. कान: इंडिग्री ० से शुरू, प्रोजेक्ट निकालो, पड़ोसी खोलो, दोहराओ। सब न निकाल पाओ तो चक्र है। ३. डीएफएस: रिकर्शन, वापसी किनारे पर विफल (फिर स्लेटी में), उल्टे पोस्ट-ऑर्डर में निकालो। ४. समय ओ(वी + ई)। ग्राफ के लिए स्थान ओ(वी + ई)। ५. कई जवाब सही हो सकते हैं। सिर्फ चक्र (या अमान्य इनपुट) पर त्रुटि।

तीर सही दिशा में खींच सको, तैयार कतार भर सको, और बचे नोड चक्र क्यों हैं समझा सको, तो समस्या ४.७ तुम्हारी। वही कौशल पैकेज प्रबंधक, सीआई पाइपलाइन और कोर्स-पूर्वापेक्षा योजना में दिखता है।

---

श्रृंखला

• गाइड: सीटीसीआई सीरीज़ गाइड
• पिछला: सक्सेसर
• अगला: फर्स्ट कॉमन ऐन्सेस्टर