You have to design a LRU cache such that all operations can be done in O(1) – read, write and insert.

• In case, cache is full, you have to remove an element which was read/written last.
• Each read should update the timestamp of these elements.
• Read request of the element contains a key which is not the location of the element.

Strategy:

Assuming hashmap has retrieval complexity of O(1), we can do this using a doubly link list and a Hashmap

• Doubly link list will be used to store indexes sorted by date/timestamp information.
• Keep track of first and last node.
• No sorting effort is needed as each new node will have latest timestamp.
• The Hashmap will retrieve the node searched by key. It will also contain pointer to its respective doubly link list node.

• Search the node by key. Retrieve the node value and index for doubly linklist.
• Delete the node from doubly linked list and add it with the updated date value at the starting of the list.
• Complexity of deleting a node in doubly link list is O(1) as we can reach to it without traversing the list.

INSERT -

• Add the new node in the hashmap and the doubly linked list.
• If the cache is full, use the pointer to the last node in the doubly linked list and delete that node. Set the delete pointer appropriately.
• Inserting at the start of linked list is operation with time O(1).

UPDATE -

• Update operation will need similar operation as READ in terms of accessing the data structure. Hence, similar time complexities apply.

DELETE -

• Deleting the node from the doubly-linked list and hashmap can be done in O(1).

Implementation:

Queue with DLL + HashMap

`   1: struct LRUCacheNode {`

`   2:         int key;`

`   3:         int value;`

`   4:         LRUCacheNode* prev;`

`   5:         LRUCacheNode* next;`

`   6:         LRUCacheNode(): key(0),value(0),next(NULL),prev(NULL) { } ;`

`   7: } ;`

`   8:`

`   9: class LRUCache{`

`  10: private:`

`  11:     hash_map< int, LRUCacheNode* >  Map;`

`  12:     LRUCacheNode *  Head;`

`  13:     LRUCacheNode *  Tail;`

`  14:     int Capacity ;`

`  15:     int Count ;`

`  16:`

`  17: public:`

`  18:     LRUCache(int capacity) {`

`  19:         Capacity = capacity ;`

`  20:         Count = 0 ;`

`  21:         Head = new LRUCacheNode;`

`  22:         Tail = new LRUCacheNode;`

`  23:         Head->prev = NULL;`

`  24:         Head->next = Tail;`

`  25:         Tail->next = NULL;`

`  26:         Tail->prev = Head;`

`  27:     }`

`  28:`

`  29:     ~LRUCache ( ) {`

`  30:         delete Head;`

`  31:         delete Tail;`

`  32:     }`

`  33:`

`  34:     int get(int key) {`

`  35:         LRUCacheNode* node = Map[key];`

`  36:         if(node)`

`  37:         {`

`  38:             DetachNode(node);`

`  39:             AttachNodeToFront(node);`

`  40:             return node->value;`

`  41:         }`

`  42:         else`

`  43:         return -1 ;`

`  44:`

`  45:     }`

`  46:`

`  47:     void set(int key, int value) {`

`  48:         LRUCacheNode* node = Map[key];`

`  49:         if(node)`

`  50:         {`

`  51:             DetachNode(node);`

`  52:             node->value = value;`

`  53:             AttachNodeToFront(node);`

`  54:         }`

`  55:         else{`

`  56:             LRUCacheNode* node = new LRUCacheNode ;`

`  57:             if ( Capacity == Count ) { // If Cache is Full`

`  58:                 RemoveLRUNode ( key ) ;`

`  59:             }`

`  60:`

`  61:             node->key = key;`

`  62:             node->value = value;`

`  63:             Map[key] = node;`

`  64:             AttachNodeToFront(node);`

`  65:             Count++ ;`

`  66:         }`

`  67:     }`

`  68: private:`

`  69:     void RemoveLRUNode ( int key ) {`

`  70:         LRUCacheNode* node = Tail->prev;`

`  71:         DetachNode(node);`

`  72:         Map.erase(node->key);`

`  73:         Count-- ;`

`  74:     }`

`  75:`

`  76:     void DetachNode(LRUCacheNode* node) {`

`  77:             node->prev->next = node->next;`

`  78:             node->next->prev = node->prev;`

`  79:     }`

`  80:`

`  81:     void AttachNodeToFront(LRUCacheNode* node) {`

`  82:             node->next = Head->next;`

`  83:             node->prev = Head;`

`  84:             Head->next = node;`

`  85:             node->next->prev = node;`

`  86:     }`

`  87: };`