class RandomizedSet {

    /** Initialize your data structure here. */
    List<Integer> list;  //<val>
    Map<Integer,Integer> map; //<val,index>
    public RandomizedSet() {
        list = new ArrayList<>();
        map = new HashMap<>();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        list.add(val);
        map.put(val,list.size() - 1);
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int curIndex = map.get(val);
        int lastIndex = list.size() - 1;
        map.put(list.get(lastIndex), curIndex);
        list.set(curIndex,list.get(list.size() -1));
        map.remove(val);
        list.remove(lastIndex);
        return true;
    }

    /** Get a random element from the set. */
    public int getRandom() {
        int random = (int)(Math.random() * (list.size()));
        return list.get(random);
    }
}