Java Machine Coding: Building a Dependency Resolver with Topological Sort

Java Machine Coding: Building a Dependency Resolver with Topological Sort

Dependency management is the backbone of build tools like Maven or Gradle and a high-signal problem in senior-level machine coding interviews. If you cannot correctly order task execution or detect circular dependencies, your system will fail at scale.

If you're prepping for interviews, I've been building javalld.com — real machine coding problems with full execution traces.

The Mistake Most Candidates Make

• Naive Recursion: Using simple DFS without state tracking, which leads to redundant computations or infinite loops in circular graphs.
• Ignoring In-Degrees: Attempting to "find" the next task by iterating over the entire list repeatedly ($O(N^2)$), rather than tracking which tasks are ready.
• Coupling Logic: Mixing the task execution logic directly into the graph traversal code, making the system hard to test and extend.

The Right Approach

• Core Mental Model: Represent the system as a Directed Acyclic Graph (DAG) and use Kahn’s Algorithm (BFS) to resolve nodes with zero incoming edges first.
• Key Entities: Task, DependencyGraph, DependencyResolver.
• Why it beats the naive approach: Kahn’s Algorithm provides $O(V + E)$ time complexity and offers a "free" way to detect cycles—if your output list is smaller than your input, you have a circular dependency.

The Key Insight (Code)

The heart of the resolver is maintaining the inDegree map. When a task's in-degree hits zero, it is ready for execution.

public List<String> resolve(Map<String, List<String>> adj, Map<String, Integer> inDegree) {
    Queue<String> queue = new LinkedList<>();
    inDegree.forEach((node, degree) -> { if (degree == 0) queue.add(node); });

    List<String> order = new ArrayList<>();
    while (!queue.isEmpty()) {
        String current = queue.poll();
        order.add(current);
        for (String neighbor : adj.getOrDefault(current, new ArrayList<>())) {
            inDegree.put(neighbor, inDegree.get(neighbor) - 1);
            if (inDegree.get(neighbor) == 0) queue.add(neighbor);
        }
    }
    if (order.size() != inDegree.size()) throw new CircularDependencyException();
    return order;
}

Key Takeaways

• In-degree Tracking: This is the most efficient way to identify "ready-to-run" tasks without re-scanning the graph.
• Cycle Detection: Always validate that the final sorted list size equals the total number of nodes to catch hidden circularities.
• Separation of Concerns: Keep your graph representation (nodes/edges) distinct from the execution engine to allow for future features like parallel execution.

Full working implementation with execution trace available at https://javalld.com/problems/dependency-builder