Создать кеш с вытеснением по принципу FIFO

Условие

Нужно реализовать кеш ограниченного объёма, где удаление происходит по правилу «первый пришёл — первый ушёл». При попытке добавить элемент, превышающий максимальный размер, следует избавиться от самого раннего добавленного элемента (не важно, как часто к нему обращались). Функция get должна возвращать сохранённое значение, а если ключ отсутствует — -1.

put(int, int)     // добавляет значение по ключу
get(int, int) int // возвращает значение по ключу, если нет — -1

Ответ

FIFO использует порядок добавления, а Get его не меняет. Обновление существующего ключа здесь не переносит его в конец очереди.

У get в условии два int без объяснения второго. Используем get(key int) int:

import "container/list"

type fifoItem struct { key, value int }
type FIFO struct {
    capacity int
    order *list.List
    items map[int]*list.Element
}
func NewFIFO(capacity int) *FIFO {
    if capacity < 1 { panic("capacity must be positive") }
    return &FIFO{capacity, list.New(), make(map[int]*list.Element)}
}
func (c *FIFO) put(key, value int) {
    if e, ok := c.items[key]; ok {
        e.Value = fifoItem{key, value}
        return
    }
    if len(c.items) == c.capacity {
        e := c.order.Front()
        delete(c.items, e.Value.(fifoItem).key)
        c.order.Remove(e)
    }
    c.items[key] = c.order.PushBack(fifoItem{key, value})
}
func (c *FIFO) get(key int) int {
    if e, ok := c.items[key]; ok { return e.Value.(fifoItem).value }
    return -1
}

Средняя сложность O(1), лимит измеряется числом записей. В конкурентном варианте оба метода защищают общим mutex. Сохранённое -1 не отличить от промаха без изменения интерфейса.