Total Image Size from Unique Layers
Problem Statement
Container images share layers by content digest. Given the layers of several images, compute the total on-disk size counting each unique layer digest only once.
Background
A registry stores each layer once, keyed by digest. The disk footprint of a set of images is the sum of sizes over distinct digests, even if many images reference the same layer.
Your Task
def total_disk(images):
- images: list of images, each a list of (digest, size) tuples.
- Return the summed size of unique digests (int).
Input Format
- images (list of lists of (str, int)).
Output Format
- A single int.
Sample
print(total_disk([[("a", 100), ("b", 50)], [("a", 100), ("c", 30)]]))
Output:
180
Example:
print(total_disk([[("a", 100), ("b", 50)], [("a", 100), ("c", 30)]]))180
- Identify all unique layer digests across the two images. Image 1 contains layers "a" and "b", while Image 2 contains layers "a" and "c". The distinct set of digests is {"a","b","c"}.
- Determine the size associated with each unique digest. Since each digest maps to a single size, we have: "a" → 100, "b" → 50, and "c" → 30. Note that "a" appears in both images but is counted only once.
- Sum the sizes of these unique layers to find the total disk footprint: 100+50+30=180.
- The final output is 180
Constraints:
- Count each digest once (same digest implies same size).
- Sum sizes of the distinct digests.
- Return an int.
1. Background Knowledge
In container ecosystems like Docker or OCI, images are composed of layers. Each layer is identified by a content-addressable digest (a hash string). Because the digest is derived from the layer's content, two images that share the same layer will reference the exact same digest. This is the foundation of layer sharing: a registry or local daemon stores each unique layer only once, regardless of how many images reference it.
The disk footprint of a set of images is therefore not the sum of all layer sizes across all images, but the sum of sizes over the set of distinct digests. If image A has layers ("a", 100) and ("b", 50), and image B has layers ("a", 100) and ("c", 30), the total on-disk size is 100+50+30=180, not 100+50+100+30=280. The layer "a" is counted only once.
This problem reduces to a classic set union operation: collect all unique digests across all images and sum their associated sizes. The key insight is that the same digest always maps to the same size, so you can safely store a mapping from digest to size and sum the values.
2. Algorithm Approach
This is a deduplication and aggregation problem. The core pattern is:
- Collect unique keys: Iterate through all layers in all images and track which digests have been seen.
- Sum associated values: For each unique digest, add its size to a running total.
The most natural data structure for this is a dictionary (hash map) mapping each digest to its size. Since the same digest always has the same size, you can simply overwrite or skip duplicates. Alternatively, you could use a set to track seen digests and a separate accumulator, but a dictionary is more direct.
This is analogous to computing the size of the union of multiple sets, where each element carries a weight (the layer size).
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.