Что такое LRU Cache — пример ответа на собеседовании Golang Разработчик

Что такое LRU Cache

«Что такое LRU Cache» — вопрос из категории Архитектура, который задают на 23% собеседований Golang Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Тип вопроса: Архитектура Вероятность: 23% Категория: Golang Разработчик

Ответ

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

Основные принципы:

Использует хеш-таблицу для быстрого доступа
Поддерживает порядок использования через двусвязный список
При переполнении удаляет самый старый элемент

Пример на Go:

type LRUCache struct {
    capacity int
    cache    map[int]*list.Element
    list     *list.List
}

type entry struct {
    key, value int
}

func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        capacity: capacity,
        cache:    make(map[int]*list.Element),
        list:     list.New(),
    }
}

func (c *LRUCache) Get(key int) int {
    if elem, ok := c.cache[key]; ok {
        c.list.MoveToFront(elem)
        return elem.Value.(*entry).value
    }
    return -1
}

func (c *LRUCache) Put(key, value int) {
    if elem, ok := c.cache[key]; ok {
        elem.Value.(*entry).value = value
        c.list.MoveToFront(elem)
        return
    }
    if len(c.cache) >= c.capacity {
        oldest := c.list.Back()
        delete(c.cache, oldest.Value.(*entry).key)
        c.list.Remove(oldest)
    }
    elem := c.list.PushFront(&entry{key, value})
    c.cache[key] = elem
}

Применение: Кеширование, базы данных, веб-серверы.