The following snippet of code defines the Recorder interface. The recorder ADT is used to keep of various objects - it is a method of tagging. For example, one might need to keep track of which instant messages (objects) have been displayed to the user. This could be represented by adding items to a Recorder, with the Recorder offering additional functionality to check if a messages was displayed (contained), or undo adding the last element (e.g., window closed before read by user). public interface Recorder {void add(Item item);//add an item Boolean contains (Item item)//is item in the collection? void undo();//removes the last item added.} Give an implementation of Recorder that allows the addition of elements in O(1), query of elements in O(n) time, and removing elements in O(1) time