Реализуйте LRU-кэш на заданное число элементов на основе LinkedHashMap

ЗадачаSeniorЧасто

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

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

LinkedHashMap умеет хранить порядок доступа: передайте третьим аргументом конструктора true, это флаг accessOrder, и каждый get или put перенесет запись в конец. Переопределите removeEldestEntry, чтобы он возвращал size() > capacity: после вставки карта сама удалит самую давнюю запись. Чтение и запись идут за O(1). Класс не потокобезопасен, для общего кэша нужна синхронизация.

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

LRU-кэш проверяет, знаете ли вы стандартную библиотеку глубже HashMap и можете ли объяснить сложность операций. От senior после кода ждут разговора о потоках, готовых кэшах вроде Caffeine и вытеснении с учетом частоты.

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

Приложение электронной библиотеки показывает обложки книг и держит последние открытые в памяти. Реализуйте LRU-кэш на заданное число элементов на основе LinkedHashMap: при переполнении удаляется обложка, к которой дольше всего не обращались. Проверьте кэш емкостью 2 на операциях из таблицы и после шагов 2, 3 и 4 выводите ключи от самого давнего к самому свежему.

ШагОперация
1put Дюна
2put Аэлита
3get Дюна
4put Солярис

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

  1. Создайте наследника LinkedHashMap, например анонимный класс в фабричном методе
  2. Передайте третьим аргументом конструктора true: флаг accessOrder заставит get переносить запись в конец
  3. Переопределите removeEldestEntry и возвращайте true, когда размер превысил емкость
  4. Прогоните шаги из условия и убедитесь, что вытеснена Аэлита

Решение

Внутри LinkedHashMap — хеш-таблица и двусвязный список записей. В режиме доступа get и put перецепляют запись в хвост за O(1), голова списка — самая давняя запись. removeEldestEntry вызывается после каждой вставки нового ключа, и true удаляет голову. Число 16 в конструкторе — начальный размер таблицы, лимит кэша задает capacity.

Java
public class Main {
    public static void main(String[] args) {
        Map<String, String> covers = lru(2);
        covers.put("Дюна", "dune.jpg");
        covers.put("Аэлита", "aelita.jpg");
        System.out.println("put Аэлита: " + covers.keySet());
        covers.get("Дюна");
        System.out.println("get Дюна: " + covers.keySet());
        covers.put("Солярис", "solaris.jpg");
        System.out.println("put Солярис: " + covers.keySet());
    }
    static <K, V> Map<K, V> lru(int capacity) {
        return new LinkedHashMap<>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > capacity;
            }
        };
    }
}
Вывод
put Аэлита: [Дюна, Аэлита]
get Дюна: [Аэлита, Дюна]
put Солярис: [Дюна, Солярис]

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

  • Как сделать этот кэш потокобезопасным?

  • Как написать LRU без LinkedHashMap?

  • Какие методы считаются обращением к записи?

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

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

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

  • «Создам new LinkedHashMap<>() и буду удалять первый ключ при переполнении»

    Конструктор по умолчанию хранит порядок вставки, и получится очередь FIFO: часто открываемая обложка вылетит первой. Включите режим доступа третьим аргументом конструктора

  • «Проверю емкость перед put и удалю старую запись сам»

    Ручная проверка дублирует removeEldestEntry, и ее придется повторить в putAll, merge и compute. Переопределите этот метод: карта вызывает его после каждой вставки нового ключа

  • «super(capacity) задаст лимит кэша»

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

  • «Повторный put того же ключа увеличит размер, и что-то вытеснится»

    Повторный put заменяет значение и переносит запись в конец, размер не меняется. Вытеснение случается только при новом ключе, когда записей становится больше емкости

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

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

Объясняет, почему обе операции идут за O(1), и сам спрашивает, будут ли кэшем пользоваться несколько потоков

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

Собирает кэш из HashMap и ArrayList и ищет давнюю запись перебором за O(n)

Красный флаг

Путает LRU с вытеснением по времени жизни и предлагает чистить кэш таймером раз в минуту

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

  • Как реализовать LRU-кэш в Java?
  • Для чего нужен параметр accessOrder у LinkedHashMap?
  • Как сделать кэш фиксированного размера, который вытесняет давно неиспользуемые записи?
  • Напишите кэш с политикой вытеснения LRU

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

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

Как устроен HashMap внутри: бакеты, коллизии, расширение и деревья с Java 8?

HashMap хранит записи в массиве бакетов. Номер бакета считается из hashCode() ключа: старшие биты хеша смешиваются с младшими, результат обрезается маской по размеру таблицы. Ключи с одним номером лежат в бакете цепочкой и различаются через equals(). Когда записей больше 0,75 от емкости, таблица удваивается. С Java 8 длинная цепочка превращается в красно-черное дерево.

  • Коллекции
  • HashMap
262
ЗнаниеJuniorЧасто

Чем ArrayList отличается от LinkedList и когда LinkedList действительно быстрее?

ArrayList хранит элементы в массиве: доступ по индексу за O(1), вставка в конец в среднем тоже, вставка в середину сдвигает хвост. LinkedList — двусвязный список: get(i) идет по узлам от ближнего края, зато вставка и удаление через итератор, который уже стоит на месте, занимают O(1). На практике почти всегда быстрее ArrayList, а для очереди берут ArrayDeque.

  • коллекции
  • Java Core
273
ЗнаниеSeniorЧасто

Как найти утечку памяти в Java-приложении, которое падает с OutOfMemoryError: Java heap space?

Сначала отличите утечку от нехватки памяти: при утечке занятая куча после каждой полной сборки растет и не возвращается. Включите -XX:+HeapDumpOnOutOfMemoryError, чтобы получить дамп в момент падения, или снимите его через jcmd. В Eclipse MAT найдите в дереве доминаторов объект, который держит больше всего памяти, и пройдите путь до корня: он покажет, чья ссылка не отпускает объекты.

  • JVM
  • память
248
ЗадачаJuniorЧасто

Объект-ключ не находится в HashMap, хотя все поля совпадают — исправьте класс ключа

HashMap по hashCode ключа выбирает корзину, в ней сначала сравнивает сохраненный хеш и только при совпадении вызывает equals. В классе переопределен один equals, hashCode берется из Object, и у двух одинаковых мест хеши почти всегда разные: до equals дело не доходит. Переопределите hashCode по тем же полям, что и equals, например через Objects.hash, а поля сделайте final.

  • Коллекции
  • HashMap
236

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

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

Да, это нормальный ответ, если вы объясните, что происходит внутри. Учтите, что наследник открывает наружу все методы Map, включая putAll и entrySet. Если нужен строгий интерфейс кэша с двумя методами, спрячьте карту внутри своего класса и делегируйте ей get и put.

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

Устройство HashMap с бакетами и деревьями, LinkedHashMap в двух режимах, TreeMap и NavigableMap, ConcurrentHashMap и его атомарные методы вроде computeIfAbsent. Для каждой структуры держите в голове сложность операций и один пример из своей практики, где вы ее выбрали.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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