Build a Dependency ResolverStep 1 of 5

Model the dependency graph

12345

Step 1: Model the dependency graph

Every package manager starts with the same idea: a package can depend on other packages. We model that as a directed graph. Each node is a package, and an edge u -> v means "u depends on v" (v must be available for u).

We store the graph as an adjacency dict: keys are nodes, values are the list of their direct neighbors. Two rules make everything downstream testable:

  • A node is created the first time it is seen, and nodes keep insertion order.
  • Neighbors are appended in the exact order edges are added.

Because Python dicts and lists both preserve insertion order, this gives us well-defined, deterministic traversals later.

Implement add_edge(u, v) so that:

g = Graph()
g.add_edge("a", "b")
g.add_edge("a", "c")
g.nodes()        -> ["a", "b", "c"]
g.neighbors("a") -> ["b", "c"]
g.neighbors("b") -> []

nodes() and neighbors() are already written for you. They read from self.adj.

Hints
Starter code
from collections import deque


class Graph:
    def __init__(self):
        self.adj = {}

    def add_edge(self, u, v):
        """Add a directed edge u -> v, creating nodes as needed.

        Preserve insertion order: new nodes are appended the first time they
        are seen, and each neighbor is appended in the order edges are added.
        """
        # TODO: make sure both u and v exist as keys in self.adj (each mapped
        # to an empty list if new), then append v to self.adj[u].
        pass

    def nodes(self):
        return list(self.adj.keys())

    def neighbors(self, u):
        return self.adj.get(u, [])
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

OverviewNext step