1
$\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$
  • 2
    $\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

Your Answer

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

Browse other questions tagged or ask your own question.