CareerCup

There are 3 basic structures that are required for these operations.
1. Hashmap : to support add, delete, contains
2. Double linked list : to support most recent entry. That is most recent added. Since we are using hashmap, to maintain last added value (most recent) we required double linked list.. (double linked list helps in the case of deletion - we can delete any element).. getMostRecent() will be in o(1)
3. One array : to keep the number of elements present upto date. This will help in randomization... getRandom() will be o(1)

structure of one node in hash will be
hash[value] = {array index, double linked list ptr}

So, the operations will be..

1. add(e) : when we add one value, hash[e] = {arr index, double linked list ptr}
2. delete(e) : when we delete one value, We are going to replace the cell that contains value in array with the last element in array. let d be the last element in the array A at index m. let i be H[value], the index in the array of the value to be removed. Set A[i]=d, H[d]=i, decrease the size of the array by one, and remove value from H. Since we are keeping a double linked list ptr.. deletion will be an easier operation to keep the most recent accordingly...
3. contains(e) : returns hash.contains(e)
4. getRandom() : return array[rand() % (array length)]
5. getMostRecent() : return last element of the double linked list

It will required a combination of HashMap, DoublyLinkedList and a random method.
1. Use HashMap\Table to store elements in key value pairs (we can use element as a key too).
Now all of these operations will be in O(1) complexity:
1. void add(e)
2. void delete(e)
3. boolean contains(e)

2. We need a linked list to perform getMostRecent() in O(1), and i will prefer doubly linked list to remove the complexity of last element.
Each time you access an element from the map, just add it's reference at the end of list. If you delete an element than find its reference from the map and remove from list too.

3. We will need a random method for getRandom(). 
//Class variable 
int previousRandom = 0;
e getRandom(){
   //Select any two prime numbers as A and B
   previousRandom = (A * previousRandom  + B) Mod sizeOfMap;
   //use  previousRandom  as hashcode to find an element from the map.
}

When you are saying the elment to be key itself, then we are assuming that all the objects inserted will be immutable objects. I don't think that is the case.

We should use hashcode as key for storing data in hashmap.

template<class T>
class MyContainer {
private:
	typedef struct MyNode {
		T val;
		MyNode* next;
		MyNode* prev;
	} LNode, *PLNode;

	hash_map<T, PLNode> m_container;
	PLNode m_head, m_tail;
public:
	void add(T e) {
		PLNode tmp = new LNode();
		tmp->val = e;
		tmp->prev = nullptr;
		tmp->next = m_head;
		m_head = tmp;
		m_container.insert(pair(e, tmp);
	}
	void delete(T e) {
		PLNode tmp = m_container.find(e).second;
		tmp->prev->next = tmp->next;
		delete tmp;		
		m_container.erase(e);
	}
	bool contains(T e) { return (m_container.find(e) != m_container.end()) }
	T getRandom(){
		int size = m_container.size();
		int randomIndex = rand() % size - 1;

		return (m_container.begin() + randomIndex).first;
	}
	T getMostRecent() {
		return m_head->val;
	}
};

Are duplicate values allowed?

With the hash table we can achieve this.

1. Add -> 0(1)
2. Delete -> O(1)
3. Contains -> 0(1)
4. GetRandom -> Need a random number generator to arbitrarily select the some random key, store it in a class variable (say mostRecent) and return the value.
5. GetMostRecent -> Using the mostRecent variable get the hashkey and return the value.

I think HashMap can solve the problem. Add/Delete/Contains will be O(1) as it's nothing but a Entry Array operations on Array will be O(1), hashing works on bucketing system so finding random number should match to the bucket number.

package com.sumologic.codingexercise;

import java.util.HashMap;
import java.util.Random;

class CustomDS2 {
    private HashMap<Integer, Integer> map;
    private int[] arr;
    private int currentSize = 0;

    public CustomDS2(int maxCapacity) {
        map = new HashMap<Integer, Integer>();
        arr = new int[maxCapacity];
    }

    public void add(int e) {
        arr[currentSize] = e;
        currentSize++;
        map.put(e, currentSize);
    }

    public void remove(int e) {
        int d = arr[currentSize];
        int i = map.get(e);
        arr[i] = d;
        map.put(d, i);
        currentSize--;
        map.remove(e);
    }

    public boolean contains(int e) {
        return map.containsKey(e);
    }

    public int getRandom() {
        Random random = new Random();
        int rand = random.nextInt(currentSize);
        return arr[rand];
    }
}

import random

class DoubleLinkedList():
  def __init__(self, data):
    self.data = data
    self.next = None
    self.prev = None

class Hash():
  def __init__(self):
    self.map = {}
    self.head = None
    self.current = None
    self.recent_element_list = []

  def contains(self, e):
    """
    This function checks if the element
    alreadys exists in the map
    @param : e element to be found
    @return : True or False
    """
    element = self.map.get(e, None)
    if element:
     return True
    else:
     return False
  
  def add(self, e):
    """
    This function is used to add any element 
    in the map
    """

    # Checking in the element already exists
    # in the map. 
    if self.contains(e):
      print "Element already exists in the Hash"
    else:
      if self.head is None or self.current is None:
        element = DoubleLinkedList(e)
        self.head = element
        self.current = element
      else:
        element = DoubleLinkedList(e)
        element.prev = self.current
        element.prev.next = element
        self.current = element
      self.map[e] = element

