LeetCode: LRU Cache

Challenge Description

Design and implement a data structure for 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

For quick query operation, it’s easy to figure out to use map to store key and value.

How we could keep which node is least recently used node?

file:img/CAPTURE-2020_02_05_leetcode-lru-cache.org_20200206_125019.png

A clever approach is using double-linked-list, whenever we visiting a node, move the node to head. The least recently visited node is the tail of link list.

Another trivial optimization in my code is, when the cache is full, we use the in-place policy to set the least recently used node’s value to new value.

file:img/CAPTURE-2020_02_05_leetcode-lru-cache.org_20200206_122541.png

#include <unordered_map>
using namespace std;

struct LRUNode {
  int key, val;
  LRUNode *prev, *next;
  LRUNode(int k, int v) : key(k), val(v), prev(NULL), next(NULL) {}
};

class LRUCache {
private:
  size_t capaty;
  LRUNode* lruList;
  unordered_map<int, LRUNode*> table;

  void set_head(LRUNode* node) {
    node->next = lruList;
    node->prev = lruList->prev;
    lruList->prev->next = node;
    lruList->prev = node;
    lruList = node;
  }

  void visit(LRUNode* node) {
    if(lruList != node) {
      node->prev->next = node->next;
      node->next->prev = node->prev;
      set_head(node);
    }
  }

  void add(LRUNode* node) {
    if(lruList == NULL) {
      lruList = node;
      node->next = node;
      node->prev = node;
    } else set_head(node);
  }

  LRUNode* get_and_visit(int key) {
    unordered_map<int, LRUNode*>::iterator it = table.find(key);
    if(it != table.end()) visit(it->second);
    return it != table.end() ? it->second : NULL;
  }

public:
  LRUCache(int capacity) : capaty(capacity), lruList(NULL) { }

  ~LRUCache() {
    LRUNode* p = lruList;
    LRUNode* t = p;
    LRUNode* n = NULL;
    while(t) {
      n = t->next;
      delete t;
      if(n == p) break;
      t = n;
    }
  }

  int get(int key) {
    LRUNode* n = get_and_visit(key);
    return n == NULL ? -1 : n->val;
  }

  void put(int key, int value) {
    LRUNode* node = get_and_visit(key);
    if(node != NULL)
      node->val = value;
    else if(table.size() < capaty) {
      // allocate new node
      node = new LRUNode(key, value);
      table[key] = node;
      add(node);
    } else {
      // use in-place policy, replace lru-node wit new key and value.
      node = lruList->prev;
      table.erase(node->key);
      node->key = key;
      node->val = value;
      table[key] = node;
      visit(node);
    }
  }
};

Preparing for an interview? Checkout this!

Join my Email List for more insights, It's Free!😋

← LeetCode: Majority Element LeetCode: Pow(x, n) →