Реализуйте множество целых чисел, в котором все операции работают за O(1)
в среднем, включая выбор случайного элемента с равномерным распределением.
(LeetCode 380 Insert Delete GetRandom O(1).)
type DynamicSet struct{ /* ... */ }
func NewDynamicSet() *DynamicSet
// Insert добавляет v. Возвращает false, если v уже был в множестве.
func (s *DynamicSet) Insert(v int) bool
// Remove удаляет v. Возвращает false, если v не было.
func (s *DynamicSet) Remove(v int) bool
// Find сообщает, есть ли v в множестве.
func (s *DynamicSet) Find(v int) bool
// GetRandom возвращает случайный элемент; каждый — с вероятностью 1/Len.
// Для пустого множества ok == false.
func (s *DynamicSet) GetRandom() (v int, ok bool)
// Len — число элементов.
func (s *DynamicSet) Len() int
На собесе интерфейс дают в виде Insert(int); Remove(int); Find(int) bool; GetRandom() int. Здесь добавлены результаты bool: так в Go принято сообщать
«ничего не изменилось» и «элемента нет».
Пример
s := NewDynamicSet()
s.Insert(1) // true
s.Insert(2) // true
s.Insert(1) // false
s.Remove(1) // true
s.Find(1) // false
s.GetRandom() // 2, true
Ограничения: до 10⁶ операций, значения — любые int. Тесты проверяют
асимптотику и распределение GetRandom статистически.
Устно: почему выбор «первого элемента при обходе map» не годится для
GetRandom? Как добавить поддержку дубликатов (мультимножество)?
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.