Необходимо реализовать LRU-кэш на основе двусвязного списка.
Задание состоит из двух частей, которые необходимо выполнять последовательно.
Список имеет структуру вида
nil <- (next) front <-> ... <-> elem <-> ... <-> back (prev) -> nil
Необходимо реализовать следующий интерфейс List:
- Len() int // длина списка
- Front() *Item // первый Item
- Back() *Item // последний Item
- PushFront(v interface{}) *Item // добавить значение в начало
- PushBack(v interface{}) *Item // добавить значение в конец
- Remove(i *Item) // удалить элемент
- MoveToFront(i *Item) // переместить элемент в начало
Гарантируется, что методы Remove и MoveToFront вызываются от существующих в списке элементов.
Элемент списка Item:
- Value interface{} // значение
- Next *Item // следующий элемент
- Prev *Item // предыдущий элемент
Сложность всех операций должна быть O(1), т.е. не должно быть мест, где осуществляется полный обход списка.
Необходимо реализовать следующий интерфейс Cache:
- Set(key string, value interface{}) bool // Добавить значение в кэш по ключу
- Get(key string) (interface{}, bool) // Получить значение из кэша по ключу
- Clear() // Очистить кэш
Структура кэша:
- ёмкость (количество сохраняемых в кэше элементов)
- очередь [последних используемых элементов] на основе двусвязного списка
- словарь, отображающий ключ (строка) на элемент очереди
Элемент кэша должен хранить в себе ключ, по которому он лежит в словаре, и само значение. Для чего это нужно понятно из алгоритма работы кэша (см. ниже).
Алгоритм работы кэша:
- при добавлении элемента:
- если элемент присутствует в словаре, то обновить его значение и переместить элемент в начало очереди;
- если элемента нет в словаре, то добавить в словарь и в начало очереди (при этом, если размер очереди больше ёмкости кэша, то необходимо удалить последний элемент из очереди и его значение из словаря);
- возвращаемое значение - флаг, присутствовал ли элемент в кэше.
- при получении элемента:
- если элемент присутствует в словаре, то переместить элемент в начало очереди и вернуть его значение и true;
- если элемента нет в словаре, то вернуть nil и false
(работа с кешом похожа на работу с
map)
(*) Дополнительное задание: сделать кэш горутино-безопасным.
- Пайплайн зелёный - 4 балла
- Добавлены новые юнит-тесты для списка - 1 балл
- Добавлены новые юнит-тесты для кэша (включая тест на логику выталкивания из кэша редко используемых элементов) - до 3 баллов
- Понятность и чистота кода - до 2 баллов
- Дополнительное задание на баллы не влияет