OPTIVER SWE OA 26/27

PowerCellBank

Language: C++20

You are writing the dispatch logic for the battery management system of a tiered power-cell bank that powers a heavy-duty industrial load. Cells are installed into the bank via LoadCell, and the load draws batches of cells via Discharge. Unused cells slowly self-discharge from charged through depleted to spent. To keep output voltage stable across discharge bursts, the system equalises charge between adjacent racks before each dispatch batch begins.

Scoring

The list below shows the test-case categories used to evaluate your submission, roughly ordered from most to least impactful. Use this as guidance for where to invest effort; categories are intentionally broad and can overlap, so don't over-optimize for labels.

State Management
Core Logic
Edge Cases
Scalability/Performance

Overview

Implement the PowerCellBank class with the following operations:

__init__ — (constructor) initialises the tiered cell bank.
LoadCell — installs a freshly-charged cell into the front-most rack that is not yet at capacity.
Discharge — equalises charge across rack pairs, then dispatches a batch of cells to the load.

The bank has num_racks racks arranged front-to-back, where rack 1 is the front rack (electrically closest to the load) and each successive rack sits further behind. The capacity of rack i is 2ⁱ. Each cell carries a rated_duration that drives the three-state lifecycle described in "Temporal States". Each Discharge call first runs a "Charge Equalisation" cycle and then dispatches cells one at a time via the "Bus Shift" rule.

Functions

init(num_racks: integer)

Initialises the bank with num_racks racks. This represents the constructor of the class in whatever programming language being used.
Rack i (1-indexed) has a capacity of 2ⁱ cells. Rack 1 is the front rack.
You may assume: 1 ≤ R < 2⁴, where R = num_racks.

LoadCell(timestamp: float, cell_id: string, rated_duration: float) -> bool

Installs one cell into the bank. Returns true on success and false if every rack is full.
The cell is installed in the front-most rack that still has free capacity. Capacity previously occupied by a spent cell counts as free.
rated_duration is the window the cell stays charged, in seconds, starting at timestamp.
You may assume:
- rated_duration > 0.
- No non-spent cell currently in the bank shares the new cell_id. A cell that has become spent (see Temporal States) is treated as absent, so its cell_id may be reused.

Discharge(timestamp: float, max_dispatch: integer) -> list[string]

Runs the Charge Equalisation cycle, then dispatches up to max_dispatch cells to the load via repeated pulls of the Bus Shift rule, in dispatch order.
Each returned entry has the form "cell_id:state", where state is "charged" if the cell is still within its rated window at the call's timestamp and "depleted" otherwise.
Dispatching stops early when the bank is empty.
cell_ids of dispatched or spent cells may be reused by later LoadCell calls.
You may assume 1 ≤ max_dispatch < 2¹⁰.

Temporal States

Each cell in the bank is in one of three temporal states, determined by the elapsed time t = timestamp - load_timestamp since its LoadCell call:

State	Elapsed Time	Dispatchable?	Occupies a Slot?	Status Label
Charged	t < rated_duration	yes	yes	`"charged"`
Depleted	rated_duration ≤ t < 2×rated_duration	yes	yes	`"depleted"`
Spent	t ≥ 2×rated_duration	no	no	—

State transitions happen automatically as time passes; no bookkeeping is required at the moment of transition. Spent cells are treated as absent: they do not appear in any output, they do not count against rack capacity, and they are excluded from every count and selection in Charge Equalisation and Bus Shift. Throughout the rest of this specification, every reference to "a cell" or "cells" means a non-spent cell unless stated otherwise.

The charge window of a cell at the call's timestamp is load_timestamp + rated_duration - timestamp. It is positive for charged cells and negative for depleted ones. Cells are ordered by their charge window at the call's timestamp, with ties broken by smallest cell_id under ordinary lexicographic (ASCII) comparison — for example, a precedes b.

Under this ordering, the most-charged cell in any set has the largest charge window, while the most-depleted cell has the smallest (smallest cell_id on ties for both). These two are duals: the most-charged cell is also the least-depleted, and the most-depleted is also the least-charged.

Charge Equalisation

At the start of each Discharge call, the system equalises charge between adjacent racks so the load sees a stable voltage as it begins drawing.

A rack is below-sag when it holds at least one cell and its charged fraction — the count of charged cells divided by the count of cells — is strictly below 50%.

The cycle visits racks in order from front to back. At each rack k that has a rear neighbour, while rack k is below-sag and rack k+1 holds at least one charged cell, the system performs a balance swap: rack k's most-depleted cell is swapped with rack k+1's most-charged cell. The cycle then moves on to rack k+1.

A rack with no rear neighbour, and a rack whose rear neighbour has run out of charged cells, take no further action in the cycle.

Bus Shift

Each pull dispatches one cell in two actions:

Dispatch: from the active rack — the front-most rack that holds at least one cell — dispatch the most-charged cell. If no such rack exists, the call stops dispatching and returns what it has so far.
Inward shift: the active rack's freed capacity is filled by advancing the most-charged cell forward from the next rack back. The inward shift frees one slot of capacity in that rack, which is filled the same way from the rack behind it, and so on. The shift halts as soon as the next rack back is empty or there is no further rack back.

A cell that arrives at a rack via the inward shift is immediately eligible for the next pull.

Constraints

Operations arrive in non-decreasing timestamp order and are processed in the order they arrive. Within a single timestamp, ties are broken by call order.
Timestamps are seconds since the Unix Epoch (Jan 1, 1970 UTC), as floating-point values with millisecond precision. They are positive and fit into 32 bits.
rated_duration is a floating-point value with millisecond-level precision (3 decimal places).
State transition thresholds and the 50% charged-fraction threshold are exact. Test inputs are constructed so that observed charge windows and charged fractions stay clear of these thresholds by a margin that exceeds floating-point precision.
1 ≤ N < 2¹⁵, where N is the total number of operations given to the program.

Input Format For Custom Testing

Input to the program is specified using a simple text format. The format and details of parsing are not relevant to answering the question but custom input can be used to help with development and debugging.

The first line must always be in the format below:

Init <num_racks>

Each subsequent input line may contain one of the instructions as in the format below:

LoadCell <timestamp> <cell_id> <rated_duration>
Discharge <timestamp> <max_dispatch>

An example input and its expected output is described below.

Sample Case

Sample input for custom testing:

Init 3
LoadCell 100.000 a 130.000
LoadCell 100.000 b 130.000
LoadCell 100.000 c 1000.000
LoadCell 100.000 d 1000.000
LoadCell 100.000 e 80.000
LoadCell 100.000 f 80.000
LoadCell 100.000 g 1000.000
LoadCell 100.000 h 1000.000
Discharge 250.000 3
Discharge 600.000 5

Expected output:

LoadCell=True
LoadCell=True
LoadCell=True
LoadCell=True
LoadCell=True
LoadCell=True
LoadCell=True
LoadCell=True
Discharge=['c:charged', 'd:charged', 'g:charged']
Discharge=['h:charged']

Explanation

The sample has two Discharge calls, at t = 250 and t = 600. The cell deadlines below are written as absolute timestamps for direct comparison against those two call times.

Init 3 creates a bank with rack capacities [2, 4, 8] (14 cells of capacity in total). Front-most-first loading lands a-b on rack 1, c-f on rack 2, and g-h on rack 3, all at t=100. Cell deadlines:

Cells	Rated	Depleted ts	Spent ts
a, b	130	230	360
c, d	1000	1100	2100
e, f	80	180	260
g, h	1000	1100	2100

Bank state across the two Discharge calls:

Step	Rack 1	Rack 2	Rack 3
After 8 LoadCells	[a, b]	[c, d, e, f]	[g, h]
Discharge 250 post-equalisation	[b, c]	[a, d, f, g]	[e, h]
Discharge 250 post-3-pulls	[b, h]	[a, f, e]	[]
Discharge 600 spent excluded	[h]	[]	[]
Discharge 600 post-1-pull	[]	[]	[]

Per-Discharge walkthrough:

Discharge 250.000 3 — at the discharge timestamp t = 250, cells a, b, e, f are depleted (windows -20, -20, -70, -70) and c, d, g, h are charged (window +850).

Equalisation. Rack 1 reads [a, b], fraction 0/2 = 0%, below-sag. The system swaps a (smaller cell_id over b) with rack 2's most-charged c (smaller cell_id over d). Rack 1 becomes [b, c], fraction 1/2 = 50%, no longer below-sag. Rack 2 now reads [a, d, e, f], fraction 1/4 = 25%, below-sag; the system swaps e (smaller cell_id over f) with rack 3's most-charged g. Rack 2 becomes [a, d, f, g], fraction 2/4 = 50%, no longer below-sag. Rack 3 has no rear neighbour; cycle ends.
Pulls. Pull 1 dispatches c:charged; the inward shift advances d (smaller cell_id over g) from rack 2 into rack 1, then h (more charged than the depleted e) from rack 3 into rack 2. Pull 2 dispatches d:charged; the shift advances g (smaller cell_id over h), then e. Pull 3 dispatches g:charged; the shift advances h from rack 2 and halts (rack 3 empty).

