Реализуйте класс LRUCache с заданной ёмкостью и двумя методами: get возвращает значение по ключу или None, put сохраняет значение. При переполнении вытесняется ключ, к которому дольше всего не обращались, и обе операции должны работать за O(1).
~15 мин голосом
Как подойти
Проверяют, умеет ли кандидат сочетать хеш-таблицу с упорядоченной структурой, чтобы получить O(1) на get и put, и аккуратно ли он обрабатывает граничные случаи: освежение ключа при get, обновление существующего ключа без вытеснения, отсутствующий ключ.
Интервьюер задаст этот вопрос и послушает. Думай вслух, проси подсказку, если нужно. Закончил — пауза или «Я ответил», через минуту здесь балл и какие пункты закрыты.