CareerCup

This is a fast set.
By set's concept of set and get, you can add and remove element in O(1).
Issue here is, you can not get random element from this DS.

What we need to do for resolving this, we need one map and one array.
In map, we will have key and value (let's say that value is a Node)

In array, there will be a item like the following:
Node.1 - Node.2 - Node.3 - Node.4
In Map, there will be key value-pairs like
<key.1, Node.1>, <key.2, Node.2>, <key.3, Node.3>, <key.4, Node.5>

In this case, add certainly be O(1), since you can add new node to list and map via O(1).
Get random element also be O(1) since you can retrieve any value from the list.

Real issue remaining at this point is: then, how do delete something at O(1)?
There is a magic:
When you need to delete with some element that is located interim of list.
Swap that element with the last element of the list. Then delete the last.
Yes!, since you remove last element from the list, it will be O(1).

Code will look like:

public class FastSet { // add, remove, get, all behaviors are done at O(1)
  private static final Random RANDOM = new Random();

  private final Map<String, FastSetNode> strCache;
  private final List<FastSetNode> posCache;
  private int position = 0;

  FastSet() {
	strCache = new HashMap<>();
	posCache = new ArrayList<>();
  }

  public boolean addItem(String input) {
	if (strCache.containsKey(input)) {
		return false;
	}
	FastSetNode n = new FastSetNode(input, position);
	strCache.put(input, n);
	posCache.add(position++, n);
	return true;
  }

  public boolean removeItem(String input) {
	if(!strCache.containsKey(input)) { 
		return false;
	}
	FastSetNode removal = strCache.remove(input); 		//Change this removal node with end node
	FastSetNode finalOne = posCache.remove(--position);
	// Delete the final element from list
	if (removal.equals(finalOne)) {
		return true;
	}
	posCache.set(removal.position, finalOne);
	finalOne.position = removal.position;
	return true;
  }

  public String get() {
	int randomPosition = RANDOM.nextInt(position);
	return posCache.get(randomPosition).data;
  }

  @Override
  public String toString() {
	StringBuilder str = new StringBuilder();
	posCache.stream().forEach((dNode) -> {
	  str.append(dNode.toString()).append("\n");
	});
	return str.toString().substring(0, str.toString().length() - 1);
  }

  public static class FastSetNode {
	private final String data;
	private int position;

	private FastSetNode(String data, int position) {
	  this.data = data;
	  this.position = position;
	}
  }

hashset or hashmap in the average case..

Using an array and hashmap. Inserting is O(1) for both. Deleting involves searching, which the hasmap makes an O(1) operation. The array makes random lookup O(1).

When an item is deleted, we don't need to remove it from the array and rearrange the array. We can just mark the array cell as deleted.

The random look up will be just generating a subscript value for the array. If the cell at the subscript is marked as deleted, do it again.

Here is a C++ implementation:

class MyDataStructure {
public:
    void insert(int element);
    void remove(int element);
    int lookup();
private:
    unordered_map<int, size_t> hash;
    vector<pair<int, bool>> mainVector;
};
void MyDataStructure::insert(int element) {
    hash[element] = mainVector.size();
    mainVector.push_back({element, true});
}
void MyDataStructure::remove(int element) {
    auto idx = hash[element];
    if(idx < mainVector.size()) {
        mainVector[idx].second = false;
    }
}
int MyDataStructure::lookup() {
    while (true) {
        auto v = mainVector[rand() % mainVector.size()];
        if(v.second) {
            return v.first;
        }
    }
}

in python

import random

class MyDataStructure(object):

    def __init__(self):
        self.d = {} # hash table
        self.li = [] # dynamic resizing array

    def insert(self, key):
        if key in self.d:
            index = self.d[key]
            self.d[key] = index
            self.li[index] = key
        else:
            self.d[key] = len(self.li)
            self.li.append(key)

    def remove(self, key):
        if key in self.d:
            index = self.d[key] # get the index for the key
            last_key = self.li[-1] # the key for the last element in the list
            self.li[index] = last_key # set it in the index which you want to remove

            # update the hashtable to reflect this index change
            old_index = self.d[last_key]
            self.d[last_key] = index

            # proceed to delete the entry
            del self.d[key]
            self.li.pop()

    def contains(self, key):
        return key in self.d

    def get_random(self):
        length = len(self.li)
        key = self.li[random.randrange(length)]
        return key

if __name__ == '__main__':
    ds = MyDataStructure()
    ds.insert('Hen')
    ds.insert('Donkey')
    ds.insert('Pig')

    print "Debug 1: ", ds.d, ds.li

    for _ in range(4):
        print ds.get_random()

    ds.remove('Hen')

    print "Debug 2: ", ds.d, ds.li

Using an array for storing the items and a HashMap to map from value to index in the array where the value is stored. Removing an item "shrinks" the array buy replacing the last item into the index of the removed value and updating the hashmap of that movement.

public class DataStructure {

	private int[] items = new int[4];
	private int count = 0;
	private HashMap<Integer, Integer> indexMap = new HashMap<>();
	
	public void insert(int value) 
	{
		makeRoom(1);
		items[count] = value;
		indexMap.put(value, count);
		count++;
	}
	
	public boolean remove(int value) 
	{
		if (!indexMap.containsKey(value))
			return false;
		
		int index = indexMap.get(value);
		items[index] = items[count - 1];
		indexMap.put(items[count-1], index);
		count--;
		return true;
	}
	
	public int get()
	{
		if (count == 0)
			return -1;
		
		int index = new Random().nextInt(count);
		return items[index];
	}
	
	private void makeRoom(int nItems)
	{
		int requiredCapacity = count + nItems;
		
		if (items.length >= requiredCapacity)
			return;
		
		int capcaity = items.length;
		while (capcaity < requiredCapacity)
			capcaity *= 2;
		
		int[] newArray = new int[capcaity];
		System.arraycopy(items, 0, newArray, 0, count);
		items = newArray;
	}
}

public class Lookup {
	ArrayList<Integer> al = new ArrayList<>();
	
	void insertElement(int value)	{
		al.add(value);
	}
	
	void deleteElement(int value)	{
		al.remove(value);
	}
	
	int lookUp()	{
		return al.get(new Random().nextInt(al.size()));
	}
	
	void printArray()	{
		System.out.println(al);
	}
}