//Реализовать кеш с доступом к ключу за O(1) type LRUCache struct {} func (c *LRUCache) Get(key string) string {} func (c *LRUCache) Put(key string, value string) {}

Для реализации LRU-кеша с доступом к ключу за O(1) обычно используют комбинацию хеш-таблицы и двусвязного списка. Хеш-таблица обеспечивает быстрый доступ к элементам по ключу, а двусвязный список хранит порядок использования элементов, чтобы быстро обновлять LRU-политику.

Пример реализации на Go:

import "container/list"

type entry struct {
    key   string
    value string
}

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

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

func (c *LRUCache) Get(key string) string {
    if elem, ok := c.cache[key]; ok {
        c.list.MoveToFront(elem) // обновляем позицию в списке
        return elem.Value.(*entry).value
    }
    return "" // или другой индикатор отсутствия
}

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

    if c.list.Len() == c.capacity {
        // удаляем последний элемент (наименее недавно использованный)
        back := c.list.Back()
        if back != nil {
            c.list.Remove(back)
            delete(c.cache, back.Value.(*entry).key)
        }
    }

    elem := c.list.PushFront(&entry{key, value})
    c.cache[key] = elem
}

Такой подход обеспечивает операции Get и Put за амортизированное O(1).