Minimum Rebuild Cost with Layer Caching

hardPROContainer Images & BuildsSystems & InfrastructureML Systems & Infrastructure 1

Problem Statement

Given a linear Dockerfile where each instruction has a build cost, and a set of instructions whose inputs changed, compute the total build time knowing that a cached layer is free but any layer at or below the first change must rebuild.

Background

Layers build top to bottom. A layer is rebuilt if it changed or any layer above it was rebuilt (cache invalidation cascades downward). So the first changed index f triggers rebuild of all layers f..n-1; layers 0..f-1 are cached (free). The total build time is the sum of cost[i] for i >= f. If nothing changed, total is 0. Additionally, an optional always set marks layers that never cache (e.g. ADD of a remote URL) — such a layer also forces itself and everything below to rebuild.

Your Task

def rebuild_cost(costs, changed, always=None):

costs: list of per-layer build costs.
changed: set/list of indices whose inputs changed.
always: optional set/list of indices that never cache.
Return the total rebuild time (int/float).

Input Format

costs (list of numbers), changed (list of ints), always (list of ints or None).

Output Format

A number (total rebuild cost).

Sample

print(rebuild_cost([1, 2, 3, 4], [2]))

Output:

Example

Input

print(rebuild_cost([1, 2, 3, 4], [2]))

Output

Reasoning

Identify the set of invalid layers by combining the changed indices with any always indices; here, changed is $\{2\}$ and always is empty, so the invalid set is $\{2\}$ .
Determine the first invalid index $f$ by finding the minimum value in the invalid set, which is $f = 2$ ; this index marks the start of the rebuild cascade.
Select the sub-list of costs from index $f$ to the end of the list, which corresponds to layers 2 and 3: $[3, 4]$ .
Calculate the total rebuild cost by summing the selected costs: $3 + 4 = 7$ .
The final output is 7

Constraints

The first invalidation index f = min(changed ∪ always); if empty, cost is 0.
Rebuild all layers i >= f; sum their costs.
always defaults to empty.

Learn this in

Docker & ContainerizationSystems & Networking

More from ML Systems & Infrastructure 1

Spot vs On-Demand Expected-Cost Decisionmedium Minimum-Cost Job Scheduling Across Priced Windowshard Deduplicate Retried Pipeline Runs by Idempotency Keymedium Retry with Capped Exponential Backoff and Jitter Capmedium Critical Path Length of a Pipeline DAGmedium

Concept primerPREVIEW

1. Background Knowledge

In containerized build systems (e.g., Docker), a build is decomposed into layers, each corresponding to an instruction in a Dockerfile. Layers are built sequentially from top to bottom. A critical optimization is layer caching: if the inputs to a layer have not changed and all layers above it are also unchanged, the layer can be reused from cache at zero cost.

However, cache invalidation is cascading. If any layer at index $i$ is invalidated (either because its inputs changed or because it is marked as non-cacheable), then every layer at index $j \ge i$ must also be rebuilt. This is because the output of layer $i$ is an input to layer $i+1$ , so a change propagates downward through the entire remaining build. The "first" invalidation point determines the rebuild boundary.

The always set represents instructions that inherently cannot be cached, such as ADD of a remote URL or RUN commands that depend on external state. These layers act as permanent invalidation points, forcing themselves and all subsequent layers to rebuild regardless of whether their direct inputs changed.

2. Algorithm Approach

This is a boundary detection problem. The core insight is that the total rebuild cost is simply the sum of costs from the minimum invalidation index to the end of the list.

The algorithm involves:

Identifying all invalidation points: the union of changed indices and always indices.
Finding the minimum index among these invalidation points. This is the first layer that must rebuild.
Summing the costs from that minimum index to the end of the costs list.

If there are no invalidation points (both changed and always are empty or None), the total cost is 0.

This is a linear scan problem with a simple aggregation step. No sorting or complex data structures are needed.

3. Step-by-Step Strategy

Handle edge cases: If costs is empty, return 0. If both changed and always are empty (or None), return 0.
Collect invalidation indices: Create a set or list containing all indices from changed and always. Be careful to handle None for always.
Find the minimum index: Compute min_index = min(invalidation_indices). This is the first layer that must rebuild.
Sum the tail: Return sum(costs[min_index:]). This sums all costs from the first invalidation point to the end.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

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.

solution.py

Python 3.13

Test results