  def delete(self, e):
    """
    This function deletes the element from the
    map
    @param: e element to be deleted
    """

    # Checking in the element already exists
    # in the map.
    if self.contains(e):
      if self.map[e] == self.current:
        self.current = self.current.prev
        element = self.map[e]
        del(element)
      else:
        element = self.map[e]
        if element.next == self.current:
          self.current.prev = element.prev
        if self.head == element:
          self.head = element.next
          element.next.prev = element.prev
        else:
          element.prev.next = element.next.prev
          element.next.prev = element.prev.next
      self.map.pop(e, None)
      
    else:
      print "Element doesn't exists in the Hash"

  def getRandom(self):
    """
    This function returns any random element
    form the Hash
    """

    key_list = self.map.keys()
    if len(key_list) == 0:
      print "Hash is empty. Please enter the elements into Hash first"
    else:
      rand_index = random.randint(0, len(key_list)-1)
      rand_key = key_list[rand_index]
      return rand_key

  def getMostRecent(self):
    """
    This function returns the most recent element added
    in the Hash
    """
    
    # Checking if the recent element list contains
    # any element

    if self.current is not None:
      return self.current.data
    else:
      print "No element in the Hash"

A cpp sollution, except getRandom() all functions are almost constant order

#include<iostream>
#include<map>
#include<list>
#include<iterator>
#include<cstdlib>
#include<ctime>

using namespace std;

template <class E>
class myContainer {
private:
    map<E, typename list<E>::iterator> emap;
    list<E> elist;
    
public:
    void add(E e);
    void deleteElement(E e);
    void toString();
    bool contains(E e);
    E getRandom();
    E getMostRecent();
};

template <class E>
void myContainer<E>::add(E e) {
    if(contains(e)) return;
    emap[e] = elist.insert(elist.end(), e);
}

template <class E>
void myContainer<E>::deleteElement(E e) {
    if(!contains(e)) return;
    elist.erase(emap[e]);
    emap.erase(e);
}

template <class E>
inline bool myContainer<E>::contains(E e) {
    if(emap.find(e) != emap.end()) return true;
    return false;
}

template <class E>
E myContainer<E>::getRandom() {
    typename list<E>::iterator it = elist.begin();
    int pos = rand()%elist.size();
    while(pos--) it++;
    return *it;
}

template <class E>
E myContainer<E>::getMostRecent() {
    return elist.back();
}

template <class E>
void myContainer<E>::toString() {
    typename map<E, typename list<E>::iterator>::iterator it;
    typename list<E>::iterator it1;
    cout << "Map contains:" << endl;
    for(it = emap.begin(); it!= emap.end(); it++) {
        cout << it->first << " ";
    }
    cout << endl;
    cout << "List contains:" << endl;
    for(it1 = elist.begin(); it1!= elist.end(); it1++) {
        cout << *it1 << "<->";
    }
    cout << endl;
}
int main() {
    srand(time(NULL));
    myContainer<int> intContainer;
    intContainer.add(1);
    intContainer.add(2);
    intContainer.add(3);
    cout << "Most recent " << intContainer.getMostRecent() << endl;
    intContainer.deleteElement(2);
    intContainer.deleteElement(2);
    intContainer.add(4);
    if(intContainer.contains(4)) {
        cout << "Contains " << 4 << endl;
    }
//    intContainer.toString();
    cout << "Random element: " <<intContainer.getRandom() << endl;
    return 0;
}

package com.test.coding;

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Stack;

public class LookUp<T> {

	Map<T, Integer> m;

	List<T> list;

	Stack<Node<T>> s;

	int currIndex;

	public LookUp() {
		m = new LinkedHashMap<T, Integer>();
		list = new ArrayList<T>();
		s = new Stack<Node<T>>();

		currIndex = 0;
	}

	void add(T val) {
		if (list.size() > currIndex) {
			list.set(currIndex, val);
		} else {
			list.add(currIndex, val);
		}
		Node<T> node = new Node<T>(val, currIndex);
		s.push(node);
		m.put(val, currIndex);
		currIndex++;

		System.out.println("add: " + list.toString());
	}

	void delete(T val) {
		if (m.containsKey(val)) {
			int elementIndex = m.get(val);
			System.out.println("Index: " + val + " " + elementIndex);
			m.remove(val);

			list.set(elementIndex, list.get(currIndex - 1));
			currIndex--;

			Node<T> topNode = s.peek();
			if (topNode.getIndex().equals(elementIndex)) {
				s.pop();
			}
		}
		System.out.println("delete: " + list.toString() + " curr index"
				+ currIndex);
	}

	boolean contains(T val) {
		if (m.containsKey(val)) {
			return true;
		}
		return false;
	}

	T getRecent() {
		if (!s.isEmpty()) {
			return s.peek().getVal();
		}
		return null;
	}

	T getRandom() {

		Random rand = new Random();
		int randomIndex = rand.nextInt((currIndex - 0) ) + 0;

		System.out.println("random index: " + randomIndex);
		return list.get(randomIndex);

	}

}

package com.test.coding;

public class Node<T> {

	private T val;
	private Integer index;

	public Integer getIndex() {
		return index;
	}

	public T getVal() {
		return val;
	}

	public Node(T val2, int lastIndex) {
		val = val2;
		index = lastIndex;
	}
}