List

Insert Delete GetRandom O(1)

The key is to swap last item with the item need to delete, and remove last.

let list[i] = last value

let map[last value] = i;

public class RandomizedSet {
    Random rnd;
    Dictionary<int,int> hs = new Dictionary<int,int>();
    List<int> list = new List<int>();
    /** Initialize your data structure here. */
    public RandomizedSet() {
        rnd = new Random();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public bool Insert(int val) {
        if(hs.ContainsKey(val)) {
            return false;
        }
        hs.Add(val, list.Count);
        list.Add(val);
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public bool Remove(int val) {
        if(!hs.ContainsKey(val))   return false;

        if(val != list[list.Count-1]){
            list[hs[val]] = list[list.Count-1];
            hs[list[list.Count-1]] = hs[val];
        }
        hs.Remove(val);
        list.RemoveAt(list.Count -1);

        return true;
    }

    /** Get a random element from the set. */
    public int GetRandom() {
        return list[rnd.Next(list.Count)];
    }
}