First Cache-Invalidated Build Layer
Problem Statement
Docker reuses cached layers until the first instruction whose inputs changed; everything from there down rebuilds. Given each instruction's cache key for the previous and current build, find the index of the first rebuilt layer.
Background
Builds compare instruction cache keys top to bottom. All layers match the cache until the first index where the current key differs from the previous build's key — that layer and every layer after it are rebuilt. If the current build has more instructions than the previous, the extra tail is new (rebuilt).
Your Task
def first_rebuild(prev_keys, cur_keys):
Return the 0-based index of the first rebuilt layer, or -1 if the build is fully cached (current is a prefix-equal of previous with no extra layers).
Input Format
- prev_keys, cur_keys (lists of strings).
Output Format
- An int index or -1.
Sample
print(first_rebuild(["a", "b", "c"], ["a", "b", "x"]))
Output:
2
Example:
print(first_rebuild(["a", "b", "c"], ["a", "b", "x"]))
2
- Compare the first layer (index 0): the previous key is
"a"and the current key is"a". Since they match, the cache is valid for this layer, so we proceed to the next index. - Compare the second layer (index 1): the previous key is
"b"and the current key is"b". Since they match, the cache remains valid, and we move to the next index. - Compare the third layer (index 2): the previous key is
"c"and the current key is"x". Since"c" \neq "x", this is the first point of divergence where the inputs have changed. - Because a mismatch is found at index 2, all layers from this index onward must be rebuilt, making index 2 the first rebuilt layer.
- The final output is 2
Constraints:
- Compare keys by index; first mismatch is the rebuild point.
- If
curis longer and matches on the shared prefix, the first extra index is the rebuild point. - Return
-1when fully cached (no mismatch andlen(cur) <= len(prev)).
1. Background Knowledge
In containerized build systems like Docker, a build is composed of sequential layers, each defined by an instruction (e.g., COPY, RUN). To speed up repeated builds, the system maintains a content-addressable cache: each layer is identified by a cache key derived from its instruction and inputs. During a rebuild, the system walks the instruction list from top to bottom, comparing each current key against the corresponding key from the previous successful build.
The critical rule is prefix matching: the cache is valid only for the longest common prefix of keys. The moment a key differs, that layer and all subsequent layers are invalidated and must be rebuilt. This is because later layers may depend on the output of earlier ones; a change upstream can alter downstream results even if their instructions are textually identical.
If the current build has more instructions than the previous one, the extra trailing instructions have no prior cache entry and are therefore always rebuilt. Conversely, if the current build is shorter but its keys match the prefix of the previous build, the build is fully cached (no rebuild needed).
2. Algorithm Approach
This is a straightforward linear scan with early termination. You compare elements pairwise from index 0 upward. The algorithm stops at the first index i where either:
- prev_keys[i] != cur_keys[i], or
- i≥len(prev_keys) (current build has extra layers).
The first such index is the answer. If no mismatch is found and the current list is not longer than the previous, return −1.
This mirrors the logic of finding the longest common prefix between two sequences, a pattern common in string algorithms and cache invalidation logic.
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.