Microservice Deployment Order
Gupshup's platform relies on a complex ecosystem of microservices. Ensuring these services are deployed in the correct sequence, respecting their inter-dependencies, is critical for system stability and preventing operational issues. A misordered deployment can lead to service failures or unexpected behavior.
This problem challenges you to determine a valid deployment order for a set of microservices given their direct dependencies. If a circular dependency exists, it signifies an impossible deployment scenario, and your system should gracefully report this.
Implement a function getDeploymentOrder that takes the total number of microservices and a list of their direct dependencies. Your function should return a valid deployment sequence for these services. If a valid order cannot be determined due to circular dependencies, an empty array should be returned.
numServices: A number representing the total count of microservices. These services are labeled numerically from 0 to numServices - 1.
dependencies: A number[][] (array of number arrays) where each inner array [u, v] signifies a direct dependency: service u must be deployed before service v.
Return: A number[] representing any valid deployment order of the services. If no valid deployment order exists due to circular dependencies, return an empty array [].
dependencies is empty, any order of services (e.g., [0, 1, ..., numServices-1]) is valid.numServices = 0: If there are no services, an empty array [] should be returned.Examples
Example 1
Input:
numServices = 3, dependencies = [[0, 1], [0, 2]]
Output:
[0, 1, 2]
Note:
Service 0 must be deployed first. Services 1 and 2 can follow in any order after 0. [0, 2, 1] would also be valid.
Example 2
Input:
numServices = 4, dependencies = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output:
[3, 1, 2, 0]
Note:
Service 3 must be deployed before 1 and 2. Services 1 and 2 must be deployed before 0. A valid order is [3, 1, 2, 0]. [3, 2, 1, 0] is also valid.
Example 3
Input:
numServices = 2, dependencies = [[0, 1], [1, 0]]
Output:
[]
Note:
Service 0 depends on 1, and service 1 depends on 0, forming a circular dependency. No valid deployment order exists.
Example 4
Input:
numServices = 1, dependencies = []
Output:
[0]
Note:
There is one service and no dependencies. It can be deployed.
Constraints
1 <= numServices <= 10^40 <= dependencies.length <= 5 * 10^4dependency pair [u, v] will satisfy 0 <= u, v < numServices and u != v.[u, v] are unique.Loading editor...