FastPrepPackage Install Order

Package Install Order

Verily logoVerily● MediumFULLTIMEONSITE INTERVIEW

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 packages from index 0 to 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 dependency web needs http (installed first, it has no entry) and then db.
  • db needs disk, so disk and then db are installed, followed by web.
  • app's second dependency db is already installed, so app is installed next.
  • web and db come later in packages but are already installed. The order is http, disk, db, web, app.

Example 2

packages = ["a"]dependencies = [[]]return = ["a"]
  • a has 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"]
  • d needs b, which needs a: install a, then b.
  • d's next dependency c needs a, which is already installed: install c, then d.
  • a is installed only once, even though both b and c need it.

Constraints

  • 1 <= packages.length <= 1000
  • dependencies.length == packages.length
  • 0 <= 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 packages are distinct, and no dependencies[i] repeats a name or contains packages[i].

More Verily Onsite Interview questions

Similar questions at other companies

Interview reports that mention this question

See Verily hiring insights
Saved
class Solution {
    public String[] installOrder(String[] packages, String[][] dependencies) {
        // Write your code here.
    }
}
Checking account…