Outage Blast Radius (C)
Topics: graphs, BFS, reversed edges, shortest paths
Problem
A service calls other services. When one fails, which services are impacted, and
how many hops away are they? Compute the blast radius: a BFS over the
reversed call graph (callee → callers), so the first time you reach a service
is its shortest hop distance from the failure.
typedef struct { const char *name; const char *const *calls; int ncalls; } Service;
int blast_radius(const Service *g, int n, const char *failed,
const char **out_name, int *out_dist);
Write each impacted service and its shortest distance into out_name[]/out_dist[]
and return the count. The failed service itself is not included; an unknown
service impacts nothing.
Key concepts
- Reverse the edges: the input lists who each service calls, but failure
propagates to callers. The callers of
X are every service whose calls
contains X — find them by scanning (no need to build a reverse index).
- BFS gives shortest hops: process the queue level by level and mark each node
the first time it's seen; that first visit is its minimum distance. A
visited
set also makes cycles terminate.
- No allocation: a fixed-size
visited[] and a queue of (node, distance)
pairs suffice.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/blast && /tmp/blast
Sign in to submit your solution.