Fallback Chain Selector (Go)
Topics: backtracking, pruning, networking
Problem
A client needs a primary backend plus some number of fallbacks — a fixed-size chain of distinct
services. To avoid a single outage taking down the whole chain, no two services in the chain may
share a failure domain (rack, AZ, region — whatever the deployment considers a blast radius).
The chain also has a total latency budget: the sum of each service's expected latency must not
exceed it.
type Service struct {
Name string
FailureDomain string
Latency int
}
func SelectChain(services []Service, length int, budget int) ([]string, bool)
SelectChain searches services, in order, for a chain of exactly length services where no two
share a FailureDomain and the sum of Latency is at most budget. It returns the chosen names,
in the order they were picked, and true — or nil, false if no such chain exists.
p: domain a, latency 2
q: domain b, latency 1
r: domain a, latency 1
SelectChain([p, q, r], length=2, budget=2) -> ["q", "r"], true
Key concepts
- Subset search with two choices per item: for each service, in order, the solver either
includes it (if its failure domain is still free and it fits the remaining budget) or skips
it. This is the classic "include or skip, recurse on the rest" combination search.
- Pruning on cumulative cost: before including a service, the solver checks that
sum + service.Latency <= budget. This cuts off whole subtrees early — no point exploring a
chain that's already over budget.
- Why backtracking: in the example above,
p (latency 2) alone consumes the entire budget of
2, so any chain that includes p can have only one member — never reaching length = 2. The
solver commits to including p first (it fits on its own), discovers no second service can be
added, and must undo including p before it can find [q, r].
- Proving infeasibility: if every way of including/skipping services fails to reach
length
services within budget and distinct failure domains, the search exhausts all of them before
reporting false.
The Service struct is provided; you implement SelectChain.
Run
go test -v ./challenges/fallback-chain/go/
Sign in to submit your solution.