Automate a Common Deployment Task | Dataford Interview Questions

Your question is Automate a Common Deployment Task. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

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):