Snapshot Set Outputs
MediumDesign · Databricks
Implement a set of integers that supports snapshot iterators: an iterator created at some moment must keep returning the set's contents as of that moment, no matter how the set is modified later. Process operations in order; each one adds one entry to the output list:
["add", x]: addx. OutputTrueif it was not already present, otherwiseFalse.["remove", x]: removex. OutputTrueif it was present, otherwiseFalse.["contains", x]: output whetherxis currently in the set.["snapshot"]: take a snapshot of the current contents. Snapshots are numbered0, 1, 2, ...in creation order; output the new snapshot's number.["iterate", snapshot_id]: output the list of values that were in the set when snapshotsnapshot_idwas taken, sorted ascending.
Return the list of outputs.
Snapshots can be frequent and sets large, so aim to make taking a snapshot cheap (no full copy of the set) and pay the cost only when a snapshot is actually iterated.
Example 1
- Input:
- operations = [["add", 5], ["add", 2], ["snapshot"], ["remove", 5], ["add", 9], ["snapshot"], ["iterate", 0], ["iterate", 1], ["contains", 5]]
- Output:
- [True, True, 0, True, True, 1, [2, 5], [2, 9], False]
- Explanation
- Snapshot 0 is taken while the set holds 2 and 5. Removing 5 and adding 9 afterwards does not change what snapshot 0 iterates; snapshot 1 sees 2 and 9. The live set no longer contains 5.
Example 2
- Input:
- operations = [["add", 1], ["add", 1], ["remove", 3], ["snapshot"], ["remove", 1], ["add", 1], ["iterate", 0]]
- Output:
- [True, False, False, 0, True, True, [1]]
- Explanation
- Adding a value already present returns
False, as does removing one that is absent. Value 1 is removed and re-added after the snapshot, but it was present when the snapshot was taken, so it is iterated.
Example 3
- Input:
- operations = [["snapshot"], ["add", 4], ["iterate", 0]]
- Output:
- [0, True, []]
- Explanation
- The snapshot was taken while the set was empty, so it iterates nothing even though 4 is added later.
Constraints
0 <= operations.length <= 10^5-10^9 <= x <= 10^9- Every
snapshot_idin aniteraterefers to an existing snapshot