Medium
這個面經題一做，暴露出來不少基礎問題。比如hashmap的key是不能修改的，只能remove舊的再put新的竞思，不可以modify. 還有hashMap的key, value一定要給自己多一點思路空間，就像之前面google那位面試官說的tree里的children做key, parent做value這種逆向思維可以多嘗試钞护，思路打開一點.

我一開始remove做成了O(n), 導致了TLE. 因為hashmap的key是index, value是val, 這樣的話要刪除某個val我得先遍歷keySet()來找該val對應的key. 后來直接用val做key的話remove時直接O(1)就找到這個val. 同時開了一個list來存vals.這樣可以很容易拿到最后insert的val, 在remove時我們是通過把最后加入的移到被刪除的地方盖喷，然后刪掉最后加入的原來的key-value pair的, 所以能方便拿到最后加入的元素很重要。同時注意一下list.remove(int index)和list.remove(Object o)這兩個方法當Object是Integer的時候注意一下轉換類型难咕，不然會被當成是index.

class RandomizedSet {
    Map<Integer, Integer> map;
    List<Integer> list;
    /** Initialize your data structure here. */
    public RandomizedSet() {
        map = new HashMap<>();
        list = new ArrayList<>();
    }
    
    /** 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;
        } else {
            map.put(val, list.size());
            list.add(val);
            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;
        } else {
            map.put(list.get(list.size() - 1), map.get(val));   
            map.remove(val);
            list.remove((Integer) val);
            return true;
        }
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        Random rand = new Random();
        int randIndx = rand.nextInt(list.size());
        return list.get(randIndx);
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */