Minimum Rebuild Cost with Layer Caching
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:
7
Example:
print(rebuild_cost([1, 2, 3, 4], [2]))
7
- Identify the set of invalid layers by combining the
changedindices with anyalwaysindices; here,changedis {2} andalwaysis 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. alwaysdefaults to empty.
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≥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.
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.