CareerCup

Create a dependency graph (directed graph) like A -> B if B is dependent on A. After that perform topological sorting on graph. it will provide proper build order.

def getInstallOrder(d):
    # get all modules.
    # assume d is a dictionary of all modules
    installedModules = []
    # install modules that don't have pre-reqs
    for key in d:
        if d[key] == []:
            installedModules.append(key)
    for module in installedModules:
        d.pop(module)

    while d:
        # search RHS / dict values to find all modules satisfied by installedList
        modulesNoLongerNeeded = []
        for key in d:
            modulesNeeded = d[key]
            dependenciesSatisfied = True
            for module in modulesNeeded:
                if module not in installedModules:
                    dependenciesSatisfied = False
            if dependenciesSatisfied:
                installedModules.append(key)
                modulesNoLongerNeeded.append(key)
        for module in modulesNoLongerNeeded:
            d.pop(module)

    return installedModules


d = {1: [2], 2: [4], 3: [], 4: [3]}
print getInstallOrder(d)

Maintain 2 hashmaps of "before" and "after" relationships. In this example, before['A'] = {'B','C'} while after['B'] = {'A'} etc. Keep finding the next module m where before[m] is empty. Then print this module, look up the modules that depend on it from after[m], and remove m from all the corresponding hashmap values.

def build_order(orders):
    before = {}
    after = {}
    for order in orders:
        for module in order:
            before[module] = set()
            after[module] = set()
    for order in orders:
        module = order[0]
        dependents = order[1:]
        for d in dependents:
            before[module].add(d)
            after[d].add(module)
    
    while len(before) > 0:
        for module in before.keys():
            if len(before[module]) == 0:
                print module
                for d in after[module]:
                    before[d].remove(module)
                del before[module]
                break

print build_order(['ABC', 'BDEF', 'DF'])

Convert the dependencies into a Graph and use a Topological Sort. Should be O(m + n) where m is the number of dependencies and n is the number of different modules.

//input dependencies- each char[] is one set of dependencies.  
//[0] is the thing that has dependencies
//[1]..[n] are the things that are needed before the build can happen
public static ArrayList<Character> getBuildOrder(char[][] dependencies){
	if(dependencies == null){
		throw new NullPointerException();
	}
	
	//construct the graph
	Graph g = new Graph();
	for(char[] dependency : dependencies){
		if(dependency == null || dependency.length < 2){
			throw new IllegalArgumentException();
		}
		char from = dependency[0];
		for(int i = 1; i < dependency.length; i++){
			g.addConnection(from, dependency[i]);
		}
	}

	return topologicalSort(g);
}

static final int WORKING = 1;
static final int FINISHED = 2;

private static ArrayList<Character> topologicalSort(Graph g){
	int[] nodeStatus = new int[g.nodes.size()];
	ArrayList<Character> results = new ArrayList<Character>();

	for(Character c : nodes){
		Integer index = g.getIndex(c);
		topologicalSort(g, nodeStatus, results, index);
	}
	return results;
}

private static void topologicalSort(Graph g, int[] nodeStatus, ArrayList<Character> results, Integer index){
	if(nodeStatus[index] == FINISHED){
		continue;
	}
	if(nodeStatus[index] == WORKING){
		throw new IllegalArgumentException("Dependency Cycle Detected");
	}
	nodeStatus[index] = WORKING;
	for(Integer childIndex: g.connections.get(index)){
		topologicalSort(g, nodeStatus, results, childIndex);
	}
	nodeStatus[index] = FINISHED;
	results.add(g.nodes.get(index));
}
			
static class Graph{
	HashMap<Character, Integer> nodeToIndexMap = new HashMap<Character, Integer>();
	ArrayList<Character> nodes = new ArrayList<Character>();
	ArrayList<HashSet<Integer>> connections = new ArrayList<HashSet<Character>>();

	void addConnection(Character from, Character to){
		Integer fromIndex = this.getIndex(from);
		Integer toIndex = this.getIndex(to);
		this.connections.get(fromIndex).add(toIndex);
	}

	Integer getIndex(Character c){
		Integer index = this.nodeToIndexMap.get(c);
		if(index == null){
			index = this.nodes.size();
			this.nodeToIndexMap.put(c, index);
			this.connections.add(new HashSet<Character>());
			this.nodes.add(c);
		}
		return index;
	}
}

Topological sort is what you are talking about
en.wikipedia.org/wiki/Topological_sorting

C++11 implementation using topological sort

#include <map>
#include <set>
#include <stdio.h>
#include <vector>
using namespace std;

typedef map<string, vector<string>> DepMap;

// collect reversed topological sorted order in acc
void Visit(const string &key, DepMap &dm, set<string> &visited, vector<string> &acc) {
  if (visited.find(key) == visited.end()) {
    visited.insert(key);
    for (const auto &dep_key : dm[key])
      Visit(dep_key, dm, visited, acc);
    acc.push_back(key);
  }
}

// DepMap -> build order
vector<string> ModuleBuildOrder(DepMap dm) {
  vector<string> order;
  set<string> visited;
  if (!dm.empty())
    Visit(dm.begin()->first, dm, visited, order);
  return order;
}

int main() {
  vector<string> order = ModuleBuildOrder({
      {"A", {"B", "C"}},
      {"B", {"D", "E", "F"}},
      {"D", {"F"}} });
  for (const auto &s : order)
    printf("%s\n", s.c_str());
}