Как бы вы реализовали LRU-кэш на Go? Расскажите о структурах данных, которые вы бы использовали, и их временной сложности.

А, LRU-кэш, классика жанра! Ну, блядь, задачка для тех, кто хочет показать, что он не просто for-ом умеет пользоваться, а и в структурах данных немного шарит.

Смотри, суть в чём: надо сделать такую штуку, которая помнит, что ты у неё спрашивал недавно, а что — давно. И когда место кончается, она безжалостно выкидывает то, до чего ты сто лет не дотрагивался, со словами «сам виноват, мудак». Как твоя оперативка, только в коде.

Чтобы не получилось говно с поиском за O(n), где на каждую операцию надо весь кэш перетряхивать, берём две вещи, которые дружат за O(1):

1. Обычная мапа (map). Ну, это понятно, по ключу быстро находим — хук, и готово. Но она одна не помнит, кто давно, а кто нет. Она как золотая рыбка, блядь.
2. Двусвязный список (container/list). Вот это уже мозги. В него будем складывать элементы в порядке использования. Только что тронул — перетащил в начало. В конце списка торчит самый забытый, несчастный элемент, которого уже все заебали.

А мапа будет хранить не просто значение, а указатель на кусок этого списка. Это ключевой момент, ёпта! Без этого хуй ты удалишь из середины списка за O(1). А так — раз! — по ключу в мапе нашли указатель, и тут же его из списка выковырили или в начало засунули.

Вот, смотри, как это выглядит в коде, не трогая его, как просил:

package main

import "container/list"

// LRUCache представляет собой LRU-кэш.
// Важно: данная реализация не является потокобезопасной.
// Для конкурентного использования необходимо добавить мьютекс (sync.RWMutex).
type LRUCache struct {
    capacity int
    cache    map[int]*list.Element // Ключ -> Указатель на узел в списке
    list     *list.List            // Двусвязный список для порядка использования
}

// entry хранит ключ и значение, чтобы мы могли удалить его из мапы при вытеснении.
type entry struct {
    key   int
    value int
}

// NewLRUCache создает новый LRU-кэш с заданной вместимостью.
func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        capacity: capacity,
        cache:    make(map[int]*list.Element),
        list:     list.New(),
    }
}

// Get получает значение по ключу. Если ключ найден, элемент перемещается в начало списка.
func (l *LRUCache) Get(key int) int {
    if elem, ok := l.cache[key]; ok {
        l.list.MoveToFront(elem) // O(1)
        return elem.Value.(*entry).value
    }
    return -1
}

// Put добавляет или обновляет значение по ключу.
func (l *LRUCache) Put(key, value int) {
    // Если элемент уже существует, обновляем его значение и перемещаем в начало.
    if elem, ok := l.cache[key]; ok {
        l.list.MoveToFront(elem) // O(1)
        elem.Value.(*entry).value = value
        return
    }

    // Если кэш заполнен, удаляем самый старый элемент (из конца списка).
    if l.list.Len() >= l.capacity {
        oldest := l.list.Back() // O(1)
        if oldest != nil {
            l.list.Remove(oldest) // O(1)
            delete(l.cache, oldest.Value.(*entry).key) // O(1)
        }
    }

    // Добавляем новый элемент в начало списка и в мапу.
    newEntry := &entry{key, value}
    elem := l.list.PushFront(newEntry) // O(1)
    l.cache[key] = elem // O(1)
}

Как это работает, если на пальцах:

• Get: Ты спрашиваешь ключ. Мапа говорит: «А, есть такой, вот ссылка на него в списке!». Мы берём этот элемент списка и, со свистом, перетаскиваем его в самое начало — теперь он «самый свежий». Всё, O(1), в рот меня чих-пых.
• Put: Ты кладёшь ключ.
  • Если он уже был — находим его через мапу, обновляем значение и, как верного пса, тащим в начало списка.
  • Если его не было, а место-то кончилось — тут начинается драма. Мы смотрим в конец списка. Там сидит самый запылившийся, невостребованный элемент. Мы на него так смотрим, вздыхаем: «Прости, дружок, таков закон джунглей». И выкидываем его нахуй и из списка, и из мапы.
  • А потом уже спокойно добавляем наш новый элемент в начало списка и кладём ссылку на него в мапу.

И вся эта песня исполняется за O(1) на каждую операцию, что и требовалось. Единственное, о чём надо помнить — эта реализация не для многопоточки. Если с двух городов начать её дергать, она взбесится и устроит race condition. Для этого нужно будет прикрутить sync.RWMutex, но это уже совсем другая история, про мудёж и блокировки.