insert-delete-getrandom-o1.go

// https://leetcode.com/problems/insert-delete-getrandom-o1

import "math/rand"

type RandomizedSet struct {
    table map[int]int
    dict []int
}


/** Initialize your data structure here. */
func Constructor() RandomizedSet {
    return RandomizedSet{
        table: make(map[int]int),
        dict: []int{},
    }
}


/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
func (s *RandomizedSet) Insert(val int) bool {
    _, ok := s.table[val]
    
    if ok {
        return false
    }
    
    index := len(s.dict)
    s.dict = append(s.dict, val)
    s.table[val] = index
    
    return true
}


/** Removes a value from the set. Returns true if the set contained the specified element. */
func (s *RandomizedSet) Remove(val int) bool {
    index, ok := s.table[val]
    
    if !ok {
        return false
    }
    
    dictLen := len(s.dict)
    
    // [.....ak....an] swap with the last one
    s.dict[index], s.dict[dictLen - 1] = s.dict[dictLen - 1], s.dict[index]
    
    // update val for swapped element
    swapped := s.dict[index]
    s.table[swapped] = index
    
    // delete the given value from table and reduce dictionary size
    delete(s.table, val)
    s.dict = s.dict[:dictLen - 1]
    
    return true
}


/** Get a random element from the set. */
func (s *RandomizedSet) GetRandom() int {
    index := rand.Intn(len(s.dict))
    val := s.dict[index]
    
    return val
}