Practice/Amazon/Design a Package System with Dependencies

Design a Package System with Dependencies

Object Oriented DesignMust

Problem

You are building a software package manager similar to npm, pip, or apt. Each software package may depend on zero or more other packages that must be installed before it. Your task is to design a system that determines a valid installation order for a given set of packages and their dependencies.

Given a collection of packages where each package specifies its dependencies, compute a valid installation sequence. If the dependencies form a cycle (making installation impossible), detect this condition and return an appropriate indication.

Requirements

1. Implement a function that takes a dictionary/map of packages and their dependencies
2. Return a valid installation order as a list/array where dependencies appear before the packages that need them
3. Detect circular dependencies and return null (or None in Python) if they exist
4. Handle packages with no dependencies (they can be installed first)
5. Handle packages with multiple dependencies (all must be satisfied before installation)

Constraints

• 1 ≤ number of packages ≤ 1000
• 0 ≤ dependencies per package ≤ 100
• Package names are non-empty strings
• A package will not be listed as its own direct dependency (but indirect cycles are possible)
• Time complexity should be O(V + E) where V is packages and E is dependency relationships
• Space complexity should be O(V + E)

Examples

Example 1:

Input: \{"A": [], "B": ["A"], "C": ["B"]\} Output: ["A", "B", "C"] Explanation: Package A has no dependencies and can be installed first. Package B requires A, so it comes second. Package C requires B, so it comes last.

Example 2:

Input: \{"A": [], "B": ["A"], "C": ["A"], "D": ["B", "C"]\} Output: ["A", "B", "C", "D"] or ["A", "C", "B", "D"] Explanation: A must come first. B and C both depend only on A, so they can be in any order relative to each other. D depends on both B and C, so it must come after both.

Example 3:

Input: \{"A": ["B"], "B": ["A"]\} Output: null Explanation: Circular dependency detected. A needs B and B needs A, making installation impossible.