15. LRU-кэш карточек товаров Wildberries

Приложение Wildberries кэширует открытые карточки товаров, чтобы кнопка «Назад» показывала их мгновенно. Памяти на телефоне мало — храним не больше capacity карточек.

Напишите класс LRUCache: new LRUCache(capacity), get(key) — значение или undefined, put(key, value) — записать. И get, и put делают запись самой свежей. Если после put записей больше capacity, удаляется самая давняя. Обе операции — O(1).

В работе: Кэш карточек и картинок, история навигации, кэш запросов в SPA.

Пример 1: get освежает запись

2, [["put", "p1", "кроссовки"], ["put", "p2", "куртка"], ["get", "p1"], ["put", "p3", "шапка"], ["get", "p2"], ["get", "p1"], ["get", "p3"]]

["кроссовки", null, "кроссовки", "шапка"]

Пример 2: put существующего освежает

2, [["put", "a", 1], ["put", "b", 2], ["put", "a", 10], ["put", "c", 3], ["get", "b"], ["get", "a"]]

[null, 10]

class LRUCache { constructor(capacity); get(key); put(key, value) }

Источник: на задачах Wildberries: карточки товаров. Условие пересказано своими словами.