FastPrepMicroservice Deployment Order

Microservice Deployment Order

Goldman Sachs logoGoldman Sachs● MediumFULLTIMEONSITE INTERVIEW
Learn

Problem statement

A platform must deploy n services labeled from 0 to n - 1.

Each pair [service, prerequisite] in dependencies means that service cannot start until prerequisite is running.

Return the lexicographically smallest valid deployment order. At each step, deploy the smallest labeled service whose prerequisites are all running. If the dependencies contain a cycle, return an empty array.

Function

deploymentOrder(n: int, dependencies: int[][]) → int[]

Examples

Example 1

n = 4dependencies = [[1,0],[2,0],[3,1],[3,2]]return = [0,1,2,3]

Service 0 is ready first; services 1 and 2 then become ready, so label 1 is selected before label 2.

Example 2

n = 3dependencies = [[0,1],[1,2],[2,0]]return = []

The three services form a cycle, so no valid deployment order exists.

Constraints

  • 1 <= n <= 10^5
  • 0 <= dependencies.length <= 2 * 10^5
  • Every dependency contains two different labels in [0, n - 1].
  • Dependency pairs are unique.

More Goldman Sachs problems

See Goldman Sachs hiring insights
public int[] deploymentOrder(int n, int[][] dependencies) {
    // Write your code here.
}
n4
dependencies[[1,0],[2,0],[3,1],[3,2]]
expected[0,1,2,3]
Checking account…