Дан только интерфейс. Нужно реализовать потокобезопасный кеш ограниченного
размера с вытеснением давно не использованных записей (LRU).
type Store interface {
Set(k, v string)
Get(k string) (v string, ok bool)
}
// NewLRU создаёт кеш на capacity записей (capacity < 1 считается как 1).
func NewLRU(capacity int) *LRU
func (c *LRU) Set(k, v string)
func (c *LRU) Get(k string) (v string, ok bool)
func (c *LRU) Len() int
Требования
- В кеше не больше
capacity записей. Если при Set нового ключа места нет,
вытесняется запись, к которой дольше всех не обращались.
- «Обращение» — это успешный
Get и любой Set. Set существующего ключа
обновляет значение, делает запись самой свежей и ничего не вытесняет. Get
отсутствующего ключа ничего не меняет.
Get и Set работают за O(1), без прохода по всем записям.- Методы безопасны при конкурентных вызовах, код проходит
go test -race.
- Только стандартная библиотека.
container/list использовать можно, но будь
готов написать двусвязный список руками.
Пример
c := NewLRU(2)
c.Set("a", "1")
c.Set("b", "2")
c.Get("a") // "1", true — теперь a свежее b
c.Set("c", "3") // места нет: вытесняется b
c.Get("b") // "", false
c.Get("a") // "1", true
c.Len() // 2
Устно: почему для Get не подходит RWMutex.RLock? Как спроектировать LRU
на 10⁶ RPS: шардирование, приблизительный LRU (CLOCK), что делают ristretto и
groupcache? Как добавить TTL?
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.