Реализуйте LRU-кэш на N элементов, в котором get и put работают за O(1)

ЗадачаSeniorИногда

Проверила команда СопроводОбновлено

Короткий ответ

Храните данные в OrderedDict: он помнит порядок ключей и переносит ключ в конец за O(1). В get при попадании вызывайте move_to_end(key), чтобы ключ стал самым свежим. В put записывайте значение, переносите ключ в конец и, если элементов стало больше N, удаляйте самый давний через popitem(last=False). Без OrderedDict то же дают словарь и двусвязный список.

Почему этот вопрос задают

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

Условие задачи

Сервис аптечной сети показывает карточки препаратов и держит в памяти кэш на N карточек. Реализуйте класс LRUCache(capacity) с методами get(key) и put(key, value), оба за O(1). get возвращает карточку или None, если ее нет. При переполнении put вытесняет карточку, к которой дольше всех не обращались. Проверьте класс на емкости 2 и шести операциях из таблицы.

ШагОперацияОжидаемый результат
1put(101, Парацетамол 500 мг)в кэше 101
2put(102, Ибупрофен 200 мг)в кэше 101 и 102
3get(101)Парацетамол 500 мг
4put(103, Цетиризин 10 мг)вытеснен 102
5get(102)None
6get(101)Парацетамол 500 мг

Как подойти к решению

  1. Возьмите OrderedDict: порядок ключей в нем и будет порядком свежести
  2. Переносите ключ в конец через move_to_end при каждом чтении и записи
  3. Удаляйте первый ключ через popitem(last=False), когда размер превысил емкость
  4. Проверьте сценарий, где get спасает ключ от вытеснения

Решение

Шаг 3 освежил ключ 101, поэтому на шаге 4 вытеснен 102, и get(102) вернул None. В конце в кэше 103 и 101, самый свежий справа. Поиск по хешу, перенос в конец и удаление с начала у OrderedDict идут за O(1), память O(N).

Python
class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()
    def get(self, key):
        if key in self.data:
            self.data.move_to_end(key)
        return self.data.get(key)
    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)

cache = LRUCache(2)
cache.put(101, "Парацетамол 500 мг")
cache.put(102, "Ибупрофен 200 мг")
print(cache.get(101))
cache.put(103, "Цетиризин 10 мг")
print(cache.get(102), cache.get(101), list(cache.data))
Вывод
Парацетамол 500 мг
None Парацетамол 500 мг [103, 101]

Что спросят следом

  • Как сделать такой кэш без OrderedDict?

  • Что изменится, если кэшем пользуются несколько потоков?

  • Почему бы не взять functools.lru_cache?

Доступно по подписке

Ответы на эти вопросы

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

  • «get только читает, порядок трогать не нужно»

    Чтение и есть использование. Без move_to_end в get кэш вытеснит самую популярную карточку, как только она окажется первой по времени записи

  • «Удалю самый давний ключ через popitem()»

    Без аргумента popitem у OrderedDict удаляет последний, самый свежий ключ. Передайте last=False, чтобы удалить первый

  • «Обычный dict с Python 3.7 тоже хранит порядок, возьму его»

    Порядок вставки он хранит, но метода move_to_end у него нет: перенос пишут как d[key] = d.pop(key), первый ключ берут через next(iter(d)). Это работает, и все же OrderedDict выражает намерение явно

  • «put существующего ключа просто перезапишет значение»

    Перезапись должна еще и освежить ключ. Вызывайте move_to_end после записи в обоих случаях, тогда одна ветка кода покрывает и новый, и существующий ключ

Сигналы для интервьюера

Сильный ответ

Уточняет, считать ли емкость в карточках или в байтах, а после решения сам спрашивает, будут ли кэшем пользоваться несколько потоков

Тревожный сигнал

Хранит порядок в обычном списке ключей и удаляет из него через remove, не замечая, что это O(N)

Красный флаг

Предлагает при каждом get пересортировать все ключи по времени обращения и при этом называет такое решение O(1)

