Package Install Order
Updated
Problem statement
You are given a dependency map as two arrays: packages[i] is a package name and dependencies[i] lists the packages that must be installed before packages[i]. A name that appears only inside dependencies has no dependencies of its own.
Install everything with the following procedure and return the names in the order they are installed. Each package is installed exactly once, so the answer has no repeated names.
- Go through
packagesfrom index0to the end and install each one. - To install a package that is already installed, do nothing.
- Otherwise, first install each of its dependencies, one by one in the order they are listed, and then install the package itself.
The dependencies contain no cycle: no package needs itself, directly or through other packages.
Function
installOrder(packages: String[], dependencies: String[][]) → String[]Examples
Example 1
packages = ["app","web","db"]dependencies = [["web","db"],["http","db"],["disk"]]return = ["http","disk","db","web","app"]- Start with
app. Its first dependencywebneedshttp(installed first, it has no entry) and thendb. dbneedsdisk, sodiskand thendbare installed, followed byweb.app's second dependencydbis already installed, soappis installed next.webanddbcome later inpackagesbut are already installed. The order ishttp, disk, db, web, app.
Example 2
packages = ["a"]dependencies = [[]]return = ["a"]ahas no dependencies, so it is installed right away.
Example 3
packages = ["d","b","c","a"]dependencies = [["b","c"],["a"],["a"],[]]return = ["a","b","c","d"]dneedsb, which needsa: installa, thenb.d's next dependencycneedsa, which is already installed: installc, thend.ais installed only once, even though bothbandcneed it.
Constraints
1 <= packages.length <= 1000dependencies.length == packages.length0 <= dependencies[i].length <= 50- The input has at most 1000 different names and at most 5000 dependencies in total.
- Every name has 1 to 10 characters, each a lowercase letter, a digit or
'-'. - The names in
packagesare distinct, and nodependencies[i]repeats a name or containspackages[i].
More Verily Onsite Interview questions
Similar questions at other companies
- Task Build Order and File-Change RerunsVanta · PHONE SCREEN
- Course ScheduleAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Course SchedulePlaud · ONSITE INTERVIEW
- Course Schedule Cycle DetectionGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Validate and Resolve Evaluation ChainsPlaid · PHONE SCREEN · ONSITE INTERVIEWPlaid interview questions
- Topological Sort with Secondary OrderingRoblox · PHONE SCREEN · ONSITE INTERVIEWRoblox interview questions
- Evaluate Formulas with Cycle DetectionInstacart · PHONE SCREEN · ONSITE INTERVIEWInstacart interview questions
- Audit Discounted Category AncestorsFaire · ONSITE INTERVIEW
- Root of the Largest TreeGoldman Sachs · PHONE SCREEN · ONSITE INTERVIEWGoldman Sachs interview questions
- Detect a Cycle in a Directed GraphMakeMyTrip.com · ONSITE INTERVIEWMakeMyTrip.com interview questions