I tried to come out with a complicated solution, but they wanted the simplest one. A Hashmap and doubly linked list should satisfy them. Keep putting the recently accessed node on top of the queue and while inserting a new element, if its full, remove the last node in the queue.

why not use a minHeap?