Amazon Package Dependencies Interview Question | DFS | Same as Course Schedule II

Amazon Package Dependencies | DFS | Same as Course Schedule II

This question has appeared in slightly different Amazon interview forms.

Refer:
https://leetcode.com/discuss/post/1453430/amazon-phone-interview-by-anonymous_user-eq6m/
https://leetcode.com/discuss/post/1031933/amazon-onsite-sde2-package-dependencies-tuw9e/

Question Asked

Version 1: Install Package With Dependencies

You are given a map of software packages and dependencies.

Example:

A depends on B, C
B depends on D, E, F
C depends on F
F depends on G
H depends on I, J
J depends on G

Write a class/method that installs an individual package along with all of its dependencies.

Assume every package has an install() method that installs only that package, not its dependencies.

For example, to install package A, a valid install order could be:

G, F, C, E, D, B, A

Version 2: Build Package With Dependencies

You are given package dependencies and a package name x.

Return the build order for package x.

Example:

A -> {B, C}
B -> {E}
C -> {D, E, F}
D -> {}
F -> {}
G -> {C}

For package A, one valid build order is:

E, B, F, D, C, A

The interviewer may also ask how to handle cyclic dependencies.

Pattern

This is basically the same as:

Course Schedule I
Course Schedule II
Topological Sort
Dependency resolution

The mental model is:

Before installing/building a package,
install/build all of its dependencies first.

So DFS fits naturally.

Similarity to Course Schedule

In Course Schedule:

course -> prerequisites

Here:

package -> dependencies

Same idea.

For example:

A -> [B, C]
B -> [D, E, F]
C -> [F]
F -> [G]

means:

Before A, install B and C.
Before B, install D, E, F.
Before C, install F.
Before F, install G.

So the valid order should put dependencies before the package:

G, F, C, E, D, B, A

or another valid topological order.

The exact order may not be unique.

Why DFS?

DFS works well because it follows the dependency chain first.

For package A:

dfs(A)
    dfs(B)
        dfs(D) -> install/append D
        dfs(E) -> install/append E
        dfs(F)
            dfs(G) -> install/append G
            install/append F
        install/append B
    dfs(C)
        dfs(F) already processed
        install/append C
    install/append A

So the action happens after dependencies are done:

DFS dependency first
        ↓
Append current package OR call package.install()

If the interviewer asks to return build/install order, use:

self.order.append(package)

If the interviewer asks to actually install, use:

package.install()

Same DFS. Only the final action changes.

Cycle Detection

Use two sets:

visiting

Packages currently in the DFS path.

If we reach a package already in visiting, there is a cycle.

visited

Packages already fully processed/installed.

If a package is in visited, we do not process it again.

Code: Return Install/Build Order

Here the input is already an adjacency list:

package -> [dependencies]

So we can use it directly.

class PackageInstaller:
    def __init__(self, dependencies):
        self.dependencies = dependencies   # already adjacency list: package -> [dependencies]
        self.visiting = set()              # current DFS path, used for cycle detection
        self.visited = set()               # packages already fully processed
        self.order = []                    # final install/build order

    def installWithDependencies(self, package):
        if not self.dfs(package):
            return []                      # cycle found, cannot install/build safely
        return self.order

    def dfs(self, package):
        if package in self.visiting:       # cycle: package already in current DFS path
            return False

        if package in self.visited:        # already installed / processed once
            return True

        self.visiting.add(package)         # start checking this package

        for dep in self.dependencies.get(package, []):  # first install/build all dependencies
            if not self.dfs(dep):
                return False

        self.visiting.remove(package)      # done checking this package
        self.visited.add(package)          # mark package as fully processed
        self.order.append(package)         # add only after all dependencies are done

        return True

Example

dependencies = {
    "A": ["B", "C"],
    "B": ["D", "E", "F"],
    "C": ["F"],
    "F": ["G"],
    "H": ["I", "J"],
    "J": ["G"]
}

installer = PackageInstaller(dependencies)
print(installer.installWithDependencies("A"))

One possible output:

["D", "E", "G", "F", "B", "C", "A"]

This is valid because:

D, E, F come before B
G comes before F
F comes before C
B and C come before A

The output does not have to exactly match the sample as long as every dependency appears before the package that depends on it.

If Interviewer Asks About Actual `install()`

Sometimes the interviewer may say:

Each package already has an install() method. Install package A and all of its dependencies.

That means instead of returning a list, we actually call install() on every package in the right order.

The DFS logic is the same:

process all dependencies first
        ↓
then install current package

So in the previous code, this line:

self.order.append(package)

was used to store the package in the final answer.

For actual installation, replace it with:

package.install()

Code: Actually Install Packages

class PackageInstaller:
    def __init__(self, dependencies):
        self.dependencies = dependencies   # package -> [dependencies]
        self.visiting = set()              # current DFS path, used for cycle detection
        self.visited = set()               # packages already installed / processed

    def installWithDependencies(self, package):
        return self.dfs(package)           # True if installed safely, False if cycle found

    def dfs(self, package):
        if package in self.visiting:       # cycle: package already in current DFS path
            return False

        if package in self.visited:        # already installed once
            return True

        self.visiting.add(package)

        for dep in self.dependencies.get(package, []):  # install dependencies first
            if not self.dfs(dep):
                return False

        self.visiting.remove(package)
        self.visited.add(package)

        package.install()                  # actual install happens here, after dependencies

        return True

Tiny Example

class Package:
    def __init__(self, name):
        self.name = name

    def install(self):
        print(f"Installing {self.name}")

If dependencies are:

A -> [B, C]
B -> [D]
C -> []
D -> []

Calling:

installer.installWithDependencies(A)

would install in this order:

Installing D
Installing B
Installing C
Installing A

So the only real difference is:

# return-order version
self.order.append(package)

# actual-install version
package.install()

Same DFS. Different final action.


One caveat: in the actual `install()` version, `package` needs to be a package object, not just a string, because strings don’t have `.install()`.

Complexity

Let:

V = number of packages
E = number of dependency relationships

Time Complexity:

O(V + E)

Each package and dependency edge is processed once.

Space Complexity:

O(V + E)

For the dependency map, visited sets, result list, and recursion stack.

Main Takeaway

This is not really a new problem.

It is Course Schedule II with different names:

course  -> package
prereq  -> dependency
result  -> install/build order
cycle   -> invalid dependency chain

The key line is:

self.order.append(package)

after processing all dependencies.

If the interviewer wants actual installation, replace that line with:

package.install()

Comments (2)