LeetCode - 146. LRU Cache

What is LRU Cache?

LRU means Least Recently Used. LRU Cache is an algorithm for storing a fixed number of items and removing the least recently used item when the cache is full. The time complexity for get and put operation will be O(1).

Example

capacity: 2

new LRUCache(2) (initizlize LRU Cache with capacity 2)
get(1) -> -1 (cache: {})
put(1, 1) -> null (cache: {1: 1})
put(2, 2) -> null (cache: {1: 1, 2: 2})
get(1) -> 1 (cache: {2: 2, 1: 1})
put(3, 3) -> null (cache: {1: 1, 3: 3})
get(2) -> -1 (cache: {1: 1, 3: 3})

Thoughts:

Because I need a data structure that is capable of storing key-value pairs and memorizing the order of the pairs. I think Map is a good choice for this problem. And I can remove and set the pair for implementing the most recently used feature.

Code:

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key) {
    if (this.cache.has(key)) {
      const value = this.cache.get(key);
      this.cache.delete(key);
      this.cache.set(key, value);
      return value;
    }
    return -1;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      const leastRecentlyUsed = this.cache.keys().next().value;
      this.cache.delete(leastRecentlyUsed);
    }
    this.cache.set(key, value);
  }
}

Reference

Original link

What is LRU Cache