Создание LRU‑кэша с методами Get и Put

Необходимо реализовать структуру данных LRU‑кеш, предоставляющую два публичных метода. Метод Get(key) возвращает сохранённое значение по заданному ключу, а если ключ отсутствует — возвращает -1. Метод Put(key, value) вставляет новую пару или обновляет существующую. При достижении предельного размера кэша следует удалять элемент, который использовался дольше всех.

type LRUCache struct {}

func Constructor(capacity int) LRUCache
func (c *LRUCache) Get(key int) int
func (c *LRUCache) Put(key int, value int)

Пример применения:

cache := Constructor(2)
cache.Put(1, 1)
cache.Put(2, 2)
cache.Get(1)    // вернёт 1
cache.Put(3, 3) // удалит ключ 2
cache.Get(2)    // вернёт -1 (не найден)
cache.Put(4, 4) // удалит ключ 1
cache.Get(1)    // вернёт -1 (не найден)
cache.Get(3)    // вернёт 3
cache.Get(4)    // вернёт 4