RandomizedSet.java

package design;

import java.util.*;

/**
 * Created by gouthamvidyapradhan on 23/03/2017. Design a data structure that supports all following
 * operations in average O(1) time.
 *
 * <p>insert(val): Inserts an item val to the set if not already present. remove(val): Removes an
 * item val from the set if present. getRandom: Returns a random element from current set of
 * elements. Each element must have the same probability of being returned. Example:
 *
 * <p>// Init an empty set. RandomizedSet randomSet = new RandomizedSet();
 *
 * <p>// Inserts 1 to the set. Returns true as 1 was inserted successfully. randomSet.insert(1);
 *
 * <p>// Returns false as 2 does not exist in the set. randomSet.remove(2);
 *
 * <p>// Inserts 2 to the set, returns true. Set now contains [1,2]. randomSet.insert(2);
 *
 * <p>// getRandom should return either 1 or 2 randomly. randomSet.getRandom();
 *
 * <p>// Removes 1 from the set, returns true. Set now contains [2]. randomSet.remove(1);
 *
 * <p>// 2 was already in the set, so return false. randomSet.insert(2);
 *
 * <p>// Since 2 is the only number in the set, getRandom always return 2. randomSet.getRandom();
 */
public class RandomizedSet {
  private Map<Integer, Integer> map;
  private List<Integer> list;
  private Random random;

  /** Initialize your data structure here. */
  public RandomizedSet() {
    map = new HashMap<>();
    list = new ArrayList<>();
    random = new Random();
  }

  /**
   * Main method
   *
   * @param args
   * @throws Exception
   */
  public static void main(String[] args) throws Exception {
    RandomizedSet rSet = new RandomizedSet();
    System.out.println(rSet.getRandom());
    System.out.println(rSet.insert(1));
    System.out.println(rSet.insert(2));
    System.out.println(rSet.insert(2));
    System.out.println(rSet.insert(3));
    System.out.println(rSet.remove(2));
    System.out.println(rSet.insert(2));
    System.out.println(rSet.getRandom());
    System.out.println(rSet.insert(234));
    System.out.println(rSet.insert(23));
    System.out.println(rSet.insert(22));
    System.out.println(rSet.getRandom());
    System.out.println(rSet.remove(245));
    System.out.println(rSet.remove(234));
    System.out.println(rSet.getRandom());
  }

  /**
   * 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.keySet().contains(val)) {
      int pos = list.size();
      map.put(val, pos);
      list.add(val);
      return true;
    }
    return false;
  }

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

  /** Get a random element from the set. */
  public int getRandom() {
    /*if(list.size() == 0) return 0;
    else if (list.size() == 1) return list.get(0);*/
    return list.get(random.nextInt(list.size() - 1));
  }
}