answer-insert-delete-contains-and-getrandom-with-o1.java

public class Solution {
  private List<Integer> list;
  private Map<Integer, Set<Integer>> map; // key=n, value=set of indices
  private Random random = new Random();

  public Solution() {
    list = new ArrayList<>();
    map = new HashMap<>();
  }

  public boolean insert(int val) {
    boolean contains = map.containsKey(val);
    if (!contains) {
      map.put(val, new HashSet<>());
    }
    map.get(val).add(list.size());
    list.add(val);
    return !contains;
  }

  public boolean delete(int val) {
    if (!map.containsKey(val)) {
      return false;
    }        
    Set<Integer> indices = map.get(val);
    int index = indices.iterator().next();       
    indices.remove(index);
    if (indices.isEmpty()) {
      map.remove(val);
    }       
    if (index < list.size() - 1) {
      int lastVal = list.get(list.size() - 1);
      list.set(index, lastVal);
      map.get(lastVal).remove(list.size() - 1);
      map.get(lastVal).add(index);
    }
    list.remove(list.size() - 1);
    return true;
  }

  public boolean contains(int n) {
    return map.containsKey(n);
  }
  
  public int getRandom() {
    int n = random.nextInt(list.size());
    return list.get(n);
  }
}