2
$\begingroup$

There's an array which changes with every iteration, i.e., an element is added or deleted in every iteration. I have to save the "state" of the array for every iteration, which would later be retrieved upon querying.

For ex -

Initially, the array is [7, 8, 9]. This is version 1.
Next, 90 was added. Version 2 is [7, 8, 9, 90].
Next, 23 was added. Version 3 is [7, 8, 9, 90, 23].
Next, 90 was deleted. Version 4 is [7, 8, 9, 23].

And so on.

I need to write a function, get_version(ver_num), which returns the state of the array for each version. So, running get_version(3) should return [7, 8, 9, 23].

I have thought of saving incremental changes to the array in each iteration, in the form of an array maybe.

For ex -

[("add", [7, 8, 9]), ("add", [90]), ("add", [23]), ("subtract",[90])]

This will save space but in order to recreate the array for a specific version, I have to iterate over this array until I reach the required version. Is there a way better than this?

Thanks

$\endgroup$
  • 3
    $\begingroup$ Although I don't know the details offhand, you are looking for persistent data-structures. I would start with the Wikipedia entry on persistent arrays: en.wikipedia.org/wiki/Persistent_array. $\endgroup$ – user340082710 Aug 8 at 14:50
0
$\begingroup$

The key observation is the fact that only a single value will be changed in every operation.

For each element maintain an array of the form [(snap_id, value)].

Every time you need to snapshot the array, find out which elements have changed since their last snap_shot and update only those elements.

If you are asked to retrieve the value of any element at any given snap_id then you can simply binary_Search over the array of (snap_id, value) and return the value corresponding to the snap_id that is the closest but lesser(lower_bound in CPP) than the requested id.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.