Discharge 600.000 5 — at the discharge timestamp t = 600, cells a, b, e, f are all spent (spent thresholds ≤ 360) and excluded from every count and selection. Rack 1 therefore holds only h (charged, window +500), and racks 2-3 are empty. Equalisation is a no-op (fraction 1/1 = 100%). The first pull dispatches h:charged; the second pull finds the bank empty and dispatching stops after one cell.

The cascade in the first call — rack 1's swap dropping rack 2 below 50%, which then prompts rack 2 to draw from rack 3 — is the equalisation rule's signature behaviour: charge propagates forward through the rack chain in a single front-to-back pass.

Code Stub

class PowerCellBank {
public:
    PowerCellBank(int numRacks) {
        // Your code here...
    }

    bool loadCell(
        double timestamp,
        const std::string& cellId,
        double ratedDuration
    ) {
        // Your code here...
        return false;
    }

    std::vector<std::string> discharge(
        double timestamp,
        int maxDispatch
    ) {
        // Your code here...
        return {};
    }
};

OPTIVER SWE OA 26/27

OverheatPreventionController

Language: C++20

You are implementing the firmware controller that prevents a multi-core microprocessor from overheating. Every core runs a workload that produces heat proportional to its configured load, and all cores share a fixed cooling capacity. The operating system (OS) is in charge of assigning workloads via SetCoreLoad, and drives the controller forward via Tick on a cadence of its choosing to learn how each core's status has changed.

Scoring

State Management
Core Logic
Edge Cases
Scalability/Performance

Overview

Implement the OverheatPreventionController class with the following operations:

__init__ — (constructor) initializes the controller with its cooling capacities and cores.
SetCoreLoad — lazily updates a core's configured workload; can also restart a shut down core.
Tick — advances the controller's internal state to the given timestamp, processes any pending load changes and returns the cores whose status has changed since the previous Tick.

The controller doesn't have temperature sensors; instead, it must calculate the temperature of each core based on the configured loads and the cooling layout, as defined in Thermal Dynamics. Loads are given in watts (W).

Functions

init(passive_cooling_capacity: float, active_cooling_capacity_per_core: float, core_ids: list[string])

This represents the constructor of the class in whatever programming language being used.
Initializes the controller with the given passive_cooling_capacity (the shared passive cooling budget, in watts), active_cooling_capacity_per_core (the dedicated per-core active-cooling capacity, in watts, applied uniformly to every core when engaged), and the list of valid core_ids.
All cores start at ambient temperature (20.0 degrees C), running, with load 0 and active cooling off (i.e., status idle, see Tick below).
You may assume:
- 1 ≤ R < 2¹⁰, where R is the total number of cores.
- passive_cooling_capacity > 0 and active_cooling_capacity_per_core > 0.
- All core identifiers are unique.

SetCoreLoad(timestamp: float, core_id: string, load_watts: float)

Records a new configured load for the given core. Performs no thermal arithmetic. The new load only takes effect at the next Tick.
If two or more SetCoreLoad calls land on the same core between two Ticks, only the last one takes effect.
If the core is currently shut down, this call also acts as a manual restart attempt: it will restart the core with the new load, but only if the core's temperature observed at the next Tick is strictly below 50 degrees C. Otherwise the restart is discarded and the core stays shut down with load 0 — restarting later requires another SetCoreLoad call.
If the core is currently running, the new load is simply recorded and processed normally at the next Tick.
You may assume core_id always exists and load_watts is always within [0, 2¹⁵).

Tick(timestamp: float) -> list[string]

It does, in order:

Advances the controller to timestamp in a single step. See Thermal Dynamics for how temperatures evolves.
Shuts down any core whose temperature has reached 80 degrees C (its load is cleared to 0).
Processes any pending load changes, including restart attempts on shut down cores.
Decides which cores should have active cooling engaged for the upcoming interval. See Active Cooling for details.

Returns the cores whose status has changed since the previous Tick (or diverged from the initial state), where a core's status is one of:

idle — running, active cooling off.
cooling — running, active cooling engaged for the upcoming interval.
shutdown — shut down.

Each entry of the returned list has the format "core_id=status". The list is sorted alphabetically by core_id. An empty list means nothing has changed.

Thermal Dynamics

At every Tick, the controller first computes each core's temperature at the given timestamp. A core's temperature is determined as follows:

Every core's temperature evolves linearly at a rate of 0.02 degrees C/s per watt of net heat balance, positive or negative. Net heat balance is the core's load minus all its allocated cooling. When cooling down, a core's temperature will never drop below 20.0 degrees C.
The cooler distributes its effective passive cooling capacity across the cores according to their passive cooling demand. The demand is load + 2 W per core, where +2 W represents the maximum passive heat dissipation per core. The passive cooling distribution is as follows:
- If the total passive demand fits within the effective passive capacity, every core's demand is fully met.
- Otherwise, capacity is distributed proportionally to each core's demand.
The cooler's effective passive cooling capacity depends on whether active cooling was engaged by the previous Tick. The effect is described below.

Active Cooling

At the end of each Tick, the controller decides which cores should have active cooling engaged until the next Tick, when the decision will be reassessed from scratch. Active cooling works as follows:

Each core has a dedicated active-cooling channel that delivers exactly active_cooling_capacity_per_core watts on top of the passive cooling when engaged on that core.
Active cooling is expensive, therefore it should be engaged on as few cores as possible to satisfy these rules:
- Any core whose temperature is rising faster than 0.5 degrees C/s must be engaged.
- Any core whose temperature is above 60 degrees C must be engaged.
When active cooling is on, the passive cooler vibrates and runs less efficiently. The efficiency decreases proportionally to the number of cores that have active cooling engaged. When k cores are actively cooling, the total passive cooling capacity is reduced by vibration_penalty(k) percent, where:
- vibration_penalty(0) = 0.
- vibration_penalty(k) = sum over i=1..k of (10 / Fib_i), where Fib_i is the i-th term of the sequence 1, 2, 3, 5, 8, 13, ... (Fibonacci, starting from its second term).
Because engaging active cooling on a core increases the vibration penalty for everyone, it can in turn lift other cores' rates above 0.5 degrees C/s and trigger their engagement as well within the same interval.

Constraints

All timestamps are globally ever-increasing. Operations will never arrive out of order.
Timestamps are seconds since the Unix Epoch (Jan 1, 1970 UTC), as floating-point values with millisecond precision. They are positive and fit into 32 bits.
Loads and cooling capacities are in watts, as floating-point values with milliwatt precision (3 decimal places).
State transition thresholds and the active-cooling rate threshold are exact. Test inputs are constructed so that observed temperatures and rates stay clear of these thresholds by a margin that exceeds floating-point precision.
1 < N < 2¹⁰, where N is the total number of operations given to the program.

Input Format For Custom Testing

The first line must always be in the format below:

Init <passive_cooling_capacity> <active_cooling_capacity_per_core> <core1> <core2> ...

Each subsequent input line may contain one of the instructions as in the format below:

SetCoreLoad <timestamp> <core_id> <load_watts>
Tick <timestamp>

An example input and its expected output is described below.

Sample Case

Sample input for custom testing:

Init 545 60 coreA coreB coreC
SetCoreLoad 100.000 coreA 350.0
SetCoreLoad 100.000 coreB 200.0
SetCoreLoad 100.000 coreC 50.0
Tick 100.000
Tick 250.000
SetCoreLoad 1099.000 coreA 350.0
Tick 1100.000

Expected output:

Tick=['coreA=cooling', 'coreB=cooling']
Tick=['coreA=shutdown', 'coreB=idle']
Tick=['coreA=cooling', 'coreB=cooling']

Explanation

The controller manages a three-core processor with 545 W of shared passive cooling and 60 W of active cooling per core. All cores start at 20.0 degrees C, running, with load 0 (status idle).

Timestamp	Event	Temp A	Status A	Temp B	Status B	Temp C	Status C
—	Init	20.000	idle	20.000	idle	20.000	idle
100.000	SetCoreLoad x3 (loads pending)	20.000	idle	20.000	idle	20.000	idle
100.000	Tick	20.000	cooling	20.000	cooling	20.000	idle
250.000	Tick	82.75	shutdown	20.000+	idle	50.75	idle
1099.000	SetCoreLoad coreA 350 (pending restart)	82.75	shutdown	20.000+	idle	50.75	idle
1100.000	Tick (row cut off in photos; reconstructed from walkthrough)	48.75	cooling	20.000+	cooling	20.000+	idle

