Service Dependency Resolver (Rust)
Topics: graphs, topological sort, orchestration
Problem
A service mesh boots services in dependency order: a service may start only once everything it
depends on is running. Given the dependency graph, compute a valid startup order — or report a
dependency cycle if no order exists.
pub struct CycleError { pub nodes: Vec<String> }
pub fn resolve(deps: &BTreeMap<String, Vec<String>>) -> Result<Vec<String>, CycleError>;
deps maps each service to the services it depends on. A dependency that isn't itself a key is a
leaf and still appears in the output.- Every service must appear after all of its dependencies.
- The order is deterministic: when several services are ready (all their deps already emitted),
emit them in lexicographic order.
- On a cycle (including a self-dependency) return
Err(CycleError) whose nodes are the services
that couldn't be ordered, sorted.
{web:[api], api:[db], db:[]} → ["db","api","web"]
{app:[auth,cache], auth:[db], cache:[db]} → ["db","auth","cache","app"]
{a:[b], b:[a]} → Err(CycleError{nodes:["a","b"]})
This is a topological sort; Kahn's algorithm (a BTreeSet ready set + an in-degree map) makes
the deterministic-order and cycle-detection requirements natural.
Grading
Your solution.rs is compiled together with a trusted tests.rs (which include!s it) using
rustc --test. Only solution.rs is yours to edit.
Sign in to submit your solution.