Нужны две структуры: map[key]*list.Element для O(1) поиска и container/list для порядка использования. Get: ищешь в map, перемещаешь в начало списка, возвращаешь значение. Put: если ключ есть — обновляешь и двигаешь в начало. Если нет — добавляешь в начало, если превышен capacity — удаляешь последний элемент списка и из map. Для конкурентного доступа оборачиваешь в sync.Mutex. Есть готовые библиотеки (hashicorp/golang-lru), но на собеседовании просят написать с нуля.