Package Installer with Dependency Resolution

0) Problem Restatement

Amazon asked: design a package installer (like apt, pip or npm). When the user runs install A:

1. Find A's dependencies, and their dependencies (transitively).
2. Respect version constraints (e.g., A needs B >= 2.0, < 3.0).
3. Detect missing packages and conflicts (two packages need incompatible versions of C).
4. Install in the right order (dependencies before dependents), and roll back if something fails.

1) Step 1: Build the Dependency Graph

• Each package version has metadata: name, version, dependencies: [(name, constraint)], fetched from the registry (the repository index).
• Start from the requested package, and repeatedly fetch the metadata of dependencies → a directed graph (edge A → B means "A depends on B").
• Missing package or no version satisfying a constraint → a clear error ("A 1.2 needs B>=2 but only B 1.x exists").

2) Step 2: Choose Versions (resolution)

• Simple approach (backtracking): for each package, try the newest version that satisfies all constraints seen so far. When a later dependency adds a conflicting constraint, backtrack and try an older version.
• Real tools use smarter solvers: pip's resolver (backtracking with heuristics), and apt, conda and Cargo's PubGrub (SAT-like with good error messages).
• If no combination works, report the conflict chain clearly: "A needs C<2, B needs C>=2".
• Write a lock file with the exact chosen versions and checksums, so the next install is reproducible.

3) Step 3: Install Order (topological sort)

from collections import defaultdict, deque

def install_order(deps):                 # deps: {pkg: [dep, ...]} for the chosen versions
    indeg = defaultdict(int)
    users = defaultdict(list)            # dep -> packages that need it
    nodes = set(deps) | {d for ds in deps.values() for d in ds}
    for p, ds in deps.items():
        for d in ds:
            indeg[p] += 1
            users[d].append(p)
    ready = deque(sorted(n for n in nodes if indeg[n] == 0))   # packages with no deps first
    order = []
    while ready:
        n = ready.popleft(); order.append(n)
        for u in users[n]:
            indeg[u] -= 1
            if indeg[u] == 0: ready.append(u)
    if len(order) != len(nodes):
        raise ValueError("dependency cycle among: " + ", ".join(sorted(nodes - set(order))))
    return order

print(install_order({"app": ["web", "db"], "web": ["http"], "db": ["http"], "http": []}))
# ['http', 'web', 'db', 'app']  (http first, app last)

Kahn's algorithm installs a package only after all its dependencies, and detects cycles when some packages can never become ready.

flowchart LR
    REQ["install app"] --> META["Fetch metadata from registry"]
    META --> RES["Resolve versions - backtracking / solver"]
    RES --> LOCK[("Lock file")]
    RES --> TOPO["Topological order"]
    TOPO --> DL["Parallel download + verify checksums"]
    DL --> INST["Install in order - staged"]
    INST -->|"failure"| RB["Rollback to previous state"]

4) Downloading and Installing Safely

• Parallel downloads (packages at the same "level" have no dependency on each other), with a local cache of downloaded archives.
• Integrity: verify checksums (and signatures) against the registry and lock file, never installing tampered files.
• Atomic install: install into a staging area, then switch over. On failure, remove the staged files or restore the previous versions (rollback), and never leave a half-installed environment.
• Record installed packages and versions in a local database, for uninstall and upgrade.

5) Wrap-Up

Fetch package metadata from the registry to build a dependency graph, choose versions that satisfy all constraints with a backtracking resolver (or a SAT-style solver) that reports conflicts clearly, and record the result in a lock file. Install in topological order (Kahn's algorithm, detecting cycles), downloading in parallel from a cache with checksum and signature verification, and stage the install so any failure rolls back cleanly.