Как устроен LRU кэш и какими структурами данных реализовать его логику

Что проверяют

Умеете ли вы получить O(1) и на чтение, и на вставку с вытеснением, и понимаете ли, зачем для этого две структуры. Для Python следом почти всегда спрашивают про functools.lru_cache и OrderedDict: что вы возьмёте в реальном коде.

Как отвечать

LRU вытесняет элемент, к которому дольше всех не обращались. Каркас ответа:

• словарь: ключ ведёт к узлу, проверка и доступ за O(1);
• двусвязный список: хранит порядок использования. При get узел переносится в голову, при переполнении удаляется хвост. Список двусвязный, потому что вырезать узел из середины за O(1) можно, только зная его предыдущий элемент;
• ключ в узле: при вытеснении хвоста нужно удалить и запись из словаря, а для этого узел должен помнить свой ключ;
• фиктивные голова и хвост: избавляют от проверок на None на краях списка.

В Python ту же логику даёт collections.OrderedDict: move_to_end(key) при обращении и popitem(last=False) для вытеснения самого старого, оба за O(1). Обычный dict с версии 3.7 тоже хранит порядок вставки, и LRU на нём делается через pop и повторную вставку, но OrderedDict выражает намерение яснее.

Для кеширования функций есть готовый @functools.lru_cache(maxsize=128): 128 это значение по умолчанию, maxsize=None снимает лимит (то же, что functools.cache). Методы cache_info() и cache_clear() помогают в отладке и тестах. Внутренняя структура кеша потокобезопасна, но при гонке функция может выполниться дважды для одного ключа.

Где спотыкаются

Берут list для порядка и вызывают remove. Это O(n), и весь смысл конструкции теряется.

Вешают lru_cache на метод класса. Кеш держит ссылку на self в ключе, экземпляры не освобождаются, получается утечка памяти. Для методов без аргументов подходит functools.cached_property, для остальных кеш на уровне экземпляра.

Забывают, что аргументы должны быть хешируемыми, а закешированный изменяемый результат общий для всех вызовов: поправили возвращённый список, и следующий вызов вернёт уже изменённые данные.