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

Leetcode 380. Insert Delete GetRandom O(1)

type RandomizedSet struct {
    vStack []int
    // maps key to the index in keyStack
    vMap map[int]int
}


func Constructor() RandomizedSet {
    return RandomizedSet {
        vStack: []int{},
        vMap: map[int]int{},
    }
}

func (this *RandomizedSet) Insert(val int) bool {
    if _, ok := this.vMap[val]; ok {
        return false
    }
    this.vStack = append(this.vStack, val)
    this.vMap[val] = len(this.vStack)-1
    return true
}


func (this *RandomizedSet) Remove(val int) bool {
    if index, ok := this.vMap[val]; ok {
        delete(this.vMap, val)

        // swap the removed value with the last value in the stack
        tmp := this.vStack[len(this.vStack)-1]
        this.vStack[len(this.vStack)-1] = this.vStack[index]
        this.vStack[index] = tmp
        // only update the new key location if it actually moved
        if tmp != val {
            this.vMap[tmp] = index;
        }

        // remove the last value from the stack
        this.vStack = this.vStack[:len(this.vStack)-1]

        return true
    }
    return false
}


func (this *RandomizedSet) GetRandom() int {
    randomIndex := rand.Intn(len(this.vStack))
    return this.vStack[randomIndex]
}


/**
 * Your RandomizedSet object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */