Design a Package Manager/Installer with Dependency Resolution

Problem Statement

Design a Package Manager and Installer engine (similar to npm, apt-get, or Maven dependency managers). The engine must allow registering packages along with their corresponding lists of dependencies, resolve the correct order of installation dynamically using topological sorting so that all dependencies are installed before their parent packages, and detect circular dependencies (e.g., Package X depends on Package Y, and Y depends on X), throwing an exception to abort execution.

Asked In Companies

Amazon Salesforce RedHat

---

Design Decisions & Patterns Used

In modern software development, applications depend on reusable library packages. These libraries in turn depend on other libraries, forming a complex dependency graph. When a user requests to install a package, the system must traverse this graph, identify all nested dependencies, and order them so that libraries are installed in a bottom-up sequence.

To accomplish this, we model the package relationships as a **Directed Graph** where packages are nodes and dependencies are directed edges. Resolving the installation order is equivalent to executing a **Topological Sort** on this graph. If there are circular references in the graph (cycles), the topological sort is impossible, and the program must fail fast to prevent deadlocks or infinite download loops.

We will utilize the following Design Patterns:

• Strategy Pattern: We define a generic interface for dependency resolution. This allows us to swap the resolution algorithm at runtime (e.g., swapping a standard DFS-based topological sort with Kahn's BFS-based algorithm) depending on performance constraints.
• Builder Pattern: Providing a fluent API to define packages and wire their dependencies programmatically, improving the readability of client code.

---

Functional Requirements

• Maintain a global registry repository where packages can be registered with their name, version, and dependencies.
• Resolve the transient dependency graph of any target package to build the correct order of installation.
• Detect and reject circular dependency loops (e.g., Package A depends on B, B depends on C, and C depends on A).
• Simulate downloading and installing the packages in the resolved order.

---

Objects Required

• Package (The domain entity storing the package metadata, version, and a list of dependency names)
• DependencyResolver (The strategy interface defining the contract for topological sorting algorithms)
• DfsResolver (Concrete strategy implementation resolving packages using Depth-First Search)
• PackageManager (The main coordinator class managing the package registry and executing installations)

---

Package Class

The Package class encapsulates the metadata of a single software library, including its name, version, and a list of dependency names.

import java.util.ArrayList;
import java.util.List;

public class Package {
    private final String name;
    private final String version;
    private final List<String> dependencies;

    public Package(String name, String version) {
        this.name = name;
        this.version = version;
        this.dependencies = new ArrayList<>();
    }

    public void addDependency(String packageName) {
        dependencies.add(packageName);
    }

    public String getName() { return name; }
    public String getVersion() { return version; }
    public List<String> getDependencies() { return dependencies; }
}

Let's break down the logic of this class:

• Package(name, version): The constructor initializes the package with its name and version, and instantiates an empty list to store dependencies.
• addDependency(packageName): Adds a required dependency package name to our list of dependencies. This is used by the package registry to build the edges of the dependency graph.

---

DependencyResolver Interface & DfsResolver Class

The DependencyResolver interface defines the contract for resolving dependencies. We apply the **Strategy Pattern** to keep the topological sorting algorithm pluggable, allowing us to implement different sorting strategies (like DFS or BFS).

import java.util.List;
import java.util.Map;

public interface DependencyResolver {
    List<Package> resolve(String targetPackage, Map<String, Package> registry);
}

Let's implement the concrete DFS-based topological sort strategy:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class DfsResolver implements DependencyResolver {
    @Override
    public List<Package> resolve(String targetPackage, Map<String, Package> registry) {
        List<Package> resolvedOrder = new ArrayList<>();
        Set<String> visiting = new HashSet<>();
        Set<String> visited = new HashSet<>();

        resolveDfs(targetPackage, registry, resolvedOrder, visiting, visited);
        return resolvedOrder;
    }

    private void resolveDfs(String pkgName, Map<String, Package> registry, 
                            List<Package> resolvedOrder, Set<String> visiting, Set<String> visited) {
        
        // Circular dependency detection
        if (visiting.contains(pkgName)) {
            throw new IllegalStateException("Circular Dependency Error: Loop detected involving package '" + pkgName + "'");
        }

        if (!visited.contains(pkgName)) {
            Package pkg = registry.get(pkgName);
            if (pkg == null) {
                throw new IllegalArgumentException("Dependency Resolution Error: Missing package '" + pkgName + "' in registry.");
            }

            visiting.add(pkgName);

            // Recursively resolve all dependencies first
            for (String depName : pkg.getDependencies()) {
                resolveDfs(depName, registry, resolvedOrder, visiting, visited);
            }

            visiting.remove(pkgName);
            visited.add(pkgName);
            resolvedOrder.add(pkg); // Add parent package once all dependencies are resolved
        }
    }
}

Let's break down the logic of every method in the DfsResolver class:

• resolve(targetPackage, registry): This method initializes the helper collections. The visiting set tracks nodes currently in the active recursion path (to detect cycles), while the visited set tracks nodes that have been fully resolved (to prevent duplicate processing). It then calls the recursive helper method to compile the installation order.
• resolveDfs(pkgName, registry, ...): This recursive helper implements our depth-first search. First, it checks if the package is in the visiting set. If it is, a circular dependency has been detected (the graph contains a cycle), so it throws an IllegalStateException. If the node has not yet been fully processed, it checks if it exists in the registry, adds it to the visiting set, recursively resolves all its dependencies, removes it from the visiting set, adds it to the visited set, and appends the package to the installation list.

---

PackageManager Class

The PackageManager class coordinates the overall workflow. It registers packages, initiates the dependency resolver strategy, and prints the simulated installation steps.

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class PackageManager {
    private final Map<String, Package> registry;
    private final DependencyResolver resolver;

    public PackageManager(DependencyResolver resolver) {
        this.registry = new HashMap<>();
        this.resolver = resolver;
    }

    public void registerPackage(Package pkg) {
        registry.put(pkg.getName(), pkg);
        System.out.println("Registered Package: " + pkg.getName() + " (v" + pkg.getVersion() + ")");
    }

    public void install(String packageName) {
        System.out.println("Initiating installation for package: " + packageName);
        
        try {
            List<Package> installOrder = resolver.resolve(packageName, registry);
            System.out.println("\n--- Resolved Installation Order ---");
            
            for (int i = 0; i < installOrder.size(); i++) {
                Package pkg = installOrder.get(i);
                System.out.println((i + 1) + ". Installing " + pkg.getName() + " (v" + pkg.getVersion() + ")... DONE");
            }
            System.out.println("\nSuccess: Package '" + packageName + "' and all dependencies installed successfully.");
        } catch (Exception e) {
            System.err.println("\nInstallation Failed: " + e.getMessage());
            throw e;
        }
    }
}

Let's break down the logic of every method in the PackageManager class:

• PackageManager(resolver): The constructor registers the chosen dependency resolution strategy and initializes the package registry map using a standard HashMap.
• registerPackage(pkg): Registers a package in the manager's memory registry, mapping the package name to its configuration object.
• install(packageName): Initiates the installation process. It calls the resolver strategy to calculate the installation sequence, logs the resolved order, and prints simulated download progress. If any error occurs, it catches the exception and logs the failure trace.

---

Main Driver Class

This class tests our package manager, verifying dependency resolution, installation ordering, and circular dependency checks.

public class Main {
    public static void main(String[] args) {
        // Instantiate package manager with a DFS dependency resolver
        PackageManager pm = new PackageManager(new DfsResolver());

        System.out.println("==========================================");
        System.out.println("Scenario 1: Testing Successful Installation");
        System.out.println("==========================================");

        // Define packages:
        // PackageA depends on PackageB and PackageC
        // PackageB depends on PackageD
        // PackageC has no dependencies
        // PackageD has no dependencies
        
        Package pkgA = new Package("PackageA", "1.0.0");
        pkgA.addDependency("PackageB");
        pkgA.addDependency("PackageC");

        Package pkgB = new Package("PackageB", "2.1.0");
        pkgB.addDependency("PackageD");

        Package pkgC = new Package("PackageC", "1.2.0");
        Package pkgD = new Package("PackageD", "0.9.0");

        pm.registerPackage(pkgA);
        pm.registerPackage(pkgB);
        pm.registerPackage(pkgC);
        pm.registerPackage(pkgD);

        // Install PackageA (Expected order: D, B, C, A)
        pm.install("PackageA");

        System.out.println("\n==========================================");
        System.out.println("Scenario 2: Testing Circular Dependency Loop");
        System.out.println("==========================================");

        PackageManager pmInvalid = new PackageManager(new DfsResolver());

        // Cyclic Loop: X depends on Y, Y depends on Z, Z depends on X
        Package pkgX = new Package("PackageX", "1.0.0");
        pkgX.addDependency("PackageY");

        Package pkgY = new Package("PackageY", "1.0.0");
        pkgY.addDependency("PackageZ");

        Package pkgZ = new Package("PackageZ", "1.0.0");
        pkgZ.addDependency("PackageX");

        pmInvalid.registerPackage(pkgX);
        pmInvalid.registerPackage(pkgY);
        pmInvalid.registerPackage(pkgZ);

        try {
            pmInvalid.install("PackageX");
        } catch (Exception e) {
            System.out.println("Caught Expected Exception: " + e.getMessage());
        }
    }
}

The main() driver configures packages and dependencies, verifies that the manager resolves the installation order (installing dependencies first), and asserts that cyclic dependencies are detected and rejected.

---

Also See

• Most Commonly Asked Low Level Design Interview Questions
• Top 10 Low Level Design Interview Questions