Collaborative Coding With Tests

MediumPython

Problem

During a collaborative coding session for VMware Tanzu, the interviewer may add deployment scenarios as test cases while you implement the scheduling logic. Given a set of services and dependency relationships, return the order in which the services can be deployed.

Each dependency is represented as [service, prerequisite], meaning prerequisite must be deployed before service. If multiple services are currently available, choose the lexicographically smallest service name. If the dependencies contain a cycle, return an empty list because no valid deployment order exists.

Formal Specification

Implement deployment_order(services, dependencies).

services is a list of unique strings.
dependencies is a list of two-element lists of strings.
Return a list containing every service exactly once in a valid deployment order, or [] if no such order exists.
The returned order must be lexicographically smallest among all valid orders.

Constraints

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

Function Signature

def deployment_order(services, dependencies):

Formal Specification

Implement deployment_order(services, dependencies).

services is a list of unique strings.
dependencies is a list of two-element lists of strings.
Return a list containing every service exactly once in a valid deployment order, or [] if no such order exists.
The returned order must be lexicographically smallest among all valid orders.