Как еще могут спросить

  • Как реализовать LRU cache на Python?
  • Напишите кэш, который вытесняет давно не используемые элементы
  • Какую структуру данных взять для LRU-кэша, чтобы операции шли за O(1)?
  • Реализуйте класс LRUCache с методами get и put

Похожие вопросы

ЗнаниеMiddleЧасто

Как устроен словарь в Python и почему ключом не может быть список?

Словарь — хеш-таблица. По hash(key) Python выбирает ячейку, а совпадение подтверждает через хеш и ==. Поэтому ключ обязан быть хешируемым, и его хеш не должен меняться, пока ключ лежит в словаре. У изменяемого list нет __hash__, и вставка падает с TypeError. Поиск, вставка и удаление в среднем занимают O(1).

  • Python
  • словари
280
ЗнаниеJuniorЧасто

Что такое декоратор в Python и зачем внутри него functools.wraps?

Декоратор — функция, которая принимает функцию и возвращает новую, обычно обертку с дополнительной логикой: проверкой прав, логированием, кэшем. Запись @admin_only над def edit_catalog означает edit_catalog = admin_only(edit_catalog). Обертка подменяет исходную функцию, и без functools.wraps теряются ее __name__ и __doc__. wraps копирует их на обертку и сохраняет ссылку на оригинал.

  • Python
  • функции
294
ЗадачаMiddleЧасто

Напишите класс денежной суммы, который можно складывать, сравнивать и использовать как ключ словаря

Сделайте класс неизменяемым и храните сумму целым числом копеек вместе с кодом валюты: @dataclass(frozen=True) сам создаст __eq__ и согласованный с ним __hash__. Сложение напишите в __add__: для чужого типа верните NotImplemented, для разных валют бросьте ValueError. Если пишете __eq__ руками, добавьте __hash__ по тем же полям, иначе объект нельзя положить в множество.

  • Python
  • ООП
  • магические методы
222
ЗадачаMiddleЧасто

Напишите генератор, который развернет список любой вложенности в плоскую последовательность

Пройдите по элементам списка: если элемент сам список или кортеж, передайте его в тот же генератор через yield from, иначе отдайте элемент через yield. Пустые списки ничего не отдадут и пропадут сами. Строку не проверяйте вопросом «итерируема ли она»: она состоит из строк и уведет рекурсию в бесконечность. Память растет с глубиной вложенности, а не с длиной списка.

  • Python
  • генераторы
  • рекурсия
219

Частые вопросы по теме

Короткие ответы на частые вопросы по этой теме.

Да, и скажите почему: документация прямо называет его подходящим для LRU-кэшей. Будьте готовы, что интервьюер попросит версию без него. Начните с готового класса, чтобы быстро показать рабочее решение, и оставьте время на вторую версию.

Емкость 0, запись существующего ключа, get отсутствующего ключа, значение None в самом кэше. Последний случай коварный: get вернет None и для промаха, и для сохраненного None, поэтому для промаха лучше вернуть отдельный маркер или бросить KeyError.

В кэше страниц базы данных, в functools.lru_cache, в кэшах шаблонов и миниатюр. Чаще всего на работе берут готовое решение, например Redis с политикой allkeys-lru. Своя реализация нужна, когда кэш живет внутри процесса и важна предсказуемая память.

Общие вопросы на интервью

Общий вопросС опытомЧасто

Почему вы хотите работать у нас?

Назовите две-три причины, которые связывают вас именно с этой компанией: продукт, задачи, масштаб, команда. Каждую подкрепите фактом, который нашли сами: новость, проект, текст вакансии, свой опыт клиента. Потом покажите, что принесете со своей стороны. Слова о стабильности и известном бренде подходят любой компании, поэтому на них ответ не держится.

  • мотивация
  • о компании
290
Общий вопросБез опытаЧасто

Какие у вас сильные стороны?

