Outage Blast Radius (Rust)
Topics: graphs, BFS, resilience
Problem
You have a service call graph — graph[svc] lists the services that svc calls (depends on). When
one service fails, every service that transitively depends on it is impacted. Compute the blast
radius: each impacted service and how many hops away it is.
pub fn blast_radius(graph: &BTreeMap<String, Vec<String>>, failed: &str) -> BTreeMap<String, u32>;
- Return every service transitively impacted when
failed goes down, mapped to its shortest hop
distance (1 = a direct caller of failed).
- Exclude
failed itself; omit services that aren't impacted.
- The graph may contain cycles — don't loop forever.
web→api, api→{db,cache}, worker→db
blast_radius(graph, "db") → {api:1, worker:1, web:2} // cache is unaffected
This is a breadth-first search over the reversed graph (callee → callers): build the reverse
adjacency, then BFS from failed so first-visit distances are the shortest.
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.