How should I practice Minimum Snapshots for a Version Tree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Adobe online assessment problems in FastPrep.

Is Minimum Snapshots for a Version Tree associated with Adobe?

FastPrep tags this as a Adobe online assessment coding practice problem when the problem catalog has that company and stage context.

Minimum Snapshots for a Version Tree

Adobe● HardNEW GRADOA

Learn

Problem statement

A version-control system stores n + 1 versions as a rooted tree. Version 0 is the root and is always stored as a snapshot. For every version i from 1 through n, parents[i - 1] is its parent and is smaller than i.

Reading a version requires replaying edits from its nearest stored ancestor. Its reconstruction cost is the number of tree edges to that ancestor; a stored version has cost 0.

You may store additional versions as snapshots. Return the minimum number of additional snapshots needed so that every version has reconstruction cost at most maxCost.

Function

minimumSnapshots(n: int, maxCost: int, parents: int[]) → int

Examples

Example 1

n = 5maxCost = 2parents = [0,1,2,3,4]return = 1

The versions form one chain. Storing version 3 keeps versions 3, 4, and 5 within cost 2; root snapshot 0 already covers versions 1 and 2.

Example 2

n = 3maxCost = 1parents = [0,1,1]return = 1

Store version 1. Both children 2 and 3 are then one edge from a stored ancestor.

Example 3

n = 6maxCost = 2parents = [0,1,2,3,4,5]return = 2

One optimal choice stores versions 1 and 4. Every version is then at most two edges below its nearest stored ancestor.

Constraints

1 <= n <= 2 * 10^5.
parents.length = n.
0 <= parents[i] <= i for every 0 <= i < n.
0 <= maxCost <= n.
Version 0 is already stored and is not counted in the result.

Source note: The original screenshot's account mark and yellow strokes obscured part of the statement. This six-panel display redacts that exact band without reconstructing hidden text, preserves every source-visible pixel outside it, and uses overlapping crops for normal desktop and mobile readability.