Category Archives: Hash

Implement LRU (Least Recently Used) Cache using Queue and Hash

Problem :

Implement LRU (Least Recently Used) Cache using Queue and Hash
The task is to design and implement methods of an LRU cache. The class has two methods get and set which are defined as follows.

get(x) : Gets the value of the key x if the key exists in the cache otherwise returns -1
set(x,y) : inserts the value if the key x is not already present. If the cache reaches its capacity it should invalidate the least recently used value before inserting the new value. In the constructor of the class the size of the cache should be intitialized.

Solution :

– LRU can be implemented in various ways like using priority queue etc .
– Here is we will implement by using Queue (implemented on DLL) and hashMap bacause we are solving hash questions
– – For this we maintain hashmap key will be key and value will be corresponding queue node, it provide direct access of node.

Latest Source Code:


 Front[], Rear[]
Front[Mishra,Kumar,hrishikesh], Rear[hrishikesh,Kumar,Mishra]
Front[Kumar,Mishra,hrishikesh], Rear[hrishikesh,Mishra,Kumar]
Front[India,Kumar,Mishra,hrishikesh], Rear[hrishikesh,Mishra,Kumar,India]
Front[Programming,India,Kumar,Mishra], Rear[Mishra,Kumar,India,Programming]
Front[java,Programming,India,Kumar], Rear[Kumar,India,Programming,java]
Front[Kumar,java,Programming,India], Rear[India,Programming,java,Kumar]
Front[Kumar,java,Programming,India], Rear[India,Programming,java,Kumar]