Least Recently Used (LRU) Cache – Using LinkedHashSet and Deque | Set 2

Objective: Design and Implement a data structure Least Recently Used (LRU) Cache.

Earlier we had seen Least Recently Used (LRU) Cache – Using HashMap and Doubly Linked List. In this article we will see the implementation using LinkedHashSet and Deque.

Lets first brief about LRU-

Given a cache (or memory) with capacity. The cache will be filled with items you will access or look for it. The most recently accessed item will be at the top of the cache whereas least recently used cache will be at the end of the cache. As you will access the items, the cache will be filled as per the conditions below

  1. If item is not present in the cache and cache capacity is NOT REACHED then item will be added at top of the cache.
  2. If item is not present in the cache and cache capacity is REACHED then least recently item from cache will be removed (the last element in cache) and new item will be added at top of the cache.
  3. If item is already present in the cache then it will moved to the top of the cache.

Using LinkedHashSet and Deque:

Deque:  The Deque list will represent the cache and order. So each time item will be referred or looked or accessed, the item will be inserted into deque, if it is not already present. If cache is reached to its limit, means full then last item from the cache will be removed before new item is inserted.  If item is already present then it will moved to top of the cache (remove and add it again). Click here to read about Deque .

LinkedHashSet: Linked Hash Set will be used to check if item is present in the cache in O(1) time. Deque operations take O(N) time.

See the image below for more understanding.

Complete Code:

Output:

Looking for key: 1
Cache: 1 
Looking for key: 2
Cache: 2 1 
Looking for key: 1
Cache: 1 2 
Looking for key: 3
Cache: 3 1 2 
Looking for key: 4
Cache: 4 3 1 2 
Looking for key: 3
Cache: 3 4 1 2 
Looking for key: 5
Cache: 5 3 4 1 
Looking for key: 4
Cache: 4 5 3 1 
Looking for key: 6
Cache: 6 4 5 3

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: