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.

READ -

  • 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: };