Fallback Chain Selector (C)
Topics: backtracking, subset selection, pruning
Problem
Select a primary-plus-fallback chain of backend services: a fixed-size subset
where no two services share a failure domain and their total latency stays
within a budget.
typedef struct { const char *name; const char *domain; int latency; } Service;
bool select_chain(const Service *svcs, int n, int length, int budget, const char **out);
Search svcs in order for a chain of exactly length distinct services such
that no two share a domain and the sum of their latency is <= budget. On
success write the chosen names (in service order) into out[0..length) and return
true; otherwise return false.
Key concepts
- Include-or-skip backtracking: at each service, first try including it (if
its failure domain is still free and it fits the remaining budget) and recurse on
the rest; if no complete chain results, undo and try skipping it. Trying
include-before-skip makes the result deterministic and earliest-by-order.
- Prune on cost: carry a running latency sum and reject a service that would
exceed the budget — no point recursing into a branch that's already too
expensive.
- Distinct domains: a service is eligible only if no already-chosen service
shares its failure domain.
length == 0 is trivially satisfiable (the empty chain).
A fixed-size array tracks the chosen domains — no allocation.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/fallback && /tmp/fallback
Sign in to submit your solution.