FastPrep
Problem · Graph

Microservice Deployment Order

Learn this problem
● MediumGoldman Sachs logoGoldman SachsFULLTIMEONSITE INTERVIEW

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

drafts saved locally
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