FastPrep
Problem · Graph

Package Dependency Order

Learn this problem
● MediumAmazonONSITE INTERVIEW
See Amazon hiring insights

Problem statement

You are given package dependency pairs and a target package. Each pair [package, dependency] means the package depends on that dependency.

Return an order in which to install the target package and all of its transitive dependencies so that every dependency appears before the package that needs it.

If there is a cyclic dependency among packages needed by the target package, return an empty array.

The source noted that multiple valid orders may exist. FastPrep uses this deterministic rule: process dependencies in the order they appear in the input pairs.

Function

packageInstallOrder(dependencies: String[][], target: String) → String[]

Examples

Example 1

dependencies = [["A","B"],["A","C"],["B","D"],["B","E"],["B","F"],["C","F"],["F","G"],["H","I"],["H","J"],["J","G"]]target = "A"return = ["D","E","G","F","B","C","A"]

The order installs D, E, and F before B; installs G before F; installs F before C; and installs both B and C before A.

More Amazon problems

drafts saved locally
public String[] packageInstallOrder(String[][] dependencies, String target) {
  // write your code here
}
dependencies[["A","B"],["A","C"],["B","D"],["B","E"],["B","F"],["C","F"],["F","G"],["H","I"],["H","J"],["J","G"]]
target"A"
expected["D", "E", "G", "F", "B", "C", "A"]
checking account