Most LRU Caching algorithms consist of two parts: a dictionary and a list. The dictionary guarantees quick access to your data, and the list, ordered by age of the objects, controls the lifespan of objects and determines which objects are to be removed first. A simple LRU Cache implementation uses a doubly linked list; adding new items to the head, removing items from the tail, and moving any existing items to the head when referenced (touched).

I had telephone interview with Google. The interviewer asked me to develop java interfaces and it implementation of cache. My Answer was below public interface ServerCache{ public void storeCache(String keyOfObject,Object objectToStore); public Object getCachedObject(String keyOfObject); } public class ServerCacheImp implements ServerCache { LinkedList queue=new LinkedList(); Hashtable cacheStorage=null; public ServerCacheImpl() { cacheStorage=new Hashtable(); } public Object getCachedObject(String keyOfObject) { queue.remove(keyOfObject); queue.add(keyOfObject); return cacheStorage.get(keyOfObject); } public void storeCache(String keyOfObject,Object objectToStore) { String key=””; Object existingObj=cacheStorage.get(keyOfObject); if(cacheStorage.get(keyOfObject)!=null&&existingObj.equals(objectToStore)) { return; } if(queue.size()>1000) { key=(String)queue.remove(); cacheStorage.remove(key); } queue.add(keyOfObject); cacheStorage.put(keyOfObject,ObjectToStore); } }