Реализуйте LRU-кэш заданной ёмкости: get(key) возвращает значение или -1, put(key, value) добавляет пару и вытесняет самый давно не использованный элемент при переполнении. Обе операции — за O(1).

Основной ответ

Требование O(1) на get и put диктует комбинацию структур. Хэш-таблица отображает ключ в узел двусвязного списка; список упорядочен по свежести: голова — недавно использованные, хвост — кандидат на вытеснение. Get: найти узел через словарь, отцепить и перенести в голову, вернуть значение. Put: если ключ есть — обновить значение и перенести в голову; если нет — создать узел в голове, а при превышении ёмкости удалить хвостовой узел и его ключ из словаря. Двусвязность списка обязательна: для отцепления узла за O(1) нужна ссылка на предыдущий. Фиктивные граничные узлы head/tail избавляют от проверок на пустоту. В Python OrderedDict с move_to_end и popitem(last=False) реализует ровно это.

Ключевые моменты

• Почему две структуры. Словарь не упорядочен, список не ищет за O(1); словарь со ссылками на узлы списка объединяет оба свойства.
• Двусвязность. Удалить узел из середины за O(1) можно, только зная его prev — односвязный список потребовал бы поиска за O(n).
• Get тоже двигает. Чтение — это использование: get обязан переносить узел в голову, иначе вытеснение выберет не того.
• Sentinel-узлы. Фиктивные head и tail делают вставку и удаление единообразными — нет веток для пустого кэша и крайних узлов.

Практический контекст

Классика раундов design-coding: проверяется выбор структур данных под заданные сложности и аккуратность с указателями при самостоятельной реализации списка. Спросите, можно ли использовать OrderedDict/LinkedHashMap или нужна реализация с нуля. Будьте готовы к развитиям: потокобезопасность (мьютекс вокруг операций), TTL для записей, LFU-вытеснение как усложнение.

Пример кода

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.data = OrderedDict()  # порядок: от давнего к свежему

    def get(self, key):
        if key not in self.data:
            return -1
        self.data.move_to_end(key)  # пометить как свежий
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.cap:
            self.data.popitem(last=False)  # вытеснить давний

c = LRUCache(2)
c.put(1, 1); c.put(2, 2)
assert c.get(1) == 1
c.put(3, 3)  # вытесняет ключ 2
assert c.get(2) == -1 and c.get(3) == 3

Частые ошибки

• Забывают, что get тоже должен обновлять порядок — вытесняется недавно прочитанный элемент
• Берут односвязный список и получают O(n) на удаление узла из середины
• При вытеснении удаляют узел из списка, но забывают удалить ключ из словаря — утечка и рассинхрон