← Wszystkie zadaniaJavaScript · Senior

LRUCache

Napisz klasę LRUCache(capacity) - cache, który po przepełnieniu usuwa element, do którego najdłużej nie było odwołania.

get(key) zwraca wartość lub undefined i oznacza klucz jako ostatnio użyty. put(key, value) dodaje lub aktualizuje wartość; to też jest użycie. Właściwość size to bieżąca liczba elementów. Obie operacje mają działać w O(1).

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

  get size() {
    // ...
  }

  get(key) {
    // ...
  }

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

Ctrl+Enter uruchamia testy. Tab robi wcięcie; aby wyjść z edytora klawiaturą, naciśnij Esc, a potem Tab. Kod zapisuje się w tej przeglądarce.

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