Automate a Common Deployment Task

MediumPython

Problem

Nielsen ONE deployments may contain services that depend on other services being deployed first. Given a set of services and prerequisite relationships, generate the deployment waves that respect every dependency while allowing independent services to deploy together.

A dependency [service, prerequisite] means the prerequisite must appear in an earlier wave than the service. Within each wave, return service names in lexicographic order. Return an empty list if the dependencies contain a cycle, because no valid deployment plan exists.

Formal Specification

Implement deploy_waves(services, dependencies).

services is a list of unique strings.
dependencies is a list of two-element lists, each containing a service and one of its prerequisites.
Return a list of lists of strings. Each inner list is one deployment wave.
Every service must appear exactly once in the result when the dependency graph is acyclic.
Services with no unmet prerequisites may be placed in the same wave.

Constraints

1 <= len(services) <= 10^5
0 <= len(dependencies) <= 2 * 10^5
Service names are unique, non-empty strings
Every dependency references a service in services
Duplicate dependency pairs do not appear

Function Signature

def deploy_waves(services, dependencies):

Formal Specification

Implement deploy_waves(services, dependencies).

services is a list of unique strings.
dependencies is a list of two-element lists, each containing a service and one of its prerequisites.
Return a list of lists of strings. Each inner list is one deployment wave.
Every service must appear exactly once in the result when the dependency graph is acyclic.
Services with no unmet prerequisites may be placed in the same wave.