Design a data structure that supports insert, delete, search and getRandom in constant time.

Design a data structure that supports following operations in Θ(1) time.

insert(x): Inserts an item x to the data structure if not already present.

remove(x): Removes an item x from the data structure if present.

search(x): Searches an item x in the data structure.

getRandom(): Returns a random element from current set of elements

Example:

insert(3); ds becomes {3} insert(4); ds becomes {3,4} insert(5); ds becomes {3,4,5} insert(6); ds becomes {3,4,5,6}

search(4); - returns true, search(10); - returns false;

getRandom()- can return anyone of the items in our data structure ....it may return either 3 or 4 or 5 or 6...because all form a part of the data structure now. So, returning any one of them is correct.

remove(4) - removes element 4 from the data structure, now data structure becomes {3,5,6}

getRandom()- returns any one of the elements from the set {3,5,6}. Returning any one of these 3 existing elements is correct

And so on...insertion(x), remove(x), search(key), getRandom() keep on going repeatedly onto our data structure, and each must be a constant time operation

Note: uniformity wasnt stressed in getRandom() operation as it was asked during a discussion round. It was merely asked to get any of the existing elements randomly....Random class of java came to the rescue for the interviewee. I am not sure how uniformity can be checked in online judge... Although, this question has been asked repeatedly at amazon

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Random;

/**
 * All operations work in constant time.
 */
public class RandomizedSet<T> {

  private Map<T, Integer> valueIndexes;
  private List<T> values;
  private Random rand;

  public RandomizedSet() {
    valueIndexes = new HashMap<>();
    values = new ArrayList<>();
    rand = new Random(System.currentTimeMillis());
  }

  public void add(T value) {
    if (!contains(value)) {
      int lastIndex = values.size();
      valueIndexes.put(value, lastIndex);
      values.add(value);
    }
  }

  public boolean contains(T value) {
    if (value == null) {
      throw new NullPointerException();
    }
    return valueIndexes.containsKey(value);
  }

  public T getRandom() {
    if (valueIndexes.isEmpty()) {
      throw new NoSuchElementException();
    }
    int randomIndex = rand.nextInt(values.size());
    return values.get(randomIndex);
  }

  public T deleteRandom() {
    if (valueIndexes.isEmpty()) {
      throw new NoSuchElementException();
    }
    int randomIndex = rand.nextInt(values.size());
    return deleteValue(randomIndex);
  }

  public T delete(T value) {
    if (!contains(value)) {
      throw new NoSuchElementException();
    }
    int index = valueIndexes.get(value);
    return deleteValue(index);
  }

  private T deleteValue(int currentIndex) {
    // remove the current element in the array, swap with the last,
    // and update the new index value in the map.
    T currentValue = values.get(currentIndex);
    int lastIndex = values.size() - 1;
    T lastVal = values.get(lastIndex);
    Collections.swap(values, currentIndex, lastIndex);
    // removing the last element is constant
    values.remove(lastIndex);
    valueIndexes.put(lastVal, currentIndex);
    valueIndexes.remove(currentValue);
    return currentValue;
  }

  public int size() {
    if (values.size() != valueIndexes.size()) {
      // should never happen.
      throw new IllegalStateException();
    }
    return values.size();
  }
}