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