+ = clamped at the ambient floor of 20.0 degrees C.
(Note: the final Tick 1100.000 row was cut off at the bottom of the screenshots; its values are reconstructed from the per-Tick walkthrough below.)

Per-Tick walkthrough

Tick 100.000 — first Tick; every core reads ambient regardless of the pending loads. The pending loads (350, 200, 50 W) are then committed and active cooling is decided for the upcoming interval. With no active cooling engaged the passive cooler is overloaded (352 + 202 + 52 = 606 W > 545 W), and coreA's would-be rate is (350 - 545 * 352 / 606) / 50 ~= 0.67 degrees C/s, above the 0.5 degrees C/s threshold — so coreA's active cooling engages. Vibration drops effective passive capacity to 545 * 0.9 ~= 490.5 W; under that capacity coreB's would-be rate becomes (200 - 490.5 * 202 / 606) / 50 ~= 0.73 degrees C/s, also above the threshold, so coreB's active cooling engages too. Vibration grows to 15%, and coreC's rate is now (50 - 463.25 * 52 / 606) / 50 ~= 0.21 degrees C/s, still well below the threshold — coreC stays passive. coreA and coreB flip from idle to cooling, coreC is unchanged.
Tick 250.000 (150 s later) — under the engaged set {coreA, coreB} and 15% vibration, coreA heated at ~= +0.42 degrees C/s, coreB cooled at ~= -0.29 degrees C/s (its 60 W of active cooling exceeds its passive deficit), and coreC heated at ~= +0.21 degrees C/s. coreA crosses 80 degrees C and shuts down; its load is cleared to 0 and total demand falls to 2 + 202 + 52 = 256 W. Effective passive capacity (no engagement) of 545 W covers everyone fully — no core's rate exceeds 0.5 degrees C/s, so active cooling disengages on both coreA and coreB. coreA flips from cooling to shutdown, coreB from cooling back to idle, coreC is unchanged.
SetCoreLoad coreA 350 at 1099.000 records a pending load on the shut down core; the actual restart attempt happens on the next Tick.
Tick 1100.000 (850 s after the previous Tick) — with no active cooling and full passive cover, every core drifts at -0.04 degrees C/s. coreA cools from 82.75 degrees C down to 48.75 degrees C, dipping below the 50 degrees C restart line; the pending load is accepted and coreA restarts with load 350 W. The other two cores hit the 20 degrees C ambient floor along the way. Total demand is back to 606 W (over capacity), and the same cascade as at Tick 100.000 re-engages active cooling on coreA and coreB. coreA goes straight from shutdown to cooling in this single Tick, coreB flips from idle to cooling, coreC is unchanged.

Starter Code (C++20)

#include <map>

class OverheatPreventionController {
public:
    OverheatPreventionController(double passiveCoolingCapacity, double activeCoolingCapacityPerCore,
        const std::vector<std::string>& coreIds) {
        // Your code here...
    }

    void setCoreLoad(double timestamp, const std::string& coreId, double loadWatts) {
        // Your code here...
    }

    std::vector<std::string> tick(double timestamp) {
        // Your code here...
        return {};
    }
};

int main() { ... }

PowerCellBank

Scoring

Overview

Functions

__init__(num_racks: integer)

LoadCell(timestamp: float, cell_id: string, rated_duration: float) -> bool

Discharge(timestamp: float, max_dispatch: integer) -> list[string]

Temporal States

Charge Equalisation

Bus Shift

Constraints

Input Format For Custom Testing

Sample Case

Explanation

Code Stub

OverheatPreventionController

Scoring

Overview

Functions

__init__(passive_cooling_capacity: float, active_cooling_capacity_per_core: float, core_ids: list[string])

SetCoreLoad(timestamp: float, core_id: string, load_watts: float)

Tick(timestamp: float) -> list[string]

Thermal Dynamics

Active Cooling

Constraints

Input Format For Custom Testing

Sample Case

Explanation

Per-Tick walkthrough

Starter Code (C++20)

init(num_racks: integer)

init(passive_cooling_capacity: float, active_cooling_capacity_per_core: float, core_ids: list[string])