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