Хватит двух-трех сильных сторон, которые нужны на этой работе, если к каждой есть пример: что сделали и какой был результат. Берите качества из текста вакансии, а не из списка «ответственный, коммуникабельный». Без опыта примеры ищите в учебе, практике и подработке. Говорите спокойно, без лишней скромности и без хвастовства.

  • сильные стороны
  • без опыта
276
Общий вопросБез опытаЧасто

Кем вы видите себя через 5 лет?

Расскажите, какие задачи хотите решать через несколько лет и чему для этого научитесь. Свяжите план с тем, что дает эта компания, и покажите первый шаг, который уже сделали. Точную должность называть не обязательно. Важнее, чтобы план был реальным и вел через эту работу, а не мимо нее.

  • мотивация
  • карьерные планы
289
ИсторияС опытомЧасто

Расскажите о конфликте с коллегой: из-за чего он возник и как вы его решили?

Расскажите один реальный конфликт по рабочему вопросу: из-за чего разошлись, чего хотела каждая сторона и как вы договорились. Говорите спокойно, без оценок коллеги. Покажите, что вы искали решение, где-то уступили и сохранили рабочие отношения. Закончите результатом и тем, что теперь делаете, чтобы похожий спор не повторился.

  • конфликты
  • работа в команде
252
ИсторияС опытомЧасто

Каким профессиональным достижением вы гордитесь больше всего?

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

  • достижения
  • результат в цифрах
276
Общий вопросБез опытаЧасто

Опыта работы еще нет, а интервьюер просит рассказать о себе: что вы скажете?

Начните с того, кто вы сейчас и на какую работу пришли. Вместо стажа расскажите об учебе, практике и подработке, которые похожи на задачи вакансии, и назовите один результат с цифрой. Закончите тем, почему хотите начать карьеру именно здесь. Уложитесь в одну-две минуты и не пересказывайте резюме по порядку.

  • о себе
  • без опыта
244

Вопросы руководителю на интервью

ИсторияРуководительЧасто

Как вы делегируете задачи: что отдаете команде, а что оставляете себе?

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

  • делегирование
  • команда
255
КейсРуководительЧасто

Два сотрудника вашей команды месяц не разговаривают друг с другом, и общий отчет уже сорвал срок — что сделаете?

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

  • конфликт
  • ответственность
242
ИсторияРуководительЧасто

Расскажите о сотруднике, которого вы вырастили: каким он пришел и чего добился?

Возьмите одного человека и покажите путь: каким он пришел, какие задачи вы ему давали по нарастающей и чем помогали, кем он стал и за какой срок. Назовите цифру роста: новая должность, своя зона, люди в подчинении. Скажите честно, где он вырос сам, а где сработали ваши решения.

  • развитие сотрудников
  • наставничество
303
ИсторияРуководительЧасто

Расскажите о цели, которую ваша команда не выполнила: когда вы это поняли и что сделали?

Назовите цель с цифрой и честный итог. Главное в ответе — момент, когда вы поняли, что цель срывается, и по какой цифре это увидели. Дальше расскажите, кому и когда сказали, что пересобрали, чтобы спасти главное, и какой один вывод сделали для следующего плана.

  • цели
  • провал
241
Общий вопросРуководительЧасто

Как вы измеряете результат своей команды?

Назовите два-три показателя, которые отражают то, ради чего существует ваша команда, и их текущие цифры. Добавьте показатель качества, который не дает гнаться за одним числом. Скажите, как часто смотрите на цифры, кто их видит и какое решение вы приняли по ним в последний раз.

  • показатели
  • цели
216
ИсторияРуководительЧасто

Расскажите, как вы разложили цель компании на задачи для своей команды

Возьмите одну цель компании с цифрой и сроком и покажите, как вы ее разбили: на какие части, по какому признаку, какие личные цели получил каждый сотрудник. Расскажите, как следили за ходом и что меняли по дороге. Закончите итогом план-факт честно, даже если цель выполнена не целиком.

  • цели
  • планирование
227