CareerCup

O(1) insert, delete search
Implementation is easy. Just each entry of the hashTable shall have a links to the next and prev entry. So whenever accessed the entry you just move it to the head of the LinkedList like entries. If you want to add a max count of the elements in cache just whenever new node added remove the last one from the LinkedList like entries. Here is a very simple java implementation using the built in LinkedHashTable :

public class SimpleCache<E> {
 	LinkedHashMap<String, E> cache;
 
 	@SuppressWarnings("serial")
 	public SimpleCache(final int maxSize) {
 		cache = new LinkedHashMap<String, E>(maxSize, 0.75f, true) {
 			@Override
 			protected boolean removeEldestEntry(Map.Entry<String, E> eldest) {
 				return size() > maxSize;
 			}
 		};
 	}
 
 	public synchronized void add(String key, E value) {
 		cache.put(key, value);
 	}
 
 	public synchronized E get(String key) {
 		E result = cache.get(key);
 
 		if (result != null)
 			return (E) result;
 		else
 			return null;
 	}
 }

#include <iostream>
#include <vector>
#include <hash_map>
 
using namespace std;
 
template <class K, class T>
struct LRUCacheEntry
{
   K key;
   T data;
   LRUCacheEntry * prev;
   LRUCacheEntry * next;
};
 
template <class K, class T>
class LRUCache
{
public:
  LRUCache(size_t sz) : head(NULL), tail(NULL){
    entries = new LRUCacheEntry<K, T>[sz];
    for (int i = 0; i < sz; i++)
      freeEntries.push_back(entries + i);
  }
   
  ~LRUCache(){  delete[] entries; } 
 
  bool containsKey(K key) { return _m.find(key) != _m.end(); }
 
  void put(K key, T data){
    LRUCacheEntry<K, T> * entry;
     
    if (_m.find(key) != _m.end()) return;
 
    if (freeEntries.size() > 0){
      entry = freeEntries.back();
      freeEntries.pop_back();
    }
    else{
      // no free entries
      entry = tail;
      if (tail->prev != NULL) tail->prev->next = NULL;
      _m.erase(entry->key);
    }
      
    _m[key] = entry;
    entry->key = key;
    entry->data = data;
    entry->next = head; 
    entry->prev = NULL;
    if (head != NULL){
      head->prev = entry;
    }
      
    head = entry;
  }
 
  // we assumes that containsKey is always called before this method
  T get(K key) {  
    LRUCacheEntry<K, T> * entry = _m[key];
   
   if (entry != head){
      if (entry->next != NULL)
      entry->next->prev = entry->prev;
 
      entry->prev->next = entry->next;
      if (entry == tail) tail = entry->prev;
 
      entry->next = head;
      entry->prev = NULL;
      head = entry;
    }
 
    return entry->data;
  }
 
  void print(){
    LRUCacheEntry<K, T> * entry = head;
    while (entry != NULL){
      cout << entry->data << " ";
      entry = entry->next;
    }
    cout << endl;
  }
private:
  hash_map<K, LRUCacheEntry<K, T> *> _m;
  LRUCacheEntry<K, T> * head, *tail, *entries;
  vector<LRUCacheEntry<K, T> *> freeEntries;
};
 
 
 
int main()
{
  LRUCache<int, int>  cache(3);
 
  cache.put(3, 3);
  cache.put(4, 4);
  cache.put(5, 5);
    
  cache.print();
 
  cache.get(3);
  cache.print();
  return 0;

}

Why not use only min-heap where pages with least recently used can be extracting the head of the min-heap. Heap will be formed based on the time of use. Say we use a variable clock which represents the time of use. A new page will be inserted in logn time.
I don't see any use of hash-map there.

Why minheap ? Java has a different way of implementing LinkedHashMap using a hashmap and a doubly linked list. The key to age an entry is to when its used, we add it to the head and keep removing entries from the tail (which will hold the oldest entries)

How about a circular linked list where the head will be the one with least recently used.