← All tasksJavaScript · Senior

LRUCache

Write a class LRUCache(capacity): a cache that, when full, evicts the entry that hasn't been accessed for the longest time.

get(key) returns the value or undefined and marks the key as recently used. put(key, value) adds or updates a value, which also counts as a use. The size property is the current number of entries. Both operations must be O(1).

class LRUCache {
  constructor(capacity) {
    // ...
  }

  get size() {
    // ...
  }

  get(key) {
    // ...
  }

  put(key, value) {
    // ...
  }
}

Ctrl+Enter runs the tests. Tab indents; to leave the editor with the keyboard, press Esc and then Tab. Your code is saved in this browser.

Tests (5)

const c = new LRUCache(2);
c.put('a', 1);
c.put('b', 2);
expect(c.get('a')).toBe(1);
c.put('c', 3);
expect(c.get('b')).toBe(undefined);
expect(c.get('a')).toBe(1);
expect(c.get('c')).toBe(3);

const c = new LRUCache(2);
c.put('a', 1);
c.put('a', 10);
c.put('b', 2);
expect(c.size).toBe(2);
expect(c.get('a')).toBe(10);

const c = new LRUCache(2);
c.put('a', 1);
c.put('b', 2);
c.put('a', 3);
c.put('c', 4);
expect(c.get('b')).toBe(undefined);
expect(c.get('a')).toBe(3);

const c = new LRUCache(1);
c.put('x', 0);
expect(c.get('x')).toBe(0);
c.put('y', null);
expect(c.get('x')).toBe(undefined);
expect(c.get('y')).toBe(null);

const c = new LRUCache(3);
expect(c.get('missing')).toBe(undefined);
expect(c.size).toBe(0);