Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

put(key, value)– Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:

Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // evicts key 2 cache.get(2); // returns -1 (not found) cache.put(4, 4); // evicts key 1 cache.get(1); // returns -1 (not found) cache.get(3); // returns 3 cache.get(4); // returns 4

Solution

In LRU Cache, We always dealing with two main functions, 1. Fast Lookup 2.Delete Least Recent Used Element.

To do fast lookup we can use any of the Hash based collection, like HashSet or HashMap, and Linkedlist is best for the element deletion.

With the help of HashMap and LinkedList, we can create LRU cache which can perform both the operations in O(1) time complexity.

Code

Output

1 -1 -1 3 4

We encourage you to write a comment if you have a better solution or having any doubt on the above topic.

Leave a Reply

Your email address will not be published. Required fields are marked *