Circuit Breaker Transitions Over an Event Stream
Problem Statement
Simulate a circuit breaker protecting a flaky tool. Process a stream of call outcomes and report the breaker's state after each.
Background
The breaker has three states. It starts closed (calls allowed). It trips to open after fail_threshold consecutive failures. While open, calls are blocked; the outcomes in the stream while open are skipped (the breaker does not see them) until a probe. After cooldown events have elapsed since opening, it moves to half_open and allows the next outcome as a probe: a success closes it (reset failure count), a failure re-opens it (reset the cooldown clock).
Simplified model for this exercise: iterate outcomes ("ok"/"fail"). Maintain state, a consecutive-failure counter, and an opened_at index.
- closed: on "fail" increment counter; if it reaches fail_threshold, go open and record opened_at. On "ok" reset counter.
- open: if current_index - opened_at >= cooldown, switch to half_open and process this outcome as a probe; otherwise stay open.
- half_open: "ok" -> closed (counter 0); "fail" -> open (record opened_at = current index, counter = fail_threshold).
Record the state string after processing each outcome.
Your Task
def circuit_states(outcomes, fail_threshold, cooldown):
Return the list of state strings, one per outcome.
Input Format
- outcomes (list of "ok"/"fail"), fail_threshold (int), cooldown (int).
Output Format
- A list of state strings.
Sample
print(circuit_states(["fail","fail","ok","ok"], 2, 1))
Output:
['closed', 'open', 'closed', 'closed']
Example:
print(circuit_states(["fail","fail","ok","ok"], 2, 1))
['closed', 'open', 'closed', 'closed']
- Index 0 (
"fail"): The breaker starts inclosedstate. The consecutive failure count increments to 1. Since 1<2 (the threshold), the state remainsclosed. - Index 1 (
"fail"): The failure count increments to 2. Since 2≥2, the breaker trips toopenand recordsopened_at = 1. - Index 2 (
"ok"): The state isopen. We check the cooldown condition: i−opened_at=2−1=1. Since 1≥1 (the cooldown), the breaker transitions tohalf_opento probe. The outcome is"ok", so the probe succeeds, and the state resets toclosedwith the failure count reset to 0. - Index 3 (
"ok"): The state isclosed. The outcome is"ok", so the failure count remains 0. The state staysclosed. - The final output is
['closed', 'open', 'closed', 'closed']
Constraints:
- States are
"closed","open","half_open". - Trip after
fail_thresholdconsecutive failures. - From open, after
cooldownelapsed indices, the next outcome is a half-open probe.
1. Background Knowledge
A circuit breaker is a resilience pattern used in distributed systems to prevent cascading failures. Instead of repeatedly hammering a failing dependency, the system "trips" the breaker into an open state, short-circuiting subsequent calls. After a cooldown period, the breaker enters a half_open state to test whether the dependency has recovered. A successful probe closes the breaker; a failed probe re-opens it.
The three-state machine follows a strict transition graph:
- closed → open: triggered when consecutive failures reach a threshold.
- open → half_open: triggered after a fixed number of events (the cooldown) have elapsed.
- half_open → closed: on a successful probe.
- half_open → open: on a failed probe, resetting the cooldown clock.
This is a classic finite state machine (FSM) problem. Each input event causes a state transition (or a self-loop), and you must record the state after processing each event. The key insight is that while the breaker is open, incoming outcomes are effectively ignored for failure counting purposes—the breaker only "sees" the first outcome after the cooldown expires, which serves as the probe.
2. Algorithm Approach
Use a single-pass simulation with explicit state variables:
- state: one of "closed", "open", "half_open".
- fail_count: consecutive failures while closed.
- opened_at: the index at which the breaker last transitioned to open.
For each outcome at index i, apply the transition rules based on the current state. The critical logic is in the open state: you must check whether i - opened_at >= cooldown to decide whether to transition to half_open and process the probe, or simply stay open and skip the outcome.
3. Step-by-Step Strategy
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.