← Alle AufgabenJavaScript · Senior

LRUCache

Schreib eine Klasse LRUCache(capacity): einen Cache, der bei vollem Speicher den Eintrag verdrängt, auf den am längsten nicht zugegriffen wurde.

get(key) liefert den Wert oder undefined und markiert den Schlüssel als kürzlich genutzt. put(key, value) fügt einen Wert hinzu oder aktualisiert ihn, was ebenfalls als Nutzung zählt. Die Eigenschaft size ist die aktuelle Zahl der Einträge. Beide Operationen müssen O(1) sein.

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

  get size() {
    // ...
  }

  get(key) {
    // ...
  }

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

Strg+Enter führt die Tests aus. Tab rückt ein; um den Editor per Tastatur zu verlassen, drücke Esc und dann Tab. Der Code wird in diesem Browser gespeichert.

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);