LRU cache

Hard TimeO(1) per op SpaceO(capacity)

Build a cache holding a fixed capacity of entries which, when full, throws away whichever key has gone longest without being touched. Reading counts as touching, not only writing, and writing an existing key updates it rather than adding a second copy. Both get and put have to run in constant time, which rules out scanning for the oldest entry, and a missing key reads as -1.

Examples

Example 1

Input: demo()
Output: [100,-1,300]
1 and 2 are stored; reading 1 leaves 2 the oldest, so storing 3 evicts it and get(2) is -1.

Example 2

Input: makeLRUCache(2).get(9)
Output: -1
Nothing has been stored yet, so key 9 is missing and reads as -1.

The Code

function makeLRUCache(capacity) {
  const map = new Map();
  return {
    get(key) {
      if (!map.has(key)) return -1;
      const value = map.get(key);
      map.delete(key);
      map.set(key, value);
      return value;
    },
    put(key, value) {
      if (map.has(key)) {
        map.delete(key);
      } else if (map.size >= capacity) {
        const oldest = map.keys().next().value;
        map.delete(oldest);
      }
      map.set(key, value);
      return map.size;
    }
  };
}
function demo() {
  const cache = makeLRUCache(2);
  cache.put(1, 100);
  cache.put(2, 200);
  const first = cache.get(1);
  cache.put(3, 300);
  return [first, cache.get(2), cache.get(3)];
}
demo();

Done

Step through demo() call by call

More like this

All linked lists examples (9) →