3. Handling Randomness

Classic Questions

Design a map supporting the following operations:

Value put(Key k, Value v)
Value remove(Key k)
Value get(Key k)

Entry<Key, Value> getRandom()
Entry<Key, Value> removeRandom()

getRandom

• use array will be very efficient
• random(array.size()) as the random element's index
• O(1) getRandom

class Entry {
    Key key;
    Value value;
}

ArrayList<Entry> array;
HashMap<Key, Index> indexMap; // Instead of Map<Key, Entry>

// when remove element
index = indexMap.get(key);
if (index == array.size() - 1) {
    array.remove(array.size() - 1);
    indexMap.remove(key);
} else {
    array.set(index, array.get(array.size() - 1));
    array.remove(array.size() - 1);
    indexMap.put(array.get(index).key, index);
    indexMap.remove(key);
}