PrepBro
← Назад к вопросам

Ограниченное хранение данных в map

1.6 Junior🔥 201 комментариев
#Основы Go

Условие

Реализуйте структуру данных - map с ограничением по количеству элементов. При превышении лимита удаляется самый старый элемент (FIFO).

Интерфейс

type LimitedMap struct {
    // ваши поля
}

func NewLimitedMap(maxSize int) *LimitedMap
func (m *LimitedMap) Set(key string, value interface{})
func (m *LimitedMap) Get(key string) (interface{}, bool)
func (m *LimitedMap) Delete(key string)
func (m *LimitedMap) Len() int

Требования

  • При добавлении нового элемента, если достигнут лимит, удалить самый старый
  • Сохранять порядок добавления элементов
  • Операция Get не влияет на порядок (в отличие от LRU)

Пример

m := NewLimitedMap(3)
m.Set("a", 1)
m.Set("b", 2)
m.Set("c", 3)
m.Set("d", 4) // удаляется "a"
_, ok := m.Get("a") // ok = false

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Ограниченное хранилище (FIFO Map)

Описание задачи

Мап с максимальным размером где при превышении лимита удаляется самый старый элемент (FIFO - First In First Out).

Отличие от LRU:

  • LRU: Get перемещает элемент в конец (свежий)
  • FIFO: Get не влияет на порядок, только время добавления

Архитектура

Используем две структуры:

  1. map[string]interface{} - для быстрого доступа O(1)
  2. []string - очередь ключей в порядке добавления

Это дешевле чем двусвязный список как в LRU.

Реализация FIFO

Непосредственно используем:

  • Mutex для синхронизации
  • map для быстрого Get/Set
  • slice для отслеживания порядка

Алгоритм Set:

  1. Если key уже существует: обновляем значение, порядок не меняем
  2. Если key новый: a. Если длина меньше maxSize: добавляем в конец queue b. Если длина равна maxSize: удаляем первый элемент из map и queue, добавляем новый
  3. Обновляем значение в map

Алгоритм Get:

  1. Простой lookup в map
  2. Возвращаем значение и флаг
  3. Порядок не меняется

Алгоритм Delete:

  1. Удаляем из map
  2. Удаляем из queue

Сложность

  • Set: O(n) - удаление из начала queue требует переноса элементов
  • Get: O(1) - простой lookup в map
  • Delete: O(n) - поиск и удаление из queue
  • Len: O(1) - длина map

Оптимизация: Deque

Для O(1) Remove из начала используем container/ring или реализуем deque:

Вместо []string queue используем:

  • Двусвязный список для O(1) удаления
  • map[string]*Node для быстрого поиска

Это дает O(1) для всех операций.

Особенности реализации

  1. При обновлении существующего ключа порядок не меняется
  2. Get не создает side effects
  3. Delete удаляет из обеих структур данных
  4. При превышении лимита удаляется из очереди в порядке FIFO

Тестовые случаи

  1. Добавление элементов до лимита
  2. Добавление элемента при достижении лимита (должен удалиться первый)
  3. Обновление существующего элемента (порядок не меняется)
  4. Удаление элемента
  5. Get несуществующего элемента
  6. Get существующего элемента
  7. Проверка длины после операций

Разница между FIFO и LRU

Пример с лимитом 2: Добавляем: a, b, c

FIFO (эта задача):
  • Очередь: [b, c]
  • Удален a (самый старый по времени добавления)

LRU:

  • Очередь зависит от Get операций
  • Если делали Get(a) перед добавлением c, то удалится b
  • Если не делали Get, удалится a

Edge cases

  1. maxSize = 0: не добавляем ничего
  2. maxSize = 1: только один элемент
  3. Обновление элемента в очереди
  4. Delete элемента в середине очереди
  5. Одновременные операции (нужен Mutex)
Ограниченное хранение данных в map | PrepBro