Implementing undo and redo for an array

Question

I got this question in a Java interview today.

I have to implement a collection which is an array and have add and delete methods which can perform only at the end of an array.

In addition to that I have to implement two more methods which is the undo and redo methods which can be performed only once.

For example:

Let x be an array containing {1,5,7,9}.

Now I add {44,66,77} in it and make it {1,5,7,9,44,66,77}.

Now when I undo it, the array should delete {44,66,77}. And if I do redo afterwards, it should be back to {1,5,7,9,44,66,77}.

And similarly for the delete.

What is the best way to achieve this in terms of complexity and memory?

My solution to the interviewer:

1. Make one string field which stores the last operation, i.e. "Add"/"Delete".
2. And a hashmap which stores key as an index of array and value as the index value of an array.

Which is a totally incorrect solution as per interviewer.

Answer 1

I would solve it like this. Basically, there will be three lists.

• A list with actual values
• Undo list with instances of Command interface

• Redo list with instances of Command interface (optional, explained below)

  public interface Command {
      void do();
      void undo();
  }
  

There will be two Command implementations: AddCommand and RemoveCommand.

• On add(), new instance of AddCommand created and added to the undo list. Then we call do() of this command, which modifies actual values and stores index of added item.
• On remove(), new instance of RemoveCommand created and added to the undo list. Then we call do() of this command, which modifies actual values and stores index and value of removed item.
• On undo() we pull last command from the undo list and execute undo() method of this command. The command pushed to the redo list. Undo methods of AddCommand and RemoveCommand revert changes back.
• On redo() we pull last command from the redo list and execute do() method again. Pulled command gets added to undo list.

Another optimization would be to remove redo list and use undo index instead. In this case when you undo(), you don't need to remove/add value from the list, but just decrease the undo index by one. Similarly, redo() will increase it by one.

Thus the final solution will have list of values, undo list and an index value.

Update:

For the simplest case, where only one undo()/redo() operation is required, solution will look even simpler. Instead of having undo list and index, it's enough to store the latest command instance. Thus you we will have a list of values and an instance of last undo command.

Answer 2

Either I misunderstand the question, or people are overthinking this. The question has quite a lot of constraints, so:

• Array for current contents
• Extra array for lastly removed items (needed to undo delete / redo add)
• One variable for previous length of array (needed to undo add / redo delete)
• One enum variable for last operation (add/delete)
• One Boolean to say if undo was just done or not

Then just update these on each different operation. No stacks or anything are needed, because multiple undo/redo is not needed.