# Build Order

4.7 Build Order: You are given a list of projects and a list of dependencies (which is a list of pairs of projects, where the second project is dependent on the first project). All of a project's dependencies must be built before the project is. Find a build order that will allow the projects to be built. If there is no valid build order, return an error.

* The idea with this problem is to build a graph that represents the dependencies provided. However, the direction we chose to do so is important. In the example, (a d) implies that a is dependent on d, or we can write that as (a->d) in the graph. However, because we can trying to prioritize the things the depend on nothing first, then I chose to write it the other way (d->a). This, in the beginning, I will have dependencies f and e empty.
* Faults in this implementation: In my linked list implementation, I am lazy and havent bothered to handle memory leaks. Also, there is a more elegent solution to removal all element of val.

EXAMPLE

```
Input:
projects: a, b, c, d, e, f
dependencies: (a, d), (f, b), (b, d), (f, a), (d, c)
Output: f, e, a, b, d, c
```

```cpp
class Node {
public:
    Node(char val) : data(val) {
        next = nullptr;
    }
    char data;
    int weight;
    Node *next;
};


class LL {
public:
    LL() {
        front = end = nullptr;
    }

    void push_back(char vertex) {
        Node *newNode = new Node(vertex);

        if (isEmpty()) {
            front = end = newNode;
        }
        else {
            end->next = newNode;
            end = newNode;
        }
    }

    void removeAll(char ch) {
        if (isEmpty()) return;

        // first element
        Node *newFront = nullptr;

        if (front->data != ch) {
            newFront = front;
        }

        Node *newIter = newFront;
        Node *iter = front;

        iter = iter->next;

        while (iter) {
            if (iter->data != ch) {
                if (newIter) {
                    newIter->next = iter;
                    newIter = iter;
                }
                else {
                    newIter = iter;
                }
            }
            iter = iter->next;
        }
        if (newIter) {
            newIter->next = nullptr;
        }
        front = newFront;
    }

    void print(Node *iter) {
        if (!iter) return;
        cout << iter->data << " -> ";
        print(iter->next);
    }

    Node *front, *end;

private:


    bool isEmpty() {
        return front == nullptr;
    }
};

// simulating friend network
class Graph {
public:
    Graph(bool dir) : directed(dir), n_verticies(0), n_edges(0) {
    }


    void insertProjects(vector<char> &p) {
        for (auto &i : p) {
            LL *ll = new LL();
            graph2.insert({ {i} ,{ll} });
        }

    }

    void insertNodes(vector<pair<char, char>> &depend) {
        for (auto &i : depend) {
            auto &find = graph2.find(i.second);
            if (find != graph2.end()) {
                // insert first element, since found
                find->second->push_back(i.first);
            }
        }
    }

    vector<char> definePriority(vector<char> &projects, vector<pair<char, char>> &depend) {
        insertProjects(projects);
        insertNodes(depend);

        vector<char> priority;
        // scan through list and find first null element
        bool flag = true;
        while (flag) {
            flag = false;
            for (auto &i : graph2) {
                if (i.second->front == nullptr) {
                    tranverse();
                    priority.push_back(i.first);
                    removeAllDependancies(i.first);
                    // reset for loop and scan through again
                    flag = true;
                    break;
                }
            }
        }

        return priority;
    }

    void removeAllDependancies(char i) {
        //graph2.find(i)->second->front = nullptr;
        delete graph2.find(i)->second;
        graph2.erase(i);
        for (auto &j : graph2) {
            j.second->removeAll(i);
        }
    }

    void tranverse() {
        for (auto &i : graph2) {
            cout << i.first << " : ";
            i.second->print(i.second->front);
            cout << endl;
        }
        cout << endl;
        //pause();
    }

    int getNumVert() { return n_verticies; }
    int getNumEdges() { return n_edges; }

private:
    bool directed;
    int n_verticies, n_edges;

    unordered_map<char, LL*> graph2;

};

int main()
{
    Graph *friend_network = new Graph(true);

    vector<char> projects = { 'a','b','c','d','e','f' };
    vector<pair<char, char>> depend = {
        {'a', 'd'},{ 'f', 'b' },{ 'b', 'd' },{ 'f', 'a' },{ 'd', 'c' }
    };

    vector<char> priority = friend_network->definePriority(projects, depend);
    print(priority);
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/coding_practice_questions/interview_questions/build-order.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.