Learn the vocabulary of pruning search-tree branches the instant their best possible outcome is proven worse.
0 / 5 completed
1 / 5
At standup, a dev mentions exploring a search tree of candidate solutions but pruning away entire branches the instant their best possible outcome is proven worse than the best solution already found. What is this technique called?
Branch and bound is exactly this: it explores a search tree of candidate solutions, computing a bound on the best possible outcome reachable from each branch, and prunes away any branch whose bound is already worse than the best solution found so far, since exploring it further could never improve on that best solution. A hash collision is an unrelated hash-table concept about two keys sharing a bucket. This prune-provably-worse-branches behavior is exactly why branch and bound can solve optimization problems far faster than exhaustively exploring every candidate.
2 / 5
During a design review, the team relies on branch and bound's bounding step specifically so an entire subtree of candidate solutions can be skipped the moment its best possible outcome is proven no better than an already-found solution. Which capability does this provide?
Branch and bound's bounding step provides avoiding wasted exploration of subtrees that could never actually improve on the best solution found so far, without ever risking missing the true optimum, since a bound that's provably worse than the current best guarantees nothing better could possibly come from that subtree, letting it be skipped entirely with full confidence. Checking every single candidate solution individually would waste time re-deriving that same conclusion the hard way. This safe-pruning behavior is exactly what lets branch and bound stay both efficient and provably correct.
3 / 5
In a code review, a dev notices an optimization feature explores every single candidate solution in a large search tree exhaustively, with no bounding or pruning logic to skip branches that can't possibly beat the best solution found so far. What does this represent?
This is a missed branch-and-bound opportunity, since exploring every single candidate solution exhaustively wastes enormous effort on subtrees that a simple bound could immediately prove can never beat the best solution already found, while branch and bound would skip those subtrees entirely. A cache eviction policy is an unrelated concept about discarded cache entries. This exhaustive-exploration pattern is exactly the kind of avoidable cost a reviewer flags once a bounding function for the problem is available.
4 / 5
An incident report shows an optimization job's runtime ballooned far beyond expectations on larger inputs, because it explored every single candidate solution exhaustively instead of using a bounding function to prune subtrees that couldn't possibly improve on the best solution found so far. What practice would prevent this?
Rewriting the search using branch and bound, computing a bound for each subtree and pruning it the moment that bound is proven worse than the current best solution, dramatically cuts the amount of the search tree that needs to be explored, which is exactly the fix for the ballooning runtime described in this incident. Continuing to exhaustively explore every candidate regardless of input size is exactly what let the runtime explode. This bounding-and-pruning approach is the standard fix for optimization problems where a useful bound on each subtree's best possible outcome can be computed.
5 / 5
During a PR review, a teammate asks why the team reaches for branch and bound instead of a purely greedy algorithm that commits to the locally best choice at every step. What is the reasoning?
A purely greedy algorithm commits irrevocably to whatever choice looks locally best at each step, which can lock in a globally suboptimal solution with no way to reconsider, while branch and bound still explores multiple alternatives but safely discards only the ones a bound proves can never beat the best solution found so far, preserving a guarantee of finding the true optimum. The tradeoff is that branch and bound generally costs more time and bookkeeping than a purely greedy approach. This is exactly why a purely greedy algorithm is preferred when it's known to be optimal or when an approximate answer suffices, while branch and bound is reserved for problems that genuinely require a provably optimal solution.