Давайте сегодня рассмотрим еще одну задачу на имплементацию структуры данных. Только в этот раз возьмем задачу не с Leetcode, а с реального интервью в Google.
Сложность: 🟠 Средняя
ℹ️ Описание
Реализуйте структуру данных для управления числами, которая имплементируют следующие методы:
▶️ Insert — добавляет новый элемент в структуру без создания дубликатов.
▶️ Remove — удаляет выбранный элемент из массива.
▶️ GetRandom — возвращает случайного элемент из ранее добавленных с равной вероятностью.
⚠️ Ограничения
Все методы должны работать с константной сложностью по времени — O(1).
1️⃣ Пример
Добавление значений в структуру.
const store = new Store()
store.insert(1)
store.insert(2)
store.insert(3)
store.insert(2)
// values — 1, 2, 3
2️⃣ Пример
Удаление значений из структуры.
const store = new Store()
store.insert(1)
store.insert(2)
store.insert(3)
store.remove(2)
// values — 1, 3
3️⃣ Пример
Получение случайного значения из структуры.
const store = new Store()
store.insert(1)
store.insert(2)
store.insert(3)
const value = store.getRandom()
// value — 1 (2 или 3 с одинаковой вероятностью)
✅ Решение
Посмотреть решение
#arrays #maps #medium