Design a Package Registry

Adapted from a real 60-minute technical screen. The company name doesn't matter; the shape does — this exact question family shows up constantly for product and platform teams.

The prompt, as given

Make a build system or package manager. Think something along the lines of npm or pip but not nearly as good. The system needs to let a user (human or system) add packages to the system.

Initial requirements:

1. A user or automated process should be able to add a single package and its immediate dependencies into the system to be tracked.
2. A user or automated process can add dependencies to a package that already exists in the system. In this case, the new dependencies and the existing dependencies should be merged such that there are no duplicates in any package's immediate list of dependencies.

First task: define and implement an API to add packages and list dependencies.

Constraints: add package can be called multiple times for the same package. Subsequent calls should merge dependencies. The same dependency should not appear in the package's dependency list more than once.

Stop here and build it before reading on. Fifteen to thirty minutes, tests included. The rest of this page is the debrief.

Reading the prompt like a spec

Every phrase in that prompt is deliberate, and the ambiguity is the graded material:

Phrase	What it's actually signalling
"define and implement an API"	You choose the interface. Naming, method set, and return types are being scored.
"First task"	There are more tasks. Task 1 is a data-model audition for tasks 2 and 3.
"think npm or pip"	Real package managers do transitive resolution, cycle detection, and install ordering. That's the roadmap.
"immediate dependencies"	Nobody qualifies a dependency list as immediate unless transitive is coming. The loudest tell in the prompt.
"no duplicates"	A hint to pick a set-shaped container instead of writing dedup code.
"human or system"	Input may be dirty and automated — validate, and make operations idempotent.

The two decisions that carry the whole problem

1. Key dependencies by name. Map<string, Package> rather than Package[]. The headline constraint — no duplicate dependencies — becomes free: it's a property of the container, not code you write. It also makes "does A depend on B?" O(1) instead of an array scan.

2. Store only canonical objects. Every dependency you store is the registry's Package for that name — never the caller's copy. One source of truth: when someone later adds a dependency to react, every package depending on react sees it, because they all hold the same object.

Both come out of one private helper, and this helper is the whole trick:

private ensure(name: string): Package {
  let pkg = this.packages.get(name);
  if (!pkg) { pkg = { name, dependencies: new Map() }; this.packages.set(name, pkg); }
  return pkg;
}

Get-or-create. It registers unknown packages, guarantees you're holding the canonical object, and deletes every if (exists) { merge } else { insert } branch from the rest of the class. If you find yourself writing that branch, back up and write ensure instead.

Phase 1 — add packages, list dependencies

interface Package {
  name: string;
  dependencies: Map<string, Package>;      // keyed by name ⇒ dedup is free
}

class Registry {
  private packages = new Map<string, Package>();

  /** get-or-create — returns THE canonical Package object for this name */
  private ensure(name: string): Package {
    let pkg = this.packages.get(name);
    if (!pkg) { pkg = { name, dependencies: new Map() }; this.packages.set(name, pkg); }
    return pkg;
  }

  addPackage(pkg: Package): void {
    const entry = this.ensure(pkg.name);              // MERGE into it — never .set() over it
    for (const depName of pkg.dependencies.keys()) {
      if (depName === pkg.name) continue;             // ignore self-dependency
      entry.dependencies.set(depName, this.ensure(depName)); // canonical, not the caller's
    }
  }

  addDependency(pkg: Package, dependency: Package): void {
    if (pkg.name === dependency.name) { this.ensure(pkg.name); return; }
    this.ensure(pkg.name).dependencies.set(dependency.name, this.ensure(dependency.name));
  }

  get(): Package[] { return [...this.packages.values()]; }

  getDependencies(name: string): Package[] {
    return [...(this.packages.get(name)?.dependencies.values() ?? [])];
  }

  size(): number { return this.packages.size; }       // .size — property, no parens
}

addPackage is O(d) in the dependencies passed; lookups are O(1); space is O(V + E).

Two lines deserve special attention, because they're where real attempts fail:

• const entry = this.ensure(pkg.name) — the single most common live bug on this question is this.packages.set(pkg.name, pkg), which replaces the entry and throws away everything a previous call registered. The prompt demands merging twice — in the requirements and again in the constraints. ensure + loop is the merge.
• addDependency is one line — it's addPackage with a single dependency. When your second method collapses into your first, the abstraction was right.

And test through the API. The other classic failure: main() mutates pkg.dependencies directly, so the method under test never runs and only looks right because of reference aliasing. Write a three-line assert helper before any design:

function assert(label: string, got: unknown, want: unknown): void {
  const ok = JSON.stringify(got) === JSON.stringify(want);
  console.log(`${ok ? "PASS" : "FAIL"} ${label}${ok ? "" : ` — got ${JSON.stringify(got)}`}`);
}

