​​LRU-кэш: Как сделать историю поиска за 3 строки кода (и пройти собеседование)

Мы в Звуке уже давно используем System Design для проверки знаний и умений кандидата. И часто, задача состоит в том, чтобы спроектировать 1-2 экрана похожих на те, что реализованы в приложении. Обычно это поиск + лента. И тут можно до бесконечности обсуждать способы реализации: пагинации списков, эффективного поиска, офлайн-кэширования и так далее. В этом и сложность этого этапа.

Так вот, один из таких вопросов это: "Как реализовать историю поиска и показывать пользователю последние запросы, а старые удалять?" Очень часто, кандидаты предлагают решение на базе HashMap. Предлагают хранить кол-во запросов/дату запроса и потом сортировать их от наиболее свежего до старого. Такой подход будет работать, но можно предложить более эффективное решение. Называется такой подход LRU-кэш.

LRU (Least Recently Used) — это алгоритм кэширования, который автоматически удаляет редко используемые данные, чтобы освободить место для новых.

Какие плюсы от LRU-кэша в данной задаче:

1. Автоматически удаляет старые элементы
Если пользователь искал много запросов, LRU удалит самые старые, оставив только последние (или N самых свежих).
Например, можно ограничить кэш 10 последними запросами.

2. Быстрый доступ к недавним элементам
LRU хранит элементы в порядке их использования, поэтому получить список недавних запросов можно за O(1).

3. Простота реализации
Во многих языках есть готовые реализации (например, LinkedHashMap в Java,

LinkedHashMap часто используется для реализации LRU-кэша, потому что эта структура данных сочетает в себе преимущества хеш-таблицы и связанного списка. Например с помощью accessOrder = true при любом обращении (вставка/чтение) элемент перемещается в конец. А метод removeEldestEntry() позволяет автоматически удалять самый старый элемент при превышении размера.

Вот так знание патерна LRU позволит вам не изобретать велосипед, а просто и эффективно решить такого рода задачу. Такие задачи - частый вопрос на собеседованиях (например, в Яндексе, Тинькофф, VK). И на практике, в android - проектах такие задачи постоянно встречаются. Например, библиотека Glide для кэширования ресурсов также использует LRU. Эти и другие эффективные подходы мы разбираем на курсе по System Design