I have an array of unique integers (say {1,2,4, 5,3}), and I randomly choose one of the integers. I want to keep track of which integer has the oldest chosen time, e.g. if I choose {1, 2, 4, 3, 2, 1, 5} I want the oldest value to be 4.

I am wondering if there is a way to accomplish this with O(1) time, and potentially O(n) memory size depending on the size of the array. I don't want to have to iterate the array to determine which one was the oldest value.

no iteration and no hashing
How many potential integers are there?
Merth and I devised a couple of reasonable solutions in SAX, I'll present them here a little more thoroughly. The general idea is similar to an LRU cache: pair a data structure that is good at ordering but bad at indexing with a data structure that is good at indexing but bad at ordering.

Let's define some notation for this problem. Your input array of integers is A, and i is the index of the element you just visited.

I'll present two equivalent solutions here. The first uses more storage but is more explicit. The second uses less storage but is a little more opaque.
Solution 1
Our first data structure is a doubly linked list, complete with start and end pointers. The invariant we'll maintain in this list is "if node A comes before node B, then A was used less recently than B".
Our second data structure is an array containing pointers. This array has the same size n as the input array of integers, and the ith element is a pointer to the linked list node holding the ith element.

To visit an element of the input array, we move it to the back of the linked list. We can then retrieve the most recently visited element, remove it from the doubly linked list, and add it back to the end. Effectively, this is removing an element from a stack and pushing it back on top. The bottom of the stack is the least recently visited element. We use a Doubly Linked List to implement our stack for the O(1) operations.

From SAX: (not rewriting this Razz)
I wrote:
call our doubly linked list DLL and our array map AM. When accessing element with index i, retrieve a pointer to its DLL node by accessing AM[i]. Then, we move this DLL node (call it DLL_i) to the end of the doubly linked list. Update DLL_i's predecessor to point to its successor and its successor to point to its predecessor. If DLL_i's predecessor was null, then its successor is the new head of the DLL & is also the least recently used element. Update the old last element of the DLL to have DLL_i as its successor (also update DLL_i to have the old last element as its predecessor) and update DLL_i to have no successor. Return the head of the DLL as the least recently used element
.

Solution 2
We don't actually need to use that many pointers. We can store the predecessors and successors in separate arrays, each indexed in the same way as AM. predecessors[i] would then give the unique index i' such that node i' has node i as a successor.

This solution uses more or less the same update logic as the first solution.
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Page 1 of 1
» All times are UTC - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement