Katkat
Back

Design a package installer with dependencies

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSystem Design

Last updated

This question tests your ability to design a system that manages complex dependency graphs, ensuring package integrity, version compatibility, and atomic installation operations.

Scenario

Design a package installer (like apt, npm, or pip) that manages software packages and their dependencies. Your system must be able to install, upgrade, and remove packages while ensuring the environment remains in a stable, consistent state.

Requirements

Functional Requirements

  • Dependency Resolution: Given a package and its version, recursively resolve all dependencies and sub-dependencies.
  • Version Constraints: Handle versions (e.g., pkg A >= 1.2.0, pkg B < 2.0.0).
  • Conflict Detection: Prevent installation if two dependencies require incompatible versions of the same library.
  • Cycle Detection: Identify and reject circular dependencies (e.g., A depends on B, B depends on A).
  • Atomic Operations: If a package installation fails halfway, the system must provide a mechanism to roll back to the previous stable state.

Non-Functional Requirements

  • Scalability: Handle thousands of packages and complex deep dependency trees.
  • Performance: Minimize time spent resolving the graph before downloading begins.

Discussion Points

Your design should address:

  1. Data Model: How do you store package metadata and version information?
  2. Graph Representation: How do you model the dependency tree internally to detect cycles and conflicts?
  3. Resolution Algorithm: Describe the strategy to determine the valid installation set (e.g., backtracking, SAT solver).
  4. Failure Handling: How do you manage partially installed packages and ensure system integrity?

Hints

Hint 1

Represent the dependency tree as a Directed Acyclic Graph (DAG) and consider using a topological sort to determine the installation order.

Hint 2

Use a backtracking algorithm or a constraint satisfaction solver to navigate version requirements, treating each version conflict as a branch in the search space.

Hint 3

Implement a 'transaction log' or staging directory strategy to ensure that files are only moved to the final destination if the entire installation plan succeeds.

Follow-up questions

  • How would you modify your design to support concurrent installations of different applications that might share common dependencies?
  • If a central package registry goes down, how can we improve the availability of the installer using caching or distributed mirrors?
  • How do you handle security verification of packages (e.g., checksums or digital signatures) to prevent malicious code injection during the installation process?