Frontend School

Microservice Deployment Order

DSA
medium

Microservice Deployment Order

Medium
Graph
Topological Sort

Overview

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.

What you need to do / Task

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.

Input & output

  • 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 [].

Clarifications

  • No dependencies: If 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.
  • Isolated services: Services that neither depend on others nor are prerequisites for others should still be included in the final deployment order.

Examples

1

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.

2

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.

3

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.

4

Example 4

Input:

numServices = 1, dependencies = []

Output:

[0]

Note:

There is one service and no dependencies. It can be deployed.

Constraints

Constraints & assumptions

  • 1 <= numServices <= 10^4
  • 0 <= dependencies.length <= 5 * 10^4
  • Each dependency pair [u, v] will satisfy 0 <= u, v < numServices and u != v.
  • All dependency pairs [u, v] are unique.

Out of scope

  • Optimizing for a specific topological sort order (e.g., lexicographically smallest). Any valid order is acceptable.
  • Handling invalid input types (e.g., non-numeric service IDs, malformed dependency pairs).

What interviewers evaluate

  • Correctness of the topological sort algorithm (e.g., using Kahn's algorithm or DFS-based approach).
  • Efficient graph representation and traversal for given constraints.
  • Accurate detection and handling of cyclic dependencies.
  • Robustness in handling edge cases such as no dependencies or single services.

Loading editor...