Interview Question for Senior Software Engineer at Google:

Use a hash map and a queue.

I think you can do better than hash map and a queue...or just simply it.

Since you're only interested in the N most recently accessed items, an array is suffice. Because N is essentially the index right?

To ml:

N was not the index, instead some random key. The combined data structure had the implement the interface:
      Object get(String key); and
      void put (String key, Object obj);

Besides the array isn't the best choice when you have to take an object out of the array and add it to the front of the queue every time the object is accessed. A double linked list works better. The hash map entries points to an item in the linked list, which then points to the object to be returned. This way you can find the item quickly to move it to the front of the queue.