BuildOrder (_4_7)

BuildOrder.java

import java.util.*;

/**
 * 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'sdependencies 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.
 * <p>
 * EXAMPLE
 * Input:
 * projects: a, b, c, d, e, f
 * dependencies: (a, d), (f, b), (b, d), (f, a), (d, c)
 * <p>
 * Output: f, e, a, b, d, c
 * Hints: #26, #47, #60, #85, # 125, # 733
 */
public class BuildOrder {
    public static void main(String[] args) {
        List<String> projects = new ArrayList<>();
        projects.add("a");
        projects.add("b");
        projects.add("c");
        projects.add("d");
        projects.add("e");
        projects.add("f");

        Map<String, String> dependencies = new HashMap<>();
        dependencies.put("a", "d");
        dependencies.put("f", "b");
        dependencies.put("b", "d");
        dependencies.put("f", "a");
        dependencies.put("d", "c");

        System.out.println(solution1(projects, dependencies)); // expected output: [f, e, b, a, d, c]

        dependencies.put("d", "b");
        System.out.println(solution1(projects, dependencies)); // expected output: null
    }


    public static LinkedList<String> solution1(List<String> proj, Map<String, String> dep) {
        LinkedList<String> result = new LinkedList<>();

        for (int i = 0; i < proj.size(); i++) {
            if (!result.contains(proj.get(i))) {
                result.addFirst(proj.get(i));
            }

            String next = proj.get(i);
            while (dep.containsKey(next)) {
                System.out.print(".");
                String key = dep.get(next);
                next = dep.get(next);
                String value = dep.get(next);

                if (key.equals(dep.get(value)) && value.equals(dep.get(key))) {
                    return null;
                }

                if (!result.contains(next)) {
                    result.addLast(next);
                }
            }
        }

        return result;
    }
}