Amazon Software Engineer Interview Experience — Phone Screen Package Installer, Onsite Topological Sort

Phone Interview

Given a mapping (Map / Adjacency List) of software packages and their dependencies, write a class or method to install a specified package along with all of its dependencies.

1. Assume each package object has an install() method that only installs that package itself and does not handle its dependencies.
2. Need to implement an installWithDependencies(package) method that makes sure all of a package's dependencies are installed in the correct order before the package itself is installed.
3. Need to handle cyclic dependencies — if a cycle is detected, the solution should be able to recognize it and take some action (e.g. throw an error or stop the installation).

Onsite

Given the package dependency data and a target package name x, return the full build order needed to build that package.

1. The logic of this problem is equivalent to LeetCode's Course Schedule II — it tests your grasp of Topological Sort.
2. Need to return an ordered List containing all the dependency packages plus the target package.
3. The interviewer usually follows up by asking how to handle cyclic dependencies.
4. Required to traverse with DFS, and explain how to use two sets — Visiting (current path) and Visited (fully processed) — to mark state and detect cycles.
5. Need to be able to analyze and state the algorithm's time complexity, O(V + E), and space complexity, O(V + E).