Then one assertion per sentence of the requirements: dependencies recorded, re-add merges, duplicates collapse, addDependency is idempotent, unknown package returns empty.

Phase 2 — transitive dependencies

"Now list everything package C needs, not just its immediate dependencies."

The word "immediate" promised this. It's DFS over the registry with a visited set — and the visited set is not an optimization: it's what stops an infinite loop when the input contains a circular dependency. The prompt never promised a DAG.

  /** everything `name` needs, directly or indirectly */
  getAllDependencies(name: string): Package[] {
    const start = this.packages.get(name);
    if (!start) return [];
    const result = new Map<string, Package>();
    const stack = [...start.dependencies.values()];   // seed with immediate deps
    while (stack.length) {
      const current = stack.pop()!;
      if (result.has(current.name)) continue;         // resolved already — and cycle guard
      result.set(current.name, current);
      for (const next of current.dependencies.values()) stack.push(next);
    }
    return [...result.values()];
  }

O(V + E) time, O(V) space. Written iteratively on purpose — "what if the dependency chain is very deep?" is the standard follow-up, and an explicit stack means never rewriting under pressure. One edge worth stating rather than special-casing: on a cyclic graph, getAllDependencies("a") includes "a" itself — correctly, because a genuinely is reachable from a. Seeding the visited set with name instead, so the start node always comes back, is just as defensible; say which one you picked and why. (The bench ignores the start node either way.)

Phase 3 — cycles and install order

"What if A depends on B and B depends on A?" → "What order do I install these in?"

Both questions are one algorithm: Kahn's topological sort — this is Course Schedule wearing a costume. Indegree = "how many dependencies does this package still need"; edges run dependency → dependent; seed with packages that depend on nothing.

  /** install order: every package appears after all of its dependencies. null if cyclic. */
  buildOrder(): Package[] | null {
    const indegree = new Map<string, number>();
    const dependents = new Map<string, Package[]>();  // dependency -> things needing it

    for (const pkg of this.packages.values()) {
      indegree.set(pkg.name, pkg.dependencies.size);  // needs this many things first
      dependents.set(pkg.name, []);
    }
    for (const pkg of this.packages.values()) {
      for (const dep of pkg.dependencies.values()) dependents.get(dep.name)!.push(pkg);
    }

    const queue: Package[] = [];
    for (const pkg of this.packages.values()) {
      if (indegree.get(pkg.name) === 0) queue.push(pkg); // depends on nothing — install first
    }

    const order: Package[] = [];
    while (queue.length) {
      const pkg = queue.pop()!;
      order.push(pkg);
      for (const dependent of dependents.get(pkg.name)!) {
        const remaining = indegree.get(dependent.name)! - 1;
        indegree.set(dependent.name, remaining);
        if (remaining === 0) queue.push(dependent);
      }
    }

    return order.length === this.packages.size ? order : null; // short ⇒ cycle
  }

  hasCycle(): boolean { return this.buildOrder() === null; }

O(V + E) time and space. The line that is the whole answer: order.length === this.packages.size ? order : null. If the queue couldn't drain everything, whatever's left is each waiting on something inside a cycle — the same finished === n check as LC 207. Say that out loud: recognizing the shape scores better than rediscovering it.

Two details that bite: seed with zero-indegree packages (the leaf libraries), or you'll emit a perfectly valid reverse order and fail silently. And notice dependents needs no guards — because ensure guaranteed every dependency is itself registered. A phase-1 decision paying off in phase 3 is exactly what this problem tests.

The one step further — and the honest trade-off

Since every stored value is ensure(key), the value is derivable from the key. The fully-normalized design is:

private packages = new Map<string, Set<string>>();   // name -> dependency NAMES

Same dedup, same O(1) membership — and now it's structurally impossible to hold a stale copy, plus you're holding a textbook adjacency list. The cost: object references let you traverse by pointer; names force a registry lookup per hop. The lookup is O(1) and the registry is always in hand, so it's practically a wash — but it is a difference, and the sentence "I'd store names and resolve through the registry, accepting a lookup per hop for a single source of truth" is trade-off reasoning that separates a senior answer from a merely correct one.

Both designs are defensible. Have an opinion and say why — that's what's being scored.

The escalations past coding

If the conversation keeps going, it goes to infrastructure, and each has a real answer:

• "The graph doesn't fit in memory." Stream edges in chunks; keep only the frontier or union-find state resident.
• "Install packages in parallel." Process the topological order by level — every zero-indegree package in a level is independent. (That's multi-source BFS.)
• "A worker dies mid-install." Checkpoint completed nodes; make re-install idempotent — which is exactly why keying by name was